次のようなゲームを組み合わせゲームという
有名なものとして ニム (https://ja.wikipedia.org/wiki/ニム, https://en.wikipedia.org/wiki/Nim) がある.
ゲームを \(A=(\mathcal{P},\mathcal{R})\) で表現する. ここで \(\mathcal{P}\) は、あり得る局面全体からなる集合である. \(\mathcal{R}\) はルールを表現する. ここで、ルールとは、 ある局面を渡されたときに、合法な手によって写せる先の局面を定めることができれば十分である. (組み合わせゲームにおいては、誰の手であっても打てる手は同じで、写せる先も同じ.) ある局面 \(P \in \mathcal{P}\) について、それを写せることのできる局面全体を \(\mathcal{R}(P)\) と書く. 写せる先のない局面は \(\mathcal{R}(P) = \{\}\) であるような \(P\) のことであり、このような局面を最終局面という. 言い換えれば、打つ手が無い局面である. 慣例として、最終局面に写した人が勝ちで、打つ手が無い場合に負けとする. これをゲームの正規形と呼ぶ. ちょうど逆として、打つ手が無い場合に勝ちを確定するものを、逆形と呼ぶ.
nつの山がある. 一つの山はいくつかの石から成る. プレイヤーは交互に、一つの山を選び、そこから1つ以上、あるだけ自由な個数の石を取ることを、する.
最終局面とは、どの山にも石が残ってない状態である. いずれかの山に、１つ以上石が残っていれば、手は残っているので最終局面ではないからである.
正規形においては、最後の一つの石を取ったものが勝ちであり、 最終局面を渡された側の負けである.
逆形においては、最後の一つの石を取ったものが負けである.
あるゲーム \(A=(\mathcal{P}, \mathcal{R})\) の グランディ数とは、\(g: \mathcal{P} \rightarrow \mathbb{N}\) なる写像である. ここで \(\mathbb{N}\) とは自然数 (非負整数) 全体 (\(0,1,2,\ldots\)) である.
グランディ数を次のように定義する: \[g(P) = mex~ \{ g(P') : P' \in \mathcal{R}(P)\}.\]
ここで mex とは、最小除外数 (minimum exclusion) などと呼ばれるもので、 \(mex~T\) (\(T\) は自然数の部分集合) とは、\(T\) に含まれない自然数の中で最小の数のことである. すなわち \(\min~(\mathbb{N} \setminus T)\) と書いても良い.
定義から、\(P\) が最終局面ならば、\(g(P)\) は \(mex~\{\} = 0\) である.
山にN個の石がある. 石が在る限り、1個以上3個以下の石を交互に取る.
正規形を考える. すなわち、石が1個も取れない状態 (空の状態) が回ってきたら負けである. 最後の1個の石を取ったら勝ちだと言い換えても良い.
このゲームの局面は、山に残った石の数で表現できる. 例えば山に石が3個残ってる局面を \(P=3\) と書く. さてではグランディ数はいかになるか、小さい\(P\)について具体的に書きだしてみる.
\(P=0\) が最終局面であるので、その時に \(g=0\) であるのは良い. \(P=1\) のとき、移れる先としては \(P=0\) がある. \(g(1) = mex~\{0\} = 1\). \(P=2\) のとき、移れる先として \(P=0,1\) がある. \(g(2)=mex~\{0,1\}=2\). みたいに数が上がっていくが、 \(P=4\) のときに初めて、移れる先として \(P=1,2,3\) となって最終局面に移れない. \(g(4)=0\) である.
| P | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ... |
|---|---|---|---|---|---|---|---|---|---|---|---|
| g | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 4 | 5 | ... |
最終局面なら \(g=0\). 移る先がいつも \(g>0\) なら \(g=0\). 当然だ.
3個以下と制限を与えたが、一般に \(k\) 個以下なら、グランディ数は周期 \(k+1\) で \(g = 0,1,2,..,(k-1),k,0,1,2,..\) となりそうなのが観察から分かる. 制限なし (いくつでも取っていい) なら、\(k=\infty\) とすれば良いだろう.
\(g(P)=0\) のとき、またそのときに限り、 局面 \(P\) は後攻必勝である. (つまり局面\(P\) が渡された人は必ず負ける.)
ゲーム \(A_1=(\mathcal{P}_1, \mathcal{R}_1)\) と \(A_2=(\mathcal{P}_2, \mathcal{R}_2)\) の和を \(A_1+A_2=(\mathcal{P}_1 \times \mathcal{P}_2, \mathcal{R}_1 + \mathcal{R}_2)\) と定める.
ゲーム和の局面は、2つのゲームの局面の直積 (すなわちただの対) である.
ゲーム和のルール \(\mathcal{R}_1 + \mathcal{R}_2\) は選択和であり、2つのゲームの局面のうち、どちらか一方だけを動かすものである: \[(\mathcal{R}_1 + \mathcal{R}_2)(P_1,P_2) = \{ (P_1',P_2) : P_1' \in \mathcal{R}_1(P_1) \} \cup \{ (P_1,P_2') : P_2' \in \mathcal{R}_2(P_2) \}.\]
和は次のように解釈できる: 2つのゲームを横に並べて遊ぶ. 自分の手番ではどちらか1つだけを選んで手番を進める.
両方のゲームが共に最終局面になったときに、ゲーム和も最終局面であると解釈される.
\[g(P_1,P_2) = g(P_1) +^* g(P_2)\] で与えられる. ここで演算子 \(+^*\) は、ニム和とも呼ばれるもので、 bit表現したときの 排他的論理和 である.
一般に、\(n\) 個以上のゲーム和も定義できて、 その和のグランディ数も、 \[g(P_1,P_2,..,P_n) = \sum {}^* g(P_i)\] で与えられる (ニム和の総和).
2つの山があって、それぞれ \(n\) 個、\(m\) 個の石からなる. プレイヤーは交互に、1つの山を選んで石を取る. 先ほどと同様に、取る石の数は1個以上3個以下と制限する. 最後の最後の一個を取ったら勝ちで、 どちらの山にも石が残ってない局面が渡されたら負けである (正規形).
状態は \((n,m)\) で表せる. 終盤局面は \((0,0)\) である. \((n,0)\) または \((0,m)\) なら、グランディ数は、先ほどの山が1つの場合と同じである. それ以外ではどうか.
例えば、\((4,1)\) の時、 \(\mathcal{R}(4,1) = \{ (4,0), (3,1), (2,1), (1,1) \}\) であって…
二次元のテーブルの上でグランディ数を具体的に書きだしてみると、 周期性が見えて、やはりなんとなく分かるが、 先ほどのニム和の性質が満たされていることも確認できる. すなわち、 \[g(n,m) = g(n) +^* g(m) = ((n+1) \bmod 4) +^* ((m+1) \bmod 4)\] である.
グランディ数の定義の仕方から、次が言える.
以上のことと、先手必勝でないならば後手必勝であるという組み合わせゲームの性質を考えれば、 証明は容易である.
以上.