07. 5×5の盤で遊ぶ五目並べ -五目並べ不敗伝説-

三目並べはご存知ですか? 三目並べは 3 × 3 の形に並べられた9個のマスに, 二人のプレイヤーが交互に○と×を書き込むゲームです. ここでは先手が○, 後手が×を書くものとしましょう. 交互に○と×を書いていったとき, 縦横斜めに並んだ3つのマスのどれかに(8通りあります)自分の記号をすべて, 先に書き込んだプレイヤーの勝ちです. とても簡単なゲームで, 誰もが1度は遊んだことがあるでしょう. 世界で最も知られたゲームの1つと言って良いかもしれません. このゲームは, 二人のプレイヤーが十分注意深くプレイすれば, 引き分けになることは, 多くの方は御存知と思います.

以下ではm × m のマス目で遊ぶm 目並べについて考えましょう. 実はm ≧ 3 ならば,m × m のマス目で遊ぶm 目並べは『先手必勝』の手順は存在しません. 以下ではm = 5 の場合をやってみましょう. このときはペアリング戦略と呼ばれる方法が有効です. 5 × 5 のマス目に次のように番号を付けます.

1 3 3 8 2
7 7 12 8 4
6 11 11 4
6 10 12 9 9
2 10 5 5 1

後手は次のような戦略で, 先手の勝利を阻止することができます. 先手がある場所に打ったら, 後手はそこと同じ番号の場所に打ちます. 先手が*の場所に打ったときは, 後手はどこに打ってもかまいません. 先手がある番号の場所に打ち, 同じ番号の場所にすでに後手の石があるときは, 後手はどこに打ってもかまいません. 縦横斜めの勝ち筋12本のどれを見ても同じ数字の対が含まれますので, 後手は先手の勝利を必ず阻止することができます.

このペアリング戦略と数学的帰納法を組み合わせると, 5 以上の任意のm について『先手必勝手順』が存在しないことが導かれます.

m × m のマスで遊ぶm 目並べに, 後手が引き分けに持ち込めるペアリング戦略が存在するとしましょう. このとき(m+ 1) × (m+ 1) のマス目で遊ぶ(m+ 1) 目並べを考えます. 盤の左上のm × m のマス目を切り取り, この中では後手はm 目並べをプレイするとしましょう. 仮定より, 後手はこのm 目並べでペアリング戦略を使って先手が勝つことを阻止できます. すると先手が勝利できる可能性は, 最下段の(m+ 1) マスを自分の石で埋めるか, 最右列を自分の石で埋めるか, 右上がりの斜めの対角線を自分の石で埋めるか, の3通りしかありません.

図1: m×mのペアリング戦略.

図1: m×mのペアリング戦略.

しかし上図のようなペアリング戦略を取ることにより, 後手はこの3通りの終了をすべて阻止することができます. ゆえに後手は(m + 1) × (m + 1) のマス目で遊ぶ(m + 1) 目並べにおいて, 先手の勝利を阻止できます.

上記のように数学的帰納法の考え方を用いると, 5 × 5 のマス目で遊ぶ5目並べで, 後手にペアリング戦略があるならば, 5以上のすべてのm について, 後手にはペアリング戦略が存在します.

m = 3, 4 の場合は, このような簡単なペアリング戦略は知られていません.

上記の証明より, 先手必勝の戦略が無いことが分かります. ちなみに, 後手の必勝の戦略もこのゲームにはありません. これは後手に必勝の戦略があったら, それを使って先手が勝てる筈です(これを正確に議論するのは少し大変です). 上記より, どちらにも必勝戦略が無いので, 2人のプレイヤーが十分注意深く打てば, 必ず引き分けに終わります.

この証明において, 後手の戦略は明示されていますが, 先手の『引き分けに持ち込む戦略』は明示されていないことに注意して下さい. すなわち, 先手は十分注意深く打たないと, 負けてしまう可能性がある, ということです.

では次に, n × n マスの盤で遊ぶm 目並べについて考えましょう. 以下ではm ≧ 3 であるとします. 盤が小さければ, 例えばn ≦m ならば, 後手は先手の勝ちを必ず阻止することができます. そのため, 十分大きな盤ならば先手必勝手順が存在するかが次の問題となります.

m = 3, 4, 5 の場合は盤が十分広ければ先手必勝の手順が存在することが知られています.この結果は, 計算機を用いてゲームをシミュレートし, 可能な盤面を適切な知見を元に絞り込んで得られたものです. そのため実際に先手の必勝手順が得られていますが, m = 5 の場合などは, その手順は膨大であり, 残念ながらここに記すことはできません.

m ≧ 8 の場合は, どんなに広い盤においても, 後手は先手の勝利を阻止できることが知られています. 例えばm = 8 の場合は, 単純なペアリング戦略ではなく, 後手の手順は場合分けを用いた複雑なものとなっています. m ≧ 9 の場合は図1 で表される太線の一方のマスに打たれたら, 他方のマスに打つというペアリングの戦略を用いて, 後手は先手の勝利を阻止できます.

m = 6, 7 については, 『十分広い盤ならば先手必勝』なのか, 『どんな広さの盤でも後手は先手の勝利を阻止できる』のか, どちらが成り立つかはまだ解決されていません.

図2: 十分広い盤での9目並べのペアリング戦略.

図2: 十分広い盤での9目並べのペアリング戦略.