二人零和有限確定完全情報ゲーム

https://youtu.be/2AXEur7pe_s

Claude Opus 4.6.icon

ツェルメロの定理（Zermelo's theorem, 1913）によって、このクラスのゲームには必ず「先手必勝」「後手必勝」「引き分け」のいずれか一つが決定されていることが証明されています。

核心は後ろ向き帰納法（backward induction）です。

ゲーム木が有限なので、まず末端（葉ノード）から考えます。葉では勝敗や引き分けが確定しています。そこから一手前のノードに遡ると、そのノードの手番プレイヤーは子ノードの結果をすべて見て、自分にとって最も有利な結果をもたらす手を選べます。この「最善の選択」を再帰的に根ノードまで繰り返すと、ゲーム開始時点での結果が一意に定まります。

もう少し丁寧に言うと、有限ゲーム木には最大深さが存在するので、深さの大きい方から数学的帰納法を回せます。深さ d のすべてのノードで結果が確定していれば、深さ d-1 のノードでも手番プレイヤーが最善選択できるので結果が確定する、という帰納ステップが成立します。有限性が保証されているからこそこの帰納が止まり、根まで到達できるわけです。

ポイントは「完全情報」と「有限性」の二つの仮定が両方必要なところです。不完全情報だと相手の手が見えないので「子ノードの結果を見て最善を選ぶ」という操作自体が成立しません。無限だと帰納の基底（葉）がそもそも保証されません。

つまり、両プレイヤーが最善手を打ち続けた場合の結果は、ゲーム開始前から理論上は確定しているということです。ゲーム木（game tree）が有限であることと、完全情報（両者がすべての局面を観察できる）であることから、後ろ向き帰納法（backward induction）で各ノードの最適戦略を葉から根へ遡って決定できます。

具体例を挙げると、チェッカーは2007年にSchinaelによって完全解析され、双方最善で引き分けになることが証明されました。三目並べも同様に引き分け。一方、四目並べ（Connect Four）は先手必勝であることが解かれています。