04. 引き分けがないゲームには必勝法がある? -ツェルメロの定理-

以下では, 2人ゲームで全ての情報が共有されているゲームには, 必勝手順が必ずあることを示しましょう.

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

 

以下ではこのゲームを例にとって, ゲームの考え方について学びます. このゲームの進行について場合分けを行って考えてみましょう.

まず最初, 先手のプレイヤーは9個のマスのうちどこかに○を書きます. どこに書いたかで, 9通りの場合分けがあります. それぞれについて, 後手は残った8個のマスのうちどこかに×を書きます. これについてもどこに書いたかで8通りの場合分けがあります. これを表にしたものが図1です.

図1: 三目並べのゲームの木.

図1: 三目並べのゲームの木.

さらに3手目, 4手目について場合分けすることによって最初の盤面から枝分かれしてゆく図を書くことができます. ゲームが終了している盤面(先手または後手の勝利が確定した盤面) については, そこでゲームは終了しますので, 場合分けも終了します. このようにして描いた図2はゲームの木と呼ばれます. ただし図2は三目並べのゲームの木の一部分を書いたものです.

図2: 三目並べのゲームの木(一部省略).

図2: 三目並べのゲームの木(一部省略).

以下ではゲームの木を詳細に定義しましょう. ただし, 以下で考えるゲームは(三目並べとは異なり) 引き分けが無いゲームとします. またプレイヤーは2人で, とりあえず先手と後手という名前で呼ぶことにします. まず各盤面を小さな黒丸で表し, これを頂点と呼びます. また, 盤面A′ が盤面A から1手打って得られるとき, A に対応する頂点とA′ に対応する頂点の間に線分を引いて, これをと呼びます. 最初の盤面に対応する頂点をと呼びます. 盤面A′ が盤面A から1手打って得られるとき, A に対応する頂点vA は, A′ に対応する頂点vA′ の親と呼び, 逆にvA′ はvA の子と呼びます. 子を持たない頂点は, ゲームが終了した盤面に対応しますが, これは特別にと呼びます. 葉の頂点には, それが先手勝ち(後手負け) の盤面に対応するならばWというラベルを付け, 後手勝ち(先手負け) の盤面に対応するならばLというラベルを付けます. 葉以外の頂点については, 対応する盤面において次の手番のプレイヤー(次に印を書き込むプレイヤー) の名前をラベルとして書き込みます(図3参照).

図3: 一般的なゲームの木の例.

図3: 一般的なゲームの木の例.

例えば三目並べのゲームの木では, 根の頂点には先手のプレイヤーのラベルIを付け, 根の子となっている頂点には, 後手のプレイヤーのラベルIIを付けます. 三目並べは, 最大でも9手でゲームが終了しますので, 根からスタートして, 子の頂点へ, さらにその子の頂点へと辿っていっても, 高々9個で葉の頂点へ辿りつきます.

このようなゲームの木として表現できるゲームは沢山あります. 例えばオセロは, 同様にしてゲームの木を書くことが出来ます. また, オセロは必ず60手でゲームが終了します. ゲームの木があれば, ゲーム全体を把握することができそうですが, ゲームの木は非常に巨大なものになり易いという問題点があります.

三目並べやオセロのようなゲームからは, 上記のようなゲームの木を作れます. 逆にゲームの木さえあれば(元のゲームが何であったか知らなくても) ゲームを次のようにプレイすることができます. まず1つコマ(例えばコインなど) を用意して, 最初に根の頂点に置きます. そして毎回次のような手順でゲームを進行させます.

 

(1) コマの置いてある頂点x のラベルがIのとき.
先手Iは, x の子のうち1つを選び, そこにコマを進めます.

(2) コマの置いてある頂点x のラベルがIIのとき.
後手IIは, x の子のうち1つを選び, そこにコマを進めます.

(3) コマの置いてある頂点のラベルがWのとき.
先手Iの勝ち(後手IIの負け) となってゲームは終了します.

(4) コマの置いてある頂点のラベルがLのとき.
後手IIの勝ち(先手Iの負け) となってゲームは終了します.

 

ゲームの木で表されるゲームにおいて引き分けがなければ, 実は『先手必勝の手順が存在する』か『後手必勝の手順が存在する』のどちらか(頂度) 一方が必ず成り立ちます. 以下ではこれを示してみましょう.

ゲームの木が与えられたとき, 頂点(x と名前を付ける) で, その子がすべて葉となっているようなものが必ず(少なくとも) 1つ存在します(図4参照).

図4: ゲームの木と頂点x.

図4: ゲームの木と頂点x.

このような頂点x の存在は次のように示せます. ゲームの木において根からの距離が1番遠い頂点をy としましょう(根からy までの距離は, 根からy にたどりつくまでに移動した枝の本数とします). このとき明らかにy は葉となります. 頂点y の親をx とすると, x の子は(y も含めて) すべて葉となります.

ゲームが頂点x に対応する盤面となったとき, 実はすでにゲームの勝敗は次のように決定しています.

 

(i) 頂点x のラベルがIのとき.

(i-a) 頂点x の子の中に,Wのラベルを持つ葉z があるとき.
先手Iはz を選ぶことによって勝利できるので, 実は頂点x において先手Iの勝利が確定します.

(i-b) 頂点x の子は, すべてLのラベルを持つ葉のとき.
先手Iがどの子を選んでも後手IIの勝利となるので, 頂点x において後手IIの勝利が確定します.

 

(ii) 頂点x のラベルがIIのとき.

(ii-a) 頂点x の子の中に,Lのラベルを持つ葉z があるとき.
後手IIはz を選んで勝利できるので, 頂点x において後手IIの勝利が確定します.

(ii-b) 頂点x の子は, すべてWのラベルを持つ葉のとき.
上記(i-b) と同様に, 先手Iの勝利が確定します.

 

上記のように, 頂点x において(2人のプレイヤーが十分注意深くプレイすれば) ゲームの勝敗は確定します.

そこで, ゲームの木から, x の子とそれにつながる枝をすべて消却した, 新しいゲームの木を作りましょう. ただし上記(i-a) または(ii-b)の場合は, 頂点x のラベルをWに換え, (i-b)または(ii-a)場合は頂点x のラベルをLに換えます(図5参照). この操作をゲームの木の縮約と呼びます.

図5: x の子を無くしたゲームの木.

図5: x の子を無くしたゲームの木.

この手続きによって, ゲームの木の頂点の数を1つ以上減らすことができます. すなわち,この手続きを繰り返し適用すれば, 最後は根の頂点1つからなるゲームの木が得られます(図6-8参照).

図6: ゲームの木の縮約.

図6: ゲームの木の縮約.

根の頂点1つからなるゲームの木が得られたとき, 根の頂点のラベルがWならば, もとのゲームには先手Iの必勝手順が存在し, 根の頂点のラベルがLならば, もとのゲームには後手IIの必勝手順が存在したことになります(図9参照).

図7: ゲームの木の縮約.

図7: ゲームの木の縮約.

図8: 1点となったゲームの木. 後手必勝となっている.

図9: 後手II の必勝手順.

図9: 後手II の必勝手順.

 

ゲームの木が与えられたとき, 上記の操作を行うと, 2人のプレイヤーのうちちょうど一方に必勝手順が存在することが分かります. ただし, この性質が成り立つためには, 2人のプレイヤーが, あらかじめゲームの木全体を知っており, またゲーム木は有限個の頂点からなり,すべての葉はWまたはLのラベルを持ち(引き分けがない), 2人のプレイヤーは各時点でゲームの木のどの頂点にいるか(コマが置かれているか) 知っていなければなりません.

 

上記の性質は Zermelo(ツェルメロ)の定理と呼ばれます. この定理より, 例えばオセロには, 『先手の必勝手順』か『後手の必勝手順』のどちらか一方が存在します. しかしながら,どちらが存在しているのか未だ不明です. 将棋や囲碁には, 引き分けが存在するので, 上記の定理をそのまま適用することはできません.

Zermelo の定理は, ゲームの終わり方が先手Iの勝ちか後手IIの勝ちの2通りしかないときのみ成り立ちます. しかし三目並べには引き分けもあります. このようにゲームの終わり方が3通り以上あるときは, どのような性質が成り立つでしょう.

ここで一般的に, ゲームの終わり方がT1, T2, . . . , Tn のn 通りあるゲームを考えましょう.先手IはT1 が最も好ましい終了であり, T2 は2番目に好ましい終了であり, 以下T3 , T4 の順に好ましいとします. Tn は先手Iにとって最悪の終了となっています. これとは逆に, 後手IIはTn が最も好ましい終了であり, Tn−1 は2番目に好ましい終了であり, 以下Tn−2 , Tn−3 の順に好ましいとします. T1 は後手IIにとって最悪の終了となっています.

ゲームの木において, すべての葉にはT1, T2, . . . , Tn のうちどれか1つのラベルが付いているとします. 三目並べのように引き分けがあるゲームは終わり方が(T1, T2, T3) の3種類あり,それぞれ(Iの勝利, 引き分け, IIの勝利) に対応していると考えることができます.

このとき, 以下が成り立ちます. ある番号i*∈ { 1, 2, . . . , n } が存在して以下の2つが同時に満たされる.

 

(1) 先手Iには(後手がどんな手を打っても)T1, T2, . . . , Ti∗ のどれかで終了するような手順が存在する.

(2) 後手IIには(先手がどんな手を打っても) Ti* , Ti*+1, . . . , Tn のどれかで終了するような手順が存在する.

 

この性質より, 双方が上記(1)と(2)の手順を使えば, ゲームはいつもTi*という結果で終了することが分かります.

ではこの性質を示しましょう. 終了状態がT1, . . . , Tn のn 種類ある元のゲームをG と書きます. これに対しn+1 個のゲームG0 ,G1 , . . . ,Gn を次のように定義します. ゲームG0 は, G のすべての葉のラベルをL に換えたゲームです. ゲームGi は, G に対し, { T1, . . . Ti } 中のラベルの付いた葉にはWのラベルを付け, { Ti+1, . . . Tn } 中のラベルの付いた葉にはLのラベルを付けて得られるゲームです. ゲームGn は, G のすべての葉のラベルをWに換えたゲームを意味します.

先に示したことより, G0 , . . . ,Gn のどのゲームも『先手Iに必勝手順が存在する』または『後手IIに必勝手順が存在する』のどちらか(頂度) 一方のみが成り立ちます. また定義より明らかにG0 には『後手IIの必勝手順が存在』しており, Gn には『先手Iの必勝手順が存在』しています. ここでG1 , . . . ,Gn のうち『後手IIの必勝手順が存在』するゲームで添字の番号が最大のものをGi′ としましょう.

このときi* = i′ + 1 とおくと, 性質(1)(2)を満たすことを示します.

 

(1) ゲームGi*−1 = Gi′ には『後手IIの必勝手順が存在する』ので, 後手IIには, (先手Iがどんな手を打っても) { Ti* , Ti*+1, Ti*+2, . . . , Tn } のどれかで終了する手順が存在します.

(2) 添字i′ の最大性より, ゲームGi*= Gi′+1 には『後手IIの必勝手順が存在しない』ので, Zermelo の定理よりGi*には『先手Iの必勝手順が存在』します. すなわち先手Iには,(後手IIがどんな手を打っても) T1, T2, . . . , Ti*のどれかで終了する手順が存在します.

 

上記の Zermelo の定理が適用できるのは, 正確には『二人ゼロ和有限確定完全情報ゲーム』と呼ばれるタイプのゲームに限りますが, 説明にかなりの紙数を要するので, ここでは詳しい説明は避けます.

実際のボードゲームに Zermelo の定理を適用できるかを考えると, 有限で終わるか,あるいは引き分けはどのように定義されているか,が問題になることが多いようです.

例えばチェッカーは有限で終わるゲームで引き分けが存在します. 2007 に初めて, 双方のプレイヤーが注意深く打てば引き分けになることが確認されました.(1)

オセロも有限で終わるゲームで, 引き分けが存在します. 現時点で 6 × 6 の盤については後手に必勝法があることが Joel Feinstein によって確認されています. 通常使われている 8× 8 の盤については, 不明です.

将棋は, 現在の公式ルールでは, 同一局面が4回現れた時点で無勝負とされ, 先手・後手を入れ替えて最初から指し直しとなります. しかしながら, このルールにでは勝敗が不明となる局面があることが指摘されているようです.(2)

囲碁は, 同一局面が反復される場合はプレイヤーの同意があれば引き分けになる, というルールが使われることが多いようです.

(1)Checkers Is Solved, Jonathan Schaeffer, Neil Burch, Yngvi Bjornsson, Akihiro Kishimoto, Martin Muller,Robert Lake, Paul Lu, and Steve Sutphen, Science, vol. 317 (2007), no. 5844, pp. 1518-1522.

(2)縫田光司, 詰将棋作品『最後の審判』, 詰将棋パラダイス, 1997年1月号特別出題.