「棒消し」や「まる消し」には必勝法があるという話
みなさん、「棒消し」や「まる消し」というゲームを知っていますか？
まず「棒消し」とは、下の図のように棒をたくさん書き、それを2人が交互に消していき、最後の棒を消したら負けというゲームです。
一回で消す棒の本数は自由(1本以上)ですが、同じ行にあるものだけです。
棒の本数、配置の仕方は自由
同じように、「まる消し」とは、複数ある丸を棒消しと同じように交互に消していき、最後の丸を消した人が負けというゲームです。
消せる丸は縦と横のみです（一つだけ消すのもOK。斜めも消せる場合もありますが、今回は簡単のため縦横のみで考えます。）
これも形は自由
そして、これらのゲームには必ず必勝法があります。
しかも、その形状に依らず必勝法は存在します。
ここで注意してほしいのが、
「必勝法は存在するが、そのやり方は簡単には求められない。」
ということです。
何言ってるかわからないと思うのですが、多分最後まで読めばわかります。
必勝法が存在する証明
まず、必勝法が存在するということは、
「すべての取りうるパターンが「勝ち確」と「負け確」にわけることができる」
という意味です。
ここで「勝ち確」と「負け確」という言葉を使いましたが、
勝ち確 : 自分の番でそのパターンになったとき、適切な選択をすれば必ず勝てる
負け確：自分の番でそのパターンになったとき、相手が適切な選択（最善手）をすると負ける
という定義とします。
黒がすでに線を引かれたところ
少し考えると、
「負け確」＝「相手から見た勝ち確」
であることがわかります。
そして
・全ての取りうるパターンがこの二択に分けられる
⇩
・全てのパターンが「勝ち確」か「負け確」＝「相手から見た勝ち確」に分けられる
⇩
・必勝法(後者の場合は後攻が勝ちとも言い換えられる。)
という流れが出来上がります。
今、消されていない棒の数をnとおきます。
（「まる消し」の場合は消されていない丸の数）
・n=0のとき、消せる棒がありません。すなわち相手が消したと解釈できるため「勝ち確」となります。
・n=1のときは、消されていない棒がどこにあろうが、それは「負け確」です。
・n=2のときはどうでしょうか。
自分の番でどの棒を消そうが、相手の番にはn=1,0のパターンになります。すなわち、「勝ち確」と「負け確」のいずれかになります
この消し方を全て考えたとき、その消したあとのパターンの中に1つ以上「負け確」のパターンがあれば、元のパターンは「勝ち確」です。
「負け確」のパターンになるように棒(丸)を消せば良いのです。
一方、1つも「負け確」がなかったら元のパターンは「負け確」です。
どのように棒(丸)を消しても、相手のパターンが「負け確」では無い、すなわち「勝ち確」であるからです。
右：勝ち確。適切な手を打つと相手の番で負け確、すなわち自分は勝ち確
この作業をn=3,4…と続けることによって全てのパターンが「勝ち確」と「負け確」に分類されることがわかります。
ちなみに、この方法は「数学的帰納法」と呼ばれるもので、ちゃんとした証明は以下のようになります。
命題を
「まだ消されていない棒(丸)がn個あるとき、それは「勝ち確」か「負け確」のいずれかである。(nは非負整数)」
とし、それを考える。
n=0のとき、勝利である。すなわち「勝ち確」となり命題は真。
n≦kのとき、命題が満たされていると仮定する。
n=k+1のときを考える。
n=k+1から棒(丸)を消すと必ずn≦kとなり、「勝ち確」と「負け確」のいずれかになる。
この消し方をすべて考え、消したあとが全て「勝ち確」であるとき、全ての消し方で相手が「勝ち確」になり、元のパターンは「負け確」である。
消したあとのパターンに少なくとも1つ「負け確」があるとき、その手を選べば相手が負けになるので元のパターンは勝ち確になることが分かる。
よってn=k+1のの時も命題は真
従って任意のnに対して上の命題は示された。
必勝法を求める
この証明の仕方を見て頂ければわかると思いますが、実際の必勝法を調べるには、全パターンを調べる必要があり、nが小さいときならまだしも、n=16くらいになると人の手でやるのはめちゃくちゃ大変です。
ということで、実際にC++を使って4×4のまるけしで必勝法を求めてみました。
右：負け確の数
これを見ると、n=16で負け確が1個あることがわかります。これより、後攻が適切な手を打てば必ず勝てるという結論になります。
気が向いたらこれについての記事を書こうと思っています。（これをやりたくてVisualStudioをダウンロードした）
オセロに必勝法はあるのか
ここまで読んでいただいた皆さんはおそらく
「他のゲームでも必勝法はあるのでは」と考えると思います。
例えば、オセロの場合を考えて見ます。
オセロに必勝法があるとは言い切れません。
理由は単純で、上で挙げた「棒消し」や「まるけし」は勝ち負けが必ず決まりますが、オセロは引き分けがあるからです。
しかし先攻、後攻のどちらが「必ず負けない手」＝「引き分け」を打つのは可能であると考えられます。
そして、オセロには白と黒の区別が重要となるため、上のゲームと比べ必勝法を求めるのは比較にならないほど大変です。
実際にこれを求めた人がいるらしく
結論は「双方が最善手を打つと引き分けになる」らしいです。
すなわち、必勝法はないといえるでしょう。
オセロと比較にならないほど求めるのが大変なものは将棋です。
これまで挙げたゲームと異なり将棋は自由度が高く、相手から取ったコマを使えるため、パターン数が無数になるからです。
これは未だに必勝法の有無はわかっていないらしいです。
まとめ
いかがでしたか。
小学生の頃にやっていたゲームも真面目に考えてみると案外奥深いですし、任意の形で必勝法があるのも面白いですね。
この議論を思いついたとき「自分天才かも！」と思ったのですが、よく考えてみるとおそらく多くの人がゲームをするとき同じ思考プロセスをたどっているのではないかと思います。
人間の頭って結構すごいなーって思ってます。
この記事が気に入ったらサポートをしてみませんか？