7.5 再帰的データ型を使ったゲームの表現

チェス、チェッカー、囲碁、ニムといったゲームは二人完全情報ゲーム (two-person games of perfect information) に分類される。これらのゲームでは二人のプレイヤーが交互に手を打ち、ゲームに関するあらゆる情報が常に二人のプレイヤーに開示されるという意味で「完全情報」である。例えばチェスでは、それぞれのプレイヤーは自身の打つ手を盤上の駒の位置だけから決定する。これに対して、トランプを使うゲームはたいてい完全情報ゲームでない: いずれのプレイヤーも相手の手札を見ることができない場合が多い。

本節では勝敗確定 (win-lose) と呼ばれる種類の二人完全情報ゲームを表す集合 \(\text{WinLoseGm}\) を考える。\(\text{WinLoseGm}\) を再帰的データ型として定義し、この種類のゲームの必勝戦略に関する基礎的な定理を構造的帰納法で証明する。\(\text{WinLoseGm}\) の再帰的定義では「ゲームの任意の時点における状態を新しいゲームの初期状態として扱う」というアイデアが利用される。これはニム (Nim) と呼ばれるゲームを考えると分かりやすく説明できる。

ニムは石がいくつか積まれた山がいくつかある状態から始まる。二人のプレイヤーは「山を一つ選び、そこから \(1\) 個以上の石を取り除く」という操作を交互に行い、最後の石を取り除いたプレイヤーの勝利となる。例えば山が一つしかない状態からニムを開始するとき、先攻のプレイヤーはその山の石を全て取り除くことで勝利できる。

ニムの特定のゲームは開始時点でそれぞれの山に含まれる石の数で定義できる。

例えば、\(i\), \(j\), \(\ldots\) 個の石が積まれた山があるニムのゲームを \(\text{Nim}_{\langle i, j, \ldots \rangle}\) と表すことにする。このとき、ゲーム \(\text{Nim}_{\langle 3,2 \rangle}\) で先攻のプレイヤーに許される操作は \(5\) 通りある: \(3\) 個の石が積まれた山から \(1\), \(2\), \(3\) 個の石を取り除く操作、そして \(2\) 個の石が積まれた山から \(1\), \(2\) 個の石を取り除く操作である。この \(5\) 個の操作のいずれかが終了すると、後攻のプレイヤーから始まる新しいニムのゲームが生まれる:

\[ \begin{aligned} 3 \text{ 個の石が積まれた山から } 1 \text{ 個の石を取り除く:} &\quad \text{Nim}_{\langle 2, 2 \rangle} \\ 3 \text{ 個の石が積まれた山から } 2 \text{ 個の石を取り除く:} &\quad \text{Nim}_{\langle 2, 1 \rangle} \\ 3 \text{ 個の石が積まれた山から } 3 \text{ 個の石を取り除く:} &\quad \text{Nim}_{\langle 2 \rangle} \\ 2 \text{ 個の石が積まれた山から } 1 \text{ 個の石を取り除く:} &\quad \text{Nim}_{\langle 1, 3 \rangle} \\ 2 \text{ 個の石が積まれた山から } 2 \text{ 個の石を取り除く:} &\quad \text{Nim}_{\langle 3 \rangle} \end{aligned} \]

これら \(5\) 個のゲームを\(\text{Nim}_{\langle 3, 2 \rangle}\) の初期操作 (first move) \(\text{Fmv}_{\langle 3, 2 \rangle}\) と呼ぶことにする:

\[ \text{Fmv}_{\langle 3, 2 \rangle} ::= \left\{ \text{Nim}_{\langle 2, 2 \rangle},\ \text{Nim}_{\langle 1, 2 \rangle},\ \text{Nim}_{\langle 2 \rangle},\ \text{Nim}_{\langle 1, 3 \rangle},\ \text{Nim}_{\langle 3 \rangle} \right\} \tag{7.24}\]

このように定めると、先攻のプレイヤーが行う操作「山を一つ選んで、そこから \(1\) 個以上の石を取り除く」を「相手のプレイヤーが先攻となるゲームを初期操作 \(\text{Fmv}_{\langle 3, 2 \rangle}\) の中から一つ選択する」と言い換えることができる。抽象的に言えば、\(\text{Nim}_{\langle 3, 2 \rangle}\) を初期操作として定義できる:

\[ \text{Nim}_{\langle 3, 2 \rangle} ::= \text{Fmv}_{\langle 3, 2 \rangle} \]

これは重要な考え方である: ニムのゲームを使ってニムのゲームを再帰的に定義できる。ベースケースは空集合であり、これは山が残っていないニムのゲームに対応する。このとき「先攻」のプレイヤーは必ず敗北する (可能な操作も存在しない)。

この再帰的な定義を使って \(\text{Nim}_{\langle 3, 2 \rangle}\) を具体的に求めてみよう。式 \(\text{(7.24)}\) に示した初期操作のそれぞれは、\(\text{Nim}_{\langle 3, 2 \rangle}\) と同様にニムのゲームの集合として定義される。最も単純な \(\text{Nim}_{\langle 2 \rangle}\) を考えると、後攻のプレイヤーに可能な操作は二つある: 石を \(1\) 個取って \(\text{Nim}_{\langle 1 \rangle}\) とする操作、そして石を \(2\) 個取って \(\text{Nim}_{\langle \varnothing \rangle}\) とする操作である。よって次が分かる:

\[ \text{Fmv}_{\langle 2 \rangle} = \left\{ \text{Nim}_{\langle 1 \rangle},\ \text{Nim}_{\langle \varnothing \rangle} \right\} \]

後攻のプレイヤーが山を全て取るとき、先攻のプレイヤーに可能な操作は存在しない。つまり次が分かる:

\[ \text{Nim}_{\langle \varnothing \rangle} ::= \text{Fmv}_{\langle \varnothing \rangle} = \varnothing \]

これは後攻のプレイヤーが勝利することを意味する。

一方で、後攻のプレイヤーが石を \(1\) 個しか取らない場合、\(1\) 個の石だけからなる山が一つだけ残ったゲーム \(\text{Nim}_{\langle 1 \rangle}\) が生まれる。このとき先攻のプレイヤーが可能な操作 (\(\text{Fmv}_{\langle 1 \rangle}\) の要素) は一つしか存在しない:

\[ \text{Fmv}_{\langle 1 \rangle} ::= \left\{ \text{Nim}_{\langle \varnothing \rangle} \right\} = \left\{ \varnothing \right\} \]

言い換えれば、先攻のプレイヤーは \(\varnothing\) を選ぶ以外の選択肢を持たない。その後、後攻のプレイヤーに可能な操作は存在しなくなる。

よって抽象的には、\(\text{Nim}_{\langle 2 \rangle}\) は空集合だけが組み合わさった次の集合に等しい:

\[ \text{Nim}_{\langle 2 \rangle} = \left\{ \left\{ \varnothing \right\}, \varnothing \right\} \]

同様の計算を続けると、ニムのゲーム \(\text{Nim}_{\langle 3, 2 \rangle}\) が抽象的には次の純粋集合 (pure set) に等しいと分かる:

\[ \begin{aligned} & \text{Nim}_{\langle 3, 2 \rangle} = \{ \\ & \quad \left\{ \varnothing, \left\{ \varnothing \right\} \right\}, \\ & \quad \left\{ \left\{ \varnothing, \left\{ \varnothing \right\} \right\}, \left\{ \left\{ \varnothing \right\}, \left\{ \left\{ \varnothing \right\} \right\}, \left\{ \varnothing, \left\{ \varnothing \right\} \right\} \right\} \right\}, \\ & \quad \left\{ \varnothing, \left\{ \varnothing \right\}, \left\{ \varnothing, \left\{ \varnothing \right\} \right\} \right\}, \\ & \quad \left\{ \left\{ \varnothing \right\}, \left\{ \left\{ \varnothing \right\} \right\}, \left\{ \varnothing, \left\{ \varnothing \right\} \right\} \right\}, \\ & \quad \left\{ \left\{ \varnothing \right\}, \left\{ \left\{ \varnothing \right\} \right\}, \left\{ \varnothing, \left\{ \varnothing \right\}, \left\{ \varnothing, \left\{ \varnothing \right\} \right\} \right\}, \left\{ \left\{ \varnothing \right\}, \left\{ \left\{ \varnothing \right\} \right\}, \left\{ \varnothing, \left\{ \varnothing \right\} \right\} \right\} \right\} \\ & \} \end{aligned} \]

同じ要領で、ニムの任意のゲームは「一番下の要素」に空集合だけを持つ集合で表せる。この例はニムと純粋集合理論 (pure set theory) の間にある関係を示している。純粋集合理論は第 8.3.3 項と問題 8.42 で触れる。

ところで、\(\text{Nim}_{\langle 3, 2 \rangle}\) において先攻プレイヤーの必勝戦略は \(3\) 個の石が積まれた山から石 \(1\) 個取り除き、後攻のプレイヤーに \(\text{Nim}_{\langle 2, 2 \rangle}\) を残す操作である。なぜなら、同じ数の石が積まれた山が二つあるゲームでは、後攻のプレイヤーは相手と対称的な操作を行うことで必ず勝利できるからである。例えば、先攻のプレイヤーがいずれかの山から \(1\) 個の石を取ったときは、もう一方の山から \(1\) 個の石を取ればよい。この戦略が後攻プレイヤーの必勝戦略である理由を考えてみよ。これをさらに一般化した、ニムの任意のゲームでどちらのプレイヤーが必勝戦略を持つかを判定する見事な手続きが知られている (問題 7.36)。

Nim は「相手に操作の選択肢がない状態にする」という目的が二人のプレイヤーに共通するという点で特別である。一般に、二人ゲームの終了状態には様々な可能性がある ── その一部では先攻のプレイヤーが勝利し、それ以外の状況では先攻のプレイヤーが敗北 (後攻のプレイヤーが勝利) する。この点に注意しつつ、勝敗確定二人完全情報ゲームの形式的な定義を次に示す:

定義 7.5.1

勝敗確定二人完全情報ゲーム (two-person win-lose games of perfect information) を表すクラス \(\text{WinLoseGm}\) は次の規則で再帰的に定義される:

ベースケース: \(\textbf{P1Win}\) と \(\textbf{P2Win}\) は \(\text{WinLoseGm}\) に属する。
構築ケース: \(G\) が \(\text{WinLoseGm}\) の要素の非空集合のとき、\(G\) は \(\text{WinLoseGm}\) に属する。このとき、\(G\) に含まれるそれぞれのゲーム \(M \in G\) を \(G\) の初期操作 (first move) と呼ぶ。

\(\text{WinLoseGm}\) に含まれるゲーム¹の記録 (play) とは、そのゲームから始まって先攻プレイヤーの勝利または敗北で終わる、または結果が出ずに無限に続く操作の列を言う。形式的には次の通りである:

定義

\(G\) を \(\text{WinLoseGm}\) に含まれるゲームとする。\(G\) の記録 (play) と、その記録の結果 (outcome) は次の規則で再帰的に定義される:

ベースケース: \(G = \textbf{P1Win}\) のとき、長さ \(1\) の列 \(\langle \textbf{P1Win} \rangle\) は \(G\) の記録である。この記録の結果は「プレイヤー \(1\) の勝利」である。
ベースケース: \(G = \textbf{P2Win}\) のとき、長さ \(1\) の列 \(\langle \textbf{P2Win} \rangle\) は \(G\) の記録である。この記録の結果は「プレイヤー \(2\) の勝利」である。
構築ケース: \(G\) が \(\text{WinLoseGm}\) の要素の非空集合のとき、\(G\) で始まって何らかのゲーム \(M \in G\) に対する記録 \(P_{M}\) が続く列は \(G\) の記録である。その記録の結果は (もし存在するなら) \(P_{M}\) の結果に等しい。

一部のゲームでは無限に続く記録があり得る。例えばチェスでは「適当な駒を動かして元の位置に戻す」操作を二人のプレイヤーが繰り返せば終了しない記録が得られる²。しかし上記のように定義した \(\text{WinLoseGm}\) では、無限に長い記録は存在できない:

補題 7.5.2

任意のゲーム \(G \in \text{WinLoseGm}\) の任意の記録は結果を持つ。

証明 \(G \in \text{WinLoseGm}\) の定義に関する構造的帰納法で示す。補題 7.5.2 を帰納法の仮定として用いる。

ベースケース: \(G = \textbf{P1Win}\) のとき、\(G\) の記録は \(\langle \textbf{P1Win} \rangle\) の一つしか存在しない。その結果は「プレイヤー \(1\) の勝利」である。

ベースケース: \(G = \textbf{P2Win}\) のとき、\(G\) の記録は \(\langle \textbf{P2Win} \rangle\) の一つしか存在しない。その結果は「プレイヤー \(2\) の勝利」である。

構築ケース: \(G\) が \(\text{WinLoseGm}\) の要素の非空集合で、任意の \(M \in G\) で帰納法の仮定が成り立つと仮定する。\(G\) の任意の記録 \(P_{G}\) は \(G\) で始まって何らかのゲーム \(M \in G\) に対する記録 \(P_{M}\) が続く列である。帰納法の仮定より、この \(P_{M}\) は結果を持つ有限列である。よって \(P_{G}\) にも結果が存在する。 ■

チェッカー、チェス、囲碁、ニムの中で間違いなく勝敗確定と言えるのはニムだけである。他のゲームではタイ・引き分け・ステイルメイト・持碁といった終了状態があり得る。ただ、「勝敗が決まらないときはプレイヤー \(1\) の敗北」などと定めれば勝敗確定ゲームに関する結果をこれらのゲームにも適用できる。

私たちが慣れ親しんでいる様々なゲームにおいて、初期操作は有限個しか存在せず、記録の長さに上限が存在する。しかし、これらの性質が \(\text{WinLoseGm}\) の定義で必要とされない事実は強調に値する。さらに言えば、以降で示す結果と証明で有限性は使われないので、仮定する方がミスリーディングである。

この「ゲームは無限でも構わない」という観察は構造的帰納法が持つ驚くべき能力を示している。例えば補題 7.5.2 の証明からは、ゲームが初期操作を無限に持つ場合でも、全ての記録が結果を持つことが言える。これは「記録の長さに固定された上界が存在する」とは異なる: 例えば、全ての非負整数 \(n\) に対して記録の長さがちょうど \(n\) になるような初期操作を持つゲームが存在しても構わない。そのゲームの記録は全て結果を持つものの、任意の非負整数に等しい長さを持つ記録が存在する。

無限ゲームは情報科学の応用からは少し離れすぎているものの、この事実は集合理論と論理学で重要な役割を果たす。無限の構造に対する命題が気付かないうちに証明されることがあるのが構造的帰納法の素敵な特徴である。

7.5.1 ゲームの戦略

プレイヤーに対する戦略 (strategy) とは、そのプレイヤーが自分の番に何をすべきかを決定する規則を言う。さらに正確に言えば、\(s\) が戦略とは、\(s\) がゲームを受け取ってゲームを返す関数であって、全てのゲーム \(G\) で \(s(G) \in G\) が成り立つことを言う。二人のプレイヤーに対する戦略が与えられれば二人が実行する操作が完全に決定するので、どちらが先攻かを決めればゲームの記録が一意に定まる。

ゲームに関する重要な質問として「必勝戦略は存在するか？」がある。いずれのプレイヤーも「自身の勝利」の結果が保証される戦略を求めている。

7.5.2 勝敗確定二人完全情報ゲームの基礎定理

勝敗確定二人完全情報ゲームの基礎定理は、相手がどんな戦略を用いたとしても勝利が保証される単一の「必勝戦略」が一方のプレイヤーに常に存在すると主張する。

例としてチェスを考えると、この定理が驚くべきことを主張していると分かる。本格的なチェスプレイヤーは自分が採用する戦略を秘密にすることが多い: その知識が相手にとって有利に働くと思っての行動である。つまり自分の戦略が知られると、相手はそれを打ち負かすための戦略を立てられると彼らは警戒している。

しかし上述の基礎定理からは逆のことが分かる。チェスやチェッカーといった任意の「勝ち・負け・引き分け確定」のゲームでは、それを相手に伝えたとしても勝利または引き分けが保証される単一の戦略が理論上は存在する。つまり、次のいずれか一方が成り立つ:

どちらかのプレイヤーに対する、勝利が保証される戦略が存在する。
両プレイヤーに対する、引き分け以上が保証される戦略が存在する。

この基礎定理はゲームに関する深遠な事実を明らかにしているものの、その証明は構造的帰納法を使えば非常に単純である。

定理 7.5.3[勝敗確定二人完全情報ゲームの基礎定理 (fundamental theorem for win-lose games of perfect information)]

任意のゲーム \(G \in \text{WinLoseGm}\) において、一方のプレイヤーに必勝戦略が存在する。

証明 \(\text{WinLoseGm}\) の定義に関する構造的帰納法で示す。ゲーム \(G \in \text{WinLoseGm}\) に関する述語「\(G\) において、どちらかのプレイヤーに必勝戦略が存在する」を帰納法の仮定 \(P(G)\) とする。

ベースケース: \(G = \textbf{P1Win}\) または \(G = \textbf{P2Win}\) のとき、両プレイヤーに可能な戦略は「何もしない」の一つしかない。これに対応する \(G\) の記録の結果は片方のプレイヤーの勝利なので、この戦略は勝利するプレイヤーの必勝戦略である。

構築ケース: \(G\) が \(\text{WinLoseGm}\) の要素の非空集合で、任意の \(M \in G\) で帰納法の仮定 \(P(M)\) が成り立つと仮定する。このとき、任意の \(M \in G\) においてどちらかのプレイヤーに必勝戦略が存在する。プレイヤーには交互に手番が回るので、\(G\) で先攻のプレイヤーは \(M\) で後攻となることに注意する。

ある \(M_{0} \in G\) で後攻のプレイヤーに必勝戦略が存在するなら、\(G\) で先攻のプレイヤーには単純な必勝戦略が存在する: 初期操作として \(M_{0}\) を選び、後は \(M_{0}\) で後攻のプレイヤーの必勝戦略に従えばよい。

これに対して、どの \(M \in G\) にも後攻のプレイヤーに必勝戦略が存在しないなら、全ての \(M \in G\) で先攻のプレイヤーに必勝戦略が存在する。このとき \(G\) で後攻のプレイヤーに単純な必勝戦略が存在する: 先攻のプレイヤーが \(M\) を選択したら、\(M\) の先攻プレイヤーの必勝戦略に従えばよい。 ■

定理 7.5.3 は必勝戦略の存在を保証するものの、その証明からはどちらのプレイヤーが必勝戦略を持つのか一切分からない。問題 4.7 で触れた部分集合テイクアウェイや、チェス、囲碁といった多くの身近なゲームでは、どちらが必勝戦略を持つのかを判定する方法は誰にも分かっていない³。

無限ゲーム [スキップ可]

\(n\) を何らかの正整数として、チェスの \(n\) 連戦を遊ぶとしよう。\(n\) 回のチェスの結果を最終的な結果にする方法を定めれば、これは \(\text{WinLoseGm}\) となる。この \(n\) 連戦の記録の長さには上界が存在する: その具体的な値は、チェスを一度だけ遊ぶときの記録の長さの上界に \(n\) を乗じれば得られる。

では、次に示すチェスのメタ連戦を考えてみよう。このメタ連戦では、最初の操作で任意の正整数 \(n\) を選択し、それからチェスの \(n\) 連戦を行う。このメタ連戦は無限ゲームである ── 最初の操作の選択肢が無限にある。

メタ連戦で選択肢が無限にあるのは最初の操作だけである。ただ、メタ連戦を \(n\) 回行うゲームを考えることができる。その上で、最初の操作としてメタ連戦を行う回数 \(n\) を選択するメタメタ連戦も考えられる...。これらの「メタ」ゲームは奇妙な定義を持つものの、基礎定理は適用できる: これらのゲームのそれぞれで、一方のプレイヤーに必勝戦略が必ず存在する。

英語で「Nim game」はニムを定義するルールを意味することもあれば、特定のゲームの記録を ── かつて有名だった「1961 年の映画 Last Year at Marienbad の三番目のゲーム」のように ── 意味することもある。どちらを意味しているかは文脈から簡単に分かるので、本書では両者を区別しない。 ↩︎
現実のチェストーナメントでは、操作の回数を事前に制限する、同じ盤面が三回以上現れる操作を禁じるといった方法で無限に長い記録が生まれる可能性を排除している。 ↩︎
かつてチェッカーはこのリストに入っていた。しかし、最近になって引き分け以上を保証する戦略の存在が証明された [52]。 ↩︎