n目並べ

その他

小学生の頃、マルバツゲームというものに熱中しました。
これは、縦 3 マス横 3 マスの盤面の中に順番にマルとバツを書き入れていき、最初に縦か横か斜めに自分の記号を並べた方が勝ち、というものです。

熱中したイガ（ラシ）少年は、何度もやっているうちに、どうも先手が有利で、双方ともに最善の手を尽くせば引き分けになるようだ、ということが分かってきました。
そこで、確かにその通りだということを実際に証明して見せたのが小学校六年生の頃。
たくさんのパターンをおうちに持って帰るはずの連絡プリントの裏に書き出したのは、今となっては良い思い出です。
（実際には膨大なパターンがありますが、回転や裏返しで同じになるものを同一視すると、意外と少ないパターン数で済みます。）

マルバツゲームは三つ並べると勝ちですが、五つ並べると勝ちと言えば、五目並べですね。
実は、五目並べは先手必勝であることが、明治時代には既に判明していたそうです。すごいですねぇ。

ここまで来ると、次の問題が起こります。
一般に、n 目並べで先手と後手のどちらが必勝なのか、もしくはどちらにも必勝法がないかを判定する簡明な手続きはあるか？
ただし、今は盤面の大きさについて何の条件も仮定していないので、これだけでは一般論は語れません。
そこで、盤面の大きさを m × n、勝ちになる石の並びの個数を k としたときに、これを m,n,k-ゲームと呼ぶことにし、これについて考えてみましょう。
[参考：Wikipedia]
以下、ほとんど全て Wikipedia からの抜粋です。
まず、後手には必勝法が存在しないことが、次のように考えると分かります。


後手に必勝法が存在すると仮定し、後手は必勝法に沿って石を置いていくものとする。
先手は始めに適当な場所に石を置き、2度目のターンで、1度目のターンに後手が置いた石に対して後手の必勝法を実行する。
その際、既に自分の石が置かれた場所に石を置くことが必勝法として要求された場合には、どこか適当な場所に石を置くことにする。
このようにしても、自分が不利になることは決してない（必勝法で想定される盤面のどこかに自分の石を一つ置いた状況になるため）。
かくして、先手に必勝法が存在することになるが、これは後手に必勝法が存在するという仮定に矛盾する。

というわけで、m,n,k-ゲームは先手必勝であるか、双方ともに最善の手を尽くせば引き分けになる、ということが証明されました。
これは、盤面の大きさが無限の場合も同様です。
すると、次なる問題は、個別の m, n, k の値に対して、先手必勝かどうかを判別することですね。
Wikipedia によると、次のような結果が知られています。


※先手に対して考えます。
※また、盤面の大きさが無限の場合の引き分けとは、いつまでも決着が着かないことを意味します。
k=1 or k=2 or k=3:
　盤面が充分に大きいとき→必勝
　盤面が小さいとき→引き分け
k=8:
　盤面が無限→必勝
k≧9:
　引き分け（盤面の大きさは関係ない）

他にも個別の結果はいくつも得られているようですが、解決されていない問題もあるようです。
例えば、盤面の大きさが無限で k=6 or k=7 のとき、必勝か引き分けかは分かっていないとか。
なかなか難しい問題のようです。

余談ですが、盤面の大きさが無限というと、自分としては集合論における決定性の公理を連想せずにはいられません。
ごくごく簡単な無限ゲームについての問題で、選択公理を仮定した場合と決定性の公理を仮定した場合とで結果が異なるようなものは何か知られているのでしょうか。
意図的に作るのも面白いかもしれません（決定性の公理は可算選択公理と矛盾しないから無理かも）。