組合せゲーム理論
概要
組合せゲーム理論（combinatorial game theory）とは、2 人が交互に打ち、偶然も隠れた情報もなく、有限回で終わり、最後に手を打った者が勝つゲームを、ゲームの和と値によって調べる理論である。Conway の流儀ではゲームを Left と Right の選択肢の集合の組として表し、和・符号反転・大小を帰納的に定める。値の等しいゲームの類は和について可換群をなし、値が $0$ のゲームはちょうど後手が勝つゲームで、これを足しても勝ち負けは変わらない。不偏ゲームは Sprague–Grundy の定理により 1 つの山の Nim と値が等しく、和の勝ち負けは Grundy 数の Nim 和で決まる。
組合せゲーム理論（combinatorial game theory）は、2 人が交互に手を打ち、偶然の要素も隠れた情報もなく、有限回で必ず終わり、最後に手を打った者が勝つゲームを調べる理論である。中心になる考え方は、ゲームの 和（いくつかのゲームを並べ、手番の者がどれか 1 つを選んでそこで 1 手打つゲーム）と、ゲームをその勝ち負けへの寄与だけで同一視した 値 である。
Nim は、2 人の打てる手が同じゲーム（不偏ゲーム）の代表で、その完全な解は Bouton の定理である。囲碁の終盤のように、2 人の打てる手が異なるゲーム（非不偏ゲーム）もある。J. H. Conway は、どちらの場合もゲームを「左の対局者 Left が移れる局面の集合」と「右の対局者 Right が移れる局面の集合」の組として表し、和・符号反転・大小を定義した。この記事では次の 2 つを証明する。
- ゲームの値は、和について アーベル群 をなす。値が $0$ のゲームはちょうど後手が勝つゲームで、値が $0$ のゲームを足しても勝ち負けは変わらない（thm-cgt-group）。
- 不偏ゲームは、ただ 1 つの $n\ge0$ について 1 つの山の Nim $*n$ と等しく、和の値は Nim 和で計算できる（thm-cgt-sprague-grundy、Sprague–Grundy の定理）。
定義
ゲーム を、日ごとに次のように帰納的に定める。
- $0$ 日目に生まれるゲームは $\{\ \mid\ \}$ だけで、これを $0$ と書く。
- $n$ 日目までに生まれたゲームの有限集合 $\mathcal L$、$\mathcal R$ の組を $\{\mathcal L\mid\mathcal R\}$ と書き、$n+1$ 日目までに生まれたゲームという。
ゲーム $G=\{\mathcal L\mid\mathcal R\}$ の $\mathcal L$ の元を $G$ の Left の選択肢、$\mathcal R$ の元を Right の選択肢 といい、代表の文字をそれぞれ $G^L$、$G^R$ と書く（$G=\{G^L\mid G^R\}$）。$G$ が生まれる最小の日を $G$ の 誕生日 $b(G)$ という。$\mathcal L$、$\mathcal R$ がそれぞれ等しいとき、2 つのゲームは 同一 であるといい、$G\equiv H$ と書く。
ゲーム $G$ は局面を表す。Left の手番なら Left は $G$ からどれかの $G^L$ へ移り、Right の手番なら Right はどれかの $G^R$ へ移る。手番の者は必ず手を打たなければならず、打てる手がない者が負けとする（最後に手を打った者の勝ち）。選択肢の誕生日は $b(G)$ より小さいので、どのように打っても $b(G)$ 手以内に終わる。以下の証明は、誕生日（または誕生日の和）についての帰納法で行う。
ゲーム $G$、$H$ の 和 と $G$ の 符号反転 を、誕生日の和についての帰納法で
$$
G+H:=\{G^L+H,\ G+H^L\mid G^R+H,\ G+H^R\},\qquad -G:=\{-G^R\mid-G^L\}
$$
で定める（$G^L$ などは選択肢全体を動く）。$G-H:=G+(-H)$ とおく。
$G+H$ では、手番の者は $G$ か $H$ の一方を選んで、そこで 1 手打つ。$-G$ は Left と Right の役割を入れ替えたゲームである。帰納法により、$G+H\equiv H+G$、$(G+H)+K\equiv G+(H+K)$、$G+0\equiv G$、$-(-G)\equiv G$、$-(G+H)\equiv(-G)+(-H)$ が成り立つ（両辺の選択肢の集合が、帰納法の仮定によりそれぞれ一致する）。和と符号反転の定義は DH09 表 1（p. 6）と同じである。
1 日目までに生まれるゲームは次の 4 つである。
$$
0=\{\ \mid\ \},\qquad1:=\{0\mid\ \},\qquad-1:=\{\ \mid0\},\qquad*:=\{0\mid0\}.
$$
$1$ では Left だけが 1 手打てる。$-1\equiv-(1)$ である。$*$ ではどちらも $0$ へ移れるので、先に打った者が勝つ。2 日目に生まれるゲームには、たとえば $\frac12:=\{0\mid1\}$ がある。
勝ち負けの判定
誕生日についての帰納法で、次のように定める。
- $G\ge0$ とは、どの Right の選択肢 $G^R$ についても $G^R\le0$ でないことである。
- $G\le0$ とは、どの Left の選択肢 $G^L$ についても $G^L\ge0$ でないことである。
$G\le0$ でないことを $G\not\le0$、$G\ge0$ でないことを $G\not\ge0$ と書く。
ゲーム $G$ について次が成り立つ。
- Right が先に打つとき Left が必ず勝てる（勝つ打ち方がある）ことは、$G\ge0$ と同値である。
- Left が先に打つとき Left が必ず勝てることは、$G\not\le0$ と同値である。
Right についても、Left と Right、$\ge$ と $\le$ を入れ替えた主張が成り立つ。とくに、誰が先に打つかを決めると、Left と Right のちょうど一方が必ず勝てる。
誕生日についての帰納法で示す。Right が先に打つとき Left が必ず勝てるのは、Right がどの $G^R$ へ移っても、そこから Left が先に打って必ず勝てるときであり、帰納法の仮定（2）によりそれはすべての $G^R$ が $G^R\not\le0$ を満たすこと、すなわち $G\ge0$ である（$G^R$ がなければ Right は打てずに負け、$G\ge0$ も成り立つ）。Left が先に打って必ず勝てるのは、ある $G^L$ へ移って、そこから Right が先に打つとき Left が必ず勝てるときであり、帰納法の仮定（1）によりそれは $G^L\ge0$ となる $G^L$ があること、すなわち $G\not\le0$ である。Right についても同じである。Left が先に打つとき、Right が必ず勝てることは $G\le0$ と同値、Left が必ず勝てることは $G\not\le0$ と同値なので、ちょうど一方が成り立つ。$\square$
したがって、どのゲームも次の 4 つの 結果の類 のちょうど 1 つに属する。
| 類 | 条件 | 意味 | 例 |
|---|---|---|---|
| $G>0$ | $G\ge0$ かつ $G\not\le0$ | 先手・後手によらず Left が勝つ | $1$、$\frac12$ |
| $G< 0$ | $G\le0$ かつ $G\not\ge0$ | 先手・後手によらず Right が勝つ | $-1$ |
| $G=0$ | $G\ge0$ かつ $G\le0$ | 後手が勝つ | $0$ |
| $G\parallel0$ | $G\not\ge0$ かつ $G\not\le0$ | 先手が勝つ | $*$ |
記号 $G=0$ は、def-cgt-equal で定める「値が等しい」の特別な場合になる。
主定理 1：ゲームの値のなす群
ゲーム $G$、$H$ について次が成り立つ。
- $G\ge0$ かつ $H\ge0$ なら $G+H\ge0$ である。$G\le0$ かつ $H\le0$ なら $G+H\le0$ である。
- $-G\ge0$ と $G\le0$ は同値であり、$-G\le0$ と $G\ge0$ は同値である。
- $G-G\ge0$ かつ $G-G\le0$ である。
要点：1 は、相手が一方の成分で打ったら同じ成分で勝つ手を返す、という戦略を帰納法で書いたものである。3 は、相手が一方の成分で打ったら、もう一方の成分で同じ手を写して打つ戦略である。
詳しい証明を開く
1：$b(G)+b(H)$ についての帰納法で前半を示す。$G+H$ の Right の選択肢 $G^R+H$ を考える。$G\ge0$ なので $G^R\not\le0$ であり、定義から $G^{RL}\ge0$ となる $G^R$ の Left の選択肢 $G^{RL}$ がある。帰納法の仮定から $G^{RL}+H\ge0$ で、これは $G^R+H$ の Left の選択肢なので $G^R+H\not\le0$ である。Right の選択肢 $G+H^R$ についても同じである。よって $G+H\ge0$ である。後半も同様である。
2：$-G$ の Right の選択肢は $-G^L$ なので、帰納法の仮定から「$-G\ge0$ ⇔ どの $-G^L$ も $\le0$ でない ⇔ どの $G^L$ も $\ge0$ でない ⇔ $G\le0$」である。後半も同様である。
3：$b(G)$ についての帰納法で $G-G\ge0$ を示す。$G-G$ の Right の選択肢は $G^R-G$ と $G+(-G)^R=G-G^L$ である。$G^R-G$ は Left の選択肢 $G^R+(-G^R)=G^R-G^R$ をもち（$-G$ の Left の選択肢は $-G^R$）、帰納法の仮定からこれは $\ge0$ なので、$G^R-G\not\le0$ である。$G-G^L$ は Left の選択肢 $G^L-G^L\ge0$ をもつので、$G-G^L\not\le0$ である。よって $G-G\ge0$ である。$-G$ にこれを使うと $(-G)-(-G)\ge0$ で、$(-G)-(-G)\equiv-(G-G)$ なので、2 により $G-G\le0$ である。$\square$
$H\ge0$ かつ $H\le0$ とする。任意のゲーム $X$ について、$X+H\ge0$ と $X\ge0$ は同値であり、$X+H\le0$ と $X\le0$ は同値である。したがって $X+H$ と $X$ は同じ結果の類に属する。
$X\ge0$ なら lem-cgt-basic の 1 により $X+H\ge0$ である。逆に $X+H\ge0$ とし、$X\ge0$ でないとすると、ある $X^R$ が $X^R\le0$ を満たす。lem-cgt-basic の 1 により $X^R+H\le0$ であるが、$X^R+H$ は $X+H$ の Right の選択肢なので $X+H\ge0$ に反する。$\le$ についても同じである。$\square$
$G-H\ge0$ のとき $G\ge H$、$G-H\le0$ のとき $G\le H$ と書き、両方が成り立つとき $G$ と $H$ は 値が等しい といって $G=H$ と書く。
$H-G\equiv-(G-H)$ なので、lem-cgt-basic の 2 により $H\ge G$ は $G\le H$ と同値である。$H\equiv0$ のときは $G-0\equiv G$ なので、$G=0$ は前の節の意味と一致する。
- $G=H$ であることと、すべてのゲーム $X$ について $G+X$ と $H+X$ が同じ結果の類に属することは同値である。
- $=$ は同値関係であり、$G=G'$、$H=H'$ なら $G+H=G'+H'$、$-G=-G'$ である。
- 値の等しさによるゲームの同値類全体は、和を演算として、$0$ の類を単位元、$-G$ の類を $G$ の類の逆元とする アーベル群 をなす。$0$ の類は、後手が勝つゲーム全体である。
1：$G=H$ とする。$H-G\equiv-(G-H)$ も lem-cgt-basic の 2 により $\ge0$ かつ $\le0$ である。任意の $X$ について、thm-cgt-zero を $H-G$ に使うと、$G+X$ と $(G+X)+(H-G)$ は同じ類に属する。和の結合法則と交換法則から $(G+X)+(H-G)\equiv(H+X)+(G-G)$ であり、lem-cgt-basic の 3 と thm-cgt-zero により、これは $H+X$ と同じ類に属する。逆に、すべての $X$ について同じ類に属するなら、$X:=-H$ とすると $G-H$ は $H-H$ と同じ類に属し、lem-cgt-basic の 3 により $H-H$ は後手が勝つ類なので、$G-H\ge0$ かつ $G-H\le0$、すなわち $G=H$ である。
2：1 の特徴づけから $=$ は同値関係である。$G=G'$ なら、任意の $X$ について $(G+H)+X\equiv G+(H+X)$ と $G'+(H+X)$ は同じ類に属するので、1 により $G+H=G'+H$ である。同様に $G'+H=G'+H'$ である。$(-G)-(-G')\equiv-(G-G')$ と lem-cgt-basic の 2 から $-G=-G'$ である。
3：2 により和は同値類の上の演算を定める。結合法則・交換法則と $G+0\equiv G$ は同一のゲームとして成り立ち、lem-cgt-basic の 3 により $G+(-G)=0$ である。$0$ の類が後手の勝つゲーム全体であることは、def-cgt-equal のあとの注意と thm-cgt-outcome による。$\square$
1 は、値が等しいゲームは、どんなゲームと並べても勝ち負けへの寄与が同じであることを意味する。たとえば、いくつかのゲームの和を解析するとき、各成分を値の等しいより簡単なゲームに取り替えてよい。
$\frac12=\{0\mid1\}$ について $\frac12+\frac12=1$ である。def-cgt-equal と thm-cgt-outcome により、$\frac12+\frac12-1$ で後手が勝つことを確かめればよい（$-1$ は Left の選択肢をもたない）。
- Left が先に打つと、Left の手は $\frac12$ の一方を $0$ にする手だけで、$\frac12-1$ になる。Right がその $\frac12$ を $1$ にすると $1-1$ になり、lem-cgt-basic の 3 により次に打つ Left が負ける。
- Right が先に $\frac12$ の一方を $1$ にすると、Left は残りの $\frac12$ を $0$ にして $1-1$ を残し、Right が負ける。Right が先に $-1$ を $0$ にすると $\frac12+\frac12$ が残り、Left が $\frac12$ を $0$ にすると、Right の手は残りの $\frac12$ を $1$ にする手だけで、Left が $1$ を $0$ にして Right が負ける。
一方 $*+*\equiv*-*$（$-*\equiv*$）は値が $0$ だが、$*$ は値が $0$ でなく（$*\parallel0$）、$0$ と大小を比べられない。値の大小は全順序ではない。
主定理 2：不偏ゲームと Sprague–Grundy の定理
ゲーム $G$ が 不偏 であるとは、Left の選択肢の集合と Right の選択肢の集合が等しく、どの選択肢も不偏であることをいう（誕生日についての帰納法による定義）。不偏ゲームでは、選択肢を単に $G'$ と書く。非負整数 $n$ について
$$
*n:=\{*0,*1,\dots,*(n-1)\mid*0,*1,\dots,*(n-1)\},\qquad*0\equiv0
$$
とおく。$*n$ は Nim の $n$ 本の山 1 つの局面であり、$*1\equiv*$ である。$k$ 個の山の Nim の局面 $(n_1,\dots,n_k)$ は和 $*n_1+\dots+*n_k$ である。
不偏ゲーム $G$ の Grundy 数 $g(G)$ を、誕生日についての帰納法で、$\{g(G')\mid G'\text{ は }G\text{ の選択肢}\}$ に含まれない最小の非負整数と定める。有限集合 $S$ に含まれない最小の非負整数を $\operatorname{mex}S$ と書くと、$g(G)=\operatorname{mex}\{g(G')\}$ である。
この定義は Nim の定義「Grundy数」と同じ規則で、帰納法を残り手数ではなく誕生日で行ったものである。
$G$ を不偏ゲームとする。
- $-G\equiv G$ であり、$G\ge0$、$G\le0$、$G=0$ は互いに同値である。したがって $G=0$ か $G\parallel0$ のどちらかである。
- $G=0$ であることと、値が $0$ に等しい選択肢 $G'$ がないことは同値である。
- 非負整数 $a$、$b$ について、$*a+*b=0$ と $a=b$ は同値である。とくに $*a=*b$ なら $a=b$ である。
要点：不偏ゲームでは Left と Right の区別がないので、勝ち負けは先手か後手かだけで決まる。
詳しい証明を開く
1：$-G\equiv\{-G'\mid-G'\}$ と帰納法の仮定 $-G'\equiv G'$ から $-G\equiv G$ である。lem-cgt-basic の 2 により $G\ge0$ は $-G\le0$、すなわち $G\le0$ と同値である。
2：$G\ge0$ は「どの $G'$ も $G'\le0$ でない」ことであり、1 を $G'$ に使うと $G'\le0$ は $G'=0$ と同値なので、これは「$G'=0$ となる $G'$ がない」ことである。1 により $G\ge0$ は $G=0$ と同値である。
3：$-*a\equiv*a$ なので $*a+*a\equiv*a-*a=0$ である（lem-cgt-basic の 3）。$a< b$ なら $*a+*b$ は選択肢 $*a+*a=0$ をもつので、2 により $*a+*b\neq0$ であり、$a>b$ のときも $*a+*b\equiv*b+*a$ から同じである。$*a=*b$ なら thm-cgt-group により $*a+*b=*b+*b=0$ なので $a=b$ である。$\square$
- 不偏ゲーム $G$ は $*g(G)$ と値が等しい。とくに、$G$ で後手が勝つことと $g(G)=0$ は同値である。
- 不偏ゲーム $G$、$H$ について $g(G+H)=g(G)\oplus g(H)$ である。ここで $\oplus$ は Nim の定義「Nim和」である。
1：誕生日についての帰納法で示す。$m:=g(G)$ とし、$G+*m=0$ を示す。不偏ゲームの和は（帰納法により）不偏なので、lem-cgt-impartial の 2 により、値が $0$ の選択肢がないことを示せばよい。選択肢は次の 2 種類である。
- $G'+*m$（$G'$ は $G$ の選択肢）：帰納法の仮定から $G'=*g(G')$ であり、$g$ の定義から $g(G')\neq m$ である。thm-cgt-group の 2 により $G'+*m=*g(G')+*m$ で、lem-cgt-impartial の 3 によりこれは $0$ でない。
- $G+*j$（$0\le j< m$）：$g$ の定義から $g(G')=j$ となる $G$ の選択肢 $G'$ があり、$G+*j$ は選択肢 $G'+*j$ をもつ。帰納法の仮定から $G'+*j=*j+*j=0$ なので、lem-cgt-impartial の 2 により $G+*j\neq0$ である。
よって $G+*m=0$ であり、thm-cgt-group の群の演算で $*m$ を足すと $G=G+(*m+*m)=*m$ である。後半は lem-cgt-impartial の 3（$*m=0=*0$ と $m=0$ の同値）による。
2：$a:=g(G)$、$b:=g(H)$、$c:=a\oplus b$ とする。Nim の局面 $(a,b,c)$ は Nim 和が $a\oplus b\oplus c=0$ なので、Nim の定理「Boutonの定理」により手番の者が負ける局面、すなわち後手が勝つ局面であり、thm-cgt-group の 3 により $*a+*b+*c=0$ である。$-*c\equiv*c$ なので $*a+*b=*c$ であり、1 と thm-cgt-group から $G+H=*a+*b=*c$ である。一方 1 から $G+H=*g(G+H)$ なので、lem-cgt-impartial の 3 により $g(G+H)=c$ である。$\square$
2 を繰り返すと、不偏ゲームの和 $G_1+\dots+G_k$ で後手が勝つのは $g(G_1)\oplus\dots\oplus g(G_k)=0$ のときである。ゲームを 1 つずつ Grundy 数に置き換えれば、和は Nim として解ける。Nim の定理「Sprague–Grundyの定理」は、2 と同じ主張である。
山から $1$ 個か $2$ 個の石を取るゲームの $n$ 個の山を $T_n$ とすると、$g(T_n)$ は $n$ を $3$ で割った余りである（$g(T_0)=0$、$g(T_1)=\operatorname{mex}\{0\}=1$、$g(T_2)=\operatorname{mex}\{1,0\}=2$ で、以後 $g(T_n)=\operatorname{mex}\{g(T_{n-1}),g(T_{n-2})\}$ が $0,1,2$ を繰り返す。石取りゲームと必勝法 の定理「1 つの山のゲーム」と同じ周期である）。$T_7$ と Nim の山 $*5$ を並べた $T_7+*5$ では、$g=1\oplus5=4\neq0$ なので先手が勝つ。勝つ手は、和の Grundy 数を $0$ にする手、たとえば Nim の山を $5$ 本から $1$ 本にする手である（$1\oplus1=0$）。
例と反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 有限回で必ず終わる | 局面 $p$ から、Left も Right も $p$ 自身へ移れるゲーム | 対局が終わらず、どちらも必ず勝つことはできない。4 つの結果の類のどれにも属さない |
| 最後に手を打った者が勝つ | 最後の 1 本を取った者が負けになる Nim で、$H=(2,2)$、$X=(1)$ | $H$ と $X$ はどちらも手番の者が負けるが、$X+H=(1,2,2)$ は手番の者が勝つ。thm-cgt-zero にあたる主張が成り立たない |
| 不偏であること | $1=\{0\mid\ \}$ | $1>0$ なので、lem-cgt-impartial の 1 により値が $0$ か $\parallel0$ になる $*n$ のどれとも値が等しくない |
確かめ：1 行目の対象はどの日にも生まれないので def-cgt-game の意味のゲームではなく、どちらが先に打っても対局が終わらないので、thm-cgt-outcome のちょうど一方が必ず勝てるという結論が成り立たない。2 行目は Nim の定理「最後の1本を取ると負けのNim」による。$(2,2)$ は $2$ 本以上の山があって Nim 和が $0$、$(1)$ は $1$ 本の山が奇数個なので手番の者が負け、$(1,2,2)$ は $2$ 本以上の山があって Nim 和が $1\neq0$ なので手番の者が勝つ。3 行目で $1=*n$ とすると、$1$ と $*n$ は thm-cgt-group の 1（$X=0$）により同じ結果の類に属するはずだが、$1$ は Left が必ず勝つ類、$*n$ は後手か先手が勝つ類である。
DH09 §2（pp. 4–9）は、2 人のゲームの 4 つの結果、和・符号反転・大小と不偏ゲームの定義（表 1、p. 6）、値が等しいゲームは同じ結果をもつこと（p. 7）、不偏ゲームが 1 つの山の Nim と等しいという Sprague–Grundy の理論（§2.2、pp. 7–8）を、証明なしに概観している。Sprague–Grundy の定理の初等的な証明は BTB11 §3.10.4（pp. 175–178）にある。同書の証明は Grundy 数の言葉だけで行い、上のようにゲームの値の群を経由しない。誕生日が有限とは限らないゲームまで考えると、$1$、$\frac12$ のような「数」のゲームを広げた Conway の超現実数は、実数と順序数を含む順序体をなす（DH09 §2.1、pp. 5–6。この記事では証明しない）。
関連項目
- 前提: Nim, 数学的帰納法, アーベル群
- 比較: 石取りゲームと必勝法, Ehrenfeucht–Fraïsséゲーム
- 関連: 構造的帰納法, 半順序
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
