Zermeloの定理(ゲーム理論)(Zermelo's theorem)とは、2 人が相手の手をすべて見ながら指す、偶然の要素のない有限のゲームで、結果が先手の勝ち・後手の勝ち・引き分けのどれかであるとき、先手が必勝の戦略をもつ、後手が必勝の戦略をもつ、両者とも引き分け以上を確保できる、のちょうど 1 つが成り立つという定理である。終局から逆にたどる値の計算で示され、結果が実数の 2 人ゼロ和の場合には純粋戦略で最大最小と最小最大が一致する。定理はどの場合かを教えないが、戦略盗用の論法で Chomp と Hex は先手必勝と分かる。集合論の整列可能定理とは別の定理である。
Zermeloの定理(Zermelo's theorem)は、2 人が交互に(一般には決まった順で)手を指し、相手の手をすべて見ている有限のゲームで、結果が「I の勝ち」「II の勝ち」「引き分け」のどれかであるものについて、次の 3 つのうちちょうど 1 つが成り立つ、という定理である。
2 人の有限完全情報ゲーム は、根 $r$ をもつ有限の根付き木 $T$ と、終局(子をもたない頂点)でない各局面 $v$ に手番の参加者 $\iota(v)\in\{\mathrm I,\mathrm{II}\}$ を対応させる写像 $\iota$ と、終局の集合 $Z$ 上の関数 $f\colon Z\to\mathbb R$ からなる。$f(z)$ は終局 $z$ で II から I に支払われる額で、I は $f$ を大きく、II は小さくしたい(2 人ゼロ和)。$f$ の値が $1,0,-1$ だけのとき、それぞれ I の勝ち、引き分け、II の勝ちと読み、勝敗のゲーム という。
局面 $v$ の子の集合を $C(v)$ と書く。I の 戦略 $\sigma$ は、$\iota(v)=\mathrm I$ の各局面 $v$ に子 $\sigma(v)\in C(v)$ を対応させる写像で、II の戦略 $\tau$ も同様である。局面 $v$ から $\sigma,\tau$ に従って進んで着く終局を $z_{\sigma,\tau}(v)$ とし、$f(\sigma,\tau\mid v):=f(z_{\sigma,\tau}(v))$、$f(\sigma,\tau):=f(\sigma,\tau\mid r)$ とおく。
勝敗のゲームで、
この記事の結果が使える条件は次のとおりである。
(i) 2 人ゼロ和:参加者は 2 人で、一方の得は他方の損である。
(ii) 完全情報で偶然の手番がない:手番の参加者は、それまでの手をすべて見ている。くじやさいころの手番はない。
(iii) 有限:局面は有限個である。局面の集合が有限で同じ局面に戻れないゲームは、この形に書き直せる(KP17 Lemma 1.2.3、p. 21)。チェスは、局面の繰り返しで引き分けにする規則によってこの条件を満たす(同 p. 21)。
ゲームが「局面」と「手番」の組の上の有向グラフで与えられる場合は、局面への道筋を頂点とする木に直して考える。こうすると戦略は道筋全体に依存してよいことになるが、thm-zt-value の証明で作る戦略は、その時点の局面だけで決まる。
局面 $v$ の 高さ $h(v)$ を、$v$ から終局までの道筋の辺の数の最大値とする。終局の高さは $0$ である。
def-zt-game のゲームで、局面の値 $W$ を高さの小さい順に
$$
W(z)=f(z)\quad(z\in Z),\qquad
W(v)=\begin{cases}\max_{c\in C(v)}W(c)&(\iota(v)=\mathrm I),\\ \min_{c\in C(v)}W(c)&(\iota(v)=\mathrm{II})\end{cases}
$$
で定める。I の局面 $v$ では $W(c)=W(v)$ となる子 $c$ を 1 つ選んで $\sigma^\ast(v)$ とし、II の局面でも同様に $\tau^\ast(v)$ を選ぶ。このとき、I と II のすべての戦略 $\sigma,\tau$ について
$$
f(\sigma,\tau^\ast)\le W(r)\le f(\sigma^\ast,\tau)
$$
が成り立つ。とくに
$$
\max_\sigma\min_\tau f(\sigma,\tau)=\min_\tau\max_\sigma f(\sigma,\tau)=W(r)
$$
であり、この値を純粋戦略で達成する戦略の組 $(\sigma^\ast,\tau^\ast)$ がある。
一般の有限 2 人ゼロ和ゲームでは、最大最小と最小最大の一致には混合戦略が要る(von Neumannのミニマックス定理)。完全情報なら純粋戦略で足りる、というのがこの定理の内容である。
すべての局面 $v$ と、すべての $\sigma,\tau$ について
$$
f(\sigma,\tau^\ast\mid v)\le W(v)\le f(\sigma^\ast,\tau\mid v)
$$
を、$h(v)$ についての帰納法で示す。終局 $v$ では 3 つの量はどれも $f(v)$ で等しい。
$h(v)\ge1$ とし、$v$ の子(高さは $h(v)$ より小さい)では主張が成り立つとする。
$\iota(v)=\mathrm I$ のとき。 $c^\ast=\sigma^\ast(v)$ とおくと $W(c^\ast)=W(v)$ である。$v$ から $(\sigma^\ast,\tau)$ に従うと最初に $c^\ast$ へ進むので、帰納法の仮定より
$$
f(\sigma^\ast,\tau\mid v)=f(\sigma^\ast,\tau\mid c^\ast)\ge W(c^\ast)=W(v).
$$
また $(\sigma,\tau^\ast)$ に従うと最初に $c=\sigma(v)$ へ進むので
$$
f(\sigma,\tau^\ast\mid v)=f(\sigma,\tau^\ast\mid c)\le W(c)\le\max_{c'\in C(v)}W(c')=W(v).
$$
$\iota(v)=\mathrm{II}$ のとき。 I と II、$\max$ と $\min$、不等号の向きを入れ替えて同じ議論をする。$c^\ast=\tau^\ast(v)$ とすると $f(\sigma,\tau^\ast\mid v)=f(\sigma,\tau^\ast\mid c^\ast)\le W(c^\ast)=W(v)$、$c=\tau(v)$ とすると $f(\sigma^\ast,\tau\mid v)=f(\sigma^\ast,\tau\mid c)\ge W(c)\ge\min_{c'}W(c')=W(v)$ である。
$v=r$ とすれば最初の主張を得る。次に、すべての $\sigma$ で $\min_\tau f(\sigma,\tau)\le f(\sigma,\tau^\ast)\le W(r)$、かつ $\min_\tau f(\sigma^\ast,\tau)\ge W(r)$ なので、$\max_\sigma\min_\tau f=W(r)$ で $\sigma^\ast$ で達成される。最小最大も同様である(戦略は有限個なので最大・最小は存在する)。$\square$
勝敗のゲーム(def-zt-game)では、次の 3 つのうちちょうど 1 つが成り立つ。
少なくとも 1 つ。 thm-zt-value より、すべての $\sigma,\tau$ で $f(\sigma,\tau^\ast)\le W(r)\le f(\sigma^\ast,\tau)$ である。$W(r)$ は終局の値のどれかなので $1,0,-1$ のどれかである。$W(r)=1$ なら、すべての $\tau$ で $f(\sigma^\ast,\tau)\ge1$、すなわち $=1$ で、$\sigma^\ast$ は I の必勝戦略である。$W(r)=-1$ なら同様に $\tau^\ast$ は II の必勝戦略である。$W(r)=0$ なら、$\sigma^\ast$ はすべての $\tau$ で $f\ge0$、$\tau^\ast$ はすべての $\sigma$ で $f\le0$ を与え、3 が成り立つ。
高々 1 つ。 I の戦略 $\sigma$ と II の戦略 $\tau$ をぶつけると、結果 $f(\sigma,\tau)$ はただ 1 つに決まる。1 と 2 が同時に成り立てば、それぞれの必勝戦略をぶつけた結果が $1$ と $-1$ の両方になり矛盾する。1 と 3 が同時に成り立てば、I の必勝戦略と II の引き分け以上を確保する戦略をぶつけた結果が $=1$ かつ $\le0$ となり矛盾する。2 と 3 も同様である。$\square$
引き分けのない勝敗のゲームでは 3 は「両者とも必勝」となって起こりえないので、どちらか一方が必勝の戦略をもつ。これは KP17 Theorem 1.2.2(p. 21)の主張にあたり、そこでは必勝の戦略がその時点の局面だけで決まるものにとれることも述べられている(証明は演習 1.b)。thm-zt-value の $\sigma^\ast$ はこの性質をもつ。
手番の参加者が 3 人以上の場合や、ゼロ和でない場合の一般化は 部分ゲーム完全均衡 にある。そこでは各局面で手番の参加者が自分の利得を最大にし、$W$ は利得の組になる。
Zermelo の定理は 3 つの場合のどれが起きるかを言わない。ゲームが対称で、余分な手が害にならないときは、「後手に必勝法があれば先手がそれを盗める」という論法で、後手必勝と引き分けを否定できる。これを 戦略盗用 という。
$m\times n$ の格子の升 $(i,j)$($1\le i\le m$、$1\le j\le n$)のうち $(1,1)$ を除いたものを板とする。2 人が交互に、残っている升 $(i,j)$ を 1 つ選び、$i'\ge i$ かつ $j'\ge j$ の升 $(i',j')$ をすべて取り除く。最後の升を取った人の勝ちとする。$mn>1$ なら先手が必勝の戦略をもつ(KP17 Theorem 1.1.7、p. 15)。
残りの升の集合が局面で、局面は有限個、手を指すたびに升は減るので、Chomp は引き分けのない有限の完全情報ゲームである。どの局面も、thm-zt-main を「その局面から始めるゲーム」に当てはめると、手番の人が必勝の 勝ち局面 か、手番でない人が必勝の 負け局面 かのどちらかである。升が残っていない局面は負け局面である。勝ち局面からは負け局面への手があり、負け局面からの手はすべて勝ち局面へ行く(thm-zt-value の値の再帰そのものである)。
板全体を $R$ とし、$R$ から右上の升 $(m,n)$ だけを取り除いた局面を $R^-$ とする。$mn>1$ なので $(m,n)\ne(1,1)$ で、$(m,n)$ は $R$ の升である。
証明は先手必勝の戦略の存在を示すだけで、どの升を選べばよいかは教えない。$2\times3$ では右上を取るのが勝つ手だが、$3\times3$ ではそうでない(KP17 p. 16)。
$n\ge1$ とし、升 $(i,j)$($1\le i,j\le n$)を、$(i,j)$ と $(i\pm1,j)$、$(i,j\pm1)$、$(i+1,j-1)$、$(i-1,j+1)$ が隣り合う形に並べた菱形の盤を考える(六角形の升を敷き詰めた盤)。I と II は交互に(I が先に)空いている升を自分の色で塗る。I の色の升の隣り合う列で $i=1$ の升と $i=n$ の升を結ぶものを I の横断、II の色の升の列で $j=1$ と $j=n$ を結ぶものを II の横断 という。盤上に横断ができた時点で、その横断の持ち主の勝ちとしてゲームを終える。
$n\times n$ の Hex では、先手 I が必勝の戦略をもつ(KP17 Theorem 1.2.5、p. 22)。
証明には次の事実を使う:すべての升が塗られた盤には、少なくとも一方の横断がある(Hex の定理。KP17 Theorem 1.2.6(p. 23)が、盤の縁を色付きの境界とみなした形で証明している)。この記事ではこの事実を証明せずに使う。
ゲームは引き分けなしの有限ゲームである。 1 手ごとに空いている升が 1 つ減るので、ゲームは $n^2$ 手以内で終わる。盤が全部塗られる前に横断ができていなくても、全部塗られた時点で Hex の定理により横断がある。新しく横断ができるのは直前に塗った人の色だけなので、勝者はちょうど 1 人に決まる。よって thm-zt-main から、I か II の一方が必勝の戦略をもつ。
II が必勝なら I も必勝。 II に必勝の戦略 $\tau$ があるとする。写像 $\varphi(i,j)=(j,i)$ は隣り合う関係を保ち(ずれの集合 $\{(\pm1,0),(0,\pm1),(1,-1),(-1,1)\}$ は成分の入れ替えで変わらない)、I の横断を II の横断に、II の横断を I の横断に移す。そこで盤を $\varphi$ で折り返し、色を入れ替えて読めば、「II が先に塗り、I が後に塗る」Hex は通常の Hex と同じゲームになり、$\tau$ を移した戦略 $\tau'$ は、このゲームで後手の I の必勝戦略になる。
I は次のように指す。最初に任意の升 $e$ を塗る。以後 I は、実際の盤から 1 つの I の石(余分な石、最初は $e$)を除いた盤を 想像の盤 とし、想像の盤の上で II を先手、自分を後手として $\tau'$ に従う。$\tau'$ が指示する升が空いていればそこを塗る。指示する升が余分な石の升なら、実際の盤の別の空いている升を塗り、それを新しい余分な石とする(想像の盤ではその指示どおり塗ったことになる)。
このとき、次の不変量が保たれる:想像の盤の II の石は実際の盤の II の石と同じで、想像の盤の I の石は実際の盤の I の石から余分な石を除いたものである。II の実際の手は実際の盤で空いている升なので、想像の盤でも空いており、想像の盤の手として正しい。余分な石の升を指示されたとき、ほかに空いている升がなければ実際の盤は全部塗られており、ゲームはすでに終わっている。
$\tau'$ は想像の盤での必勝戦略なので、想像の盤では II の横断ができる前に I の横断ができる。II の石は両方の盤で同じなので、想像の盤の手順が続く間、実際の盤にも II の横断はない。想像の盤に I の横断ができた時点で、実際の盤の I の石はそれを含むので、実際の盤にも I の横断がある(それ以前に実際の盤で I の横断ができて終わっていてもよい)。よって I が勝ち、この指し方は I の必勝戦略である。
矛盾。 I と II の必勝戦略をぶつけると両者が勝つことになり、thm-zt-main の「高々 1 つ」に反する。よって II は必勝の戦略をもたず、I が必勝の戦略をもつ。$\square$
証明が使ったのは、(a) 引き分けがないこと、(b) 先手と後手を入れ替える盤の対称性 $\varphi$、(c) 自分の石が 1 つ多くても損をしないこと、の 3 つである。(c) が成り立たないゲームでは、この論法は使えない(反例の表の 4 行目)。
$3\times3$ の升に 2 人が交互に(I が先に)自分の印を書き、縦・横・斜めのいずれかの 3 升を先にそろえた人の勝ち、全部埋まってそろわなければ引き分けとする。手は高々 9 回なので有限の勝敗のゲームで、thm-zt-main の 3 つのどれかが成り立つ。
開始の局面から到達できる局面(空の盤を含む)は 5478 個あり、それぞれの値 $W$ を後ろ向きに計算すると、根の値は $W(r)=0$ である。すなわち 3 の「両者とも引き分け以上を確保できる」が成り立つ。
局面を「盤の印の配置」で同一視すると(手順が違っても同じ配置なら同じ局面)、到達できる局面は 5478 個、そのうち終局は 958 個(I の勝ち 626、II の勝ち 316、引き分け 16)である。値を高さの小さい順に計算すると、初手 9 通りの行き先の値はどれも $0$ である。値の計算は局面だけで決まるので、木に展開しなくても配置の上で再帰すれば足りる。
$x$ 個の石の山から、2 人が交互に 1 個から 4 個を取り、最後の石を取った人の勝ちとする(KP17 Example 1.1.1、p. 13)。局面は残りの個数 $x$ だけで決まる。値の再帰により、$x$ が 5 の倍数の局面が負け局面(手番の人が負ける)、それ以外が勝ち局面である。実際、$x=0$ は負け局面で、$x\not\equiv0\pmod5$ なら $x\bmod5$ 個取って 5 の倍数の局面に移れ、5 の倍数の局面からは 1〜4 個取るとどれも 5 の倍数でない局面に移る。よって $x=5$ から始めると後手が必勝である。同じ種類の、山を複数もつゲームは 石取りゲームと必勝法 と Nim にある。
(iii) の有限性は、次のように弱めたり外したりできる。
| 外す条件 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 完全情報((ii)) | I と II が互いの選択を見ずに表か裏を選び、一致なら I の勝ち、不一致なら II の勝ち | 3 つのうち 1 つが成り立つこと(thm-zt-main) |
| 偶然の手番がない((ii)) | 公平な硬貨を 1 回投げ、表なら I の勝ち、裏なら II の勝ち | 3 つのうち 1 つが成り立つこと |
| 有限((iii)) | 選択公理のもとで作る、決定されない無限ゲーム(決定性公理) | 3 つのうち 1 つが成り立つこと |
| 余分な手が害にならないこと(戦略盗用の (c)) | ex-zt-subtraction で $x=5$ | 先手が必勝であること(prop-zt-chomp、thm-zt-hex の型の結論) |
確かめを順に書く。どの例も引き分けがないので、3 は「両者とも必勝」と同じで起こらない。
1 行目:I が表を選ぶ戦略には、II が裏を選ぶ戦略が勝ち、I が裏を選ぶ戦略には II の表が勝つので、I は必勝の戦略をもたない。同様に II も必勝の戦略をもたない。よって 1、2、3 のどれも成り立たない。このゲームは手番の順に並べても、II は I の手を見ないので (ii) を満たさない。
2 行目:参加者の手番がなく、戦略は 1 つずつしかない。どちらの戦略の組でも、勝つ確率は $\frac12$ で、どちらも勝ちを確実にはできない。1、2、3 のどれも成り立たない。
3 行目:勝利集合を選択公理で作ると、I と II のどの戦略にも、それを負かす相手のプレイがある。引き分けはないので、1、2、3 のどれも成り立たない。
4 行目:ex-zt-subtraction より $x=5$ は負け局面で、先手は必勝の戦略をもたない(後手が必勝)。手番を 1 回多く使うことが不利になりうるゲームである。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 定理は必勝の手を教える | 存在を言うだけ。手を知るには値の計算が要る | prop-zt-chomp の後の注意 |
| チェスは先手必勝である | 定理は 3 つの場合のどれかと言うだけ | thm-zt-main |
| 対称なゲームは先手必勝である | 余分な手が害にならないことも要る | ex-zt-subtraction |
| 有限ゲームなら一般に純粋戦略で値がある | 完全情報が要る。同時手番では混合戦略が要る | 反例の表の 1 行目、von Neumannのミニマックス定理 |
| 「Zermelo の定理」は整列可能定理を指す | ゲームの文脈ではこの記事の定理を指す | Zermeloの整列定理 とは別 |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する