Grundy数
1. Nimのまとめ
必勝形 ＝ すべての山の個数について，XORとると 0 になる状態
開始状態が必勝形 → 後手の勝ち
開始状態が必勝形でない → 先手の勝ち
2. 一般の組合せゲームの場合
必勝形 ＝ すべての部分ゲームのGrundy数について，XORとると 0 になる状態
開始状態が必勝形 → 後手の勝ち
開始状態が必勝形でない → 先手の勝ち
Grundy数や部分ゲームの説明は，このあとすぐ！（厳密には，組合せゲームではなくて，不偏ゲームです．）
3. Grundy数とは
その状態が必勝形かどうかを調べるために使う数．Grundyさんが考えました．
必勝形の Grundy数 ＝ 0．言い換えれば，Grundy数 = 0の状態 → 必勝形
ある状態SのGrundy数 ＝ mex(「状態Sから遷移可能な状態のGrundy数」の集合)
mex ・・・最小除外数（Minimum excludant）．集合に含まれない最小非負整数．
4. NimにおけるGrundy数の計算
(1)山の数が1つのNim
山の石数$ nに対するGrundy数を$ g(n)としよう．
$ n = 0のとき，何もできない必勝形なので，$ g(0)=0
$ n=1のとき，遷移可能な状態は$ n=0のみ．$ \{g(0)\}=\{0\}に含まれない最小非負整数は 1 なので，$ g(1)=1
$ n=2のとき，遷移可能な状態は$ n=0, 1．$ \{g(0), g(1)\}=\{0, 1\}に含まれない最小非負整数は 2 なので，$ g(2)=2
$ n=3のとき，遷移可能な状態は$ n=0, 1, 2．$ \{g(0), g(1), g(2)\}=\{0, 1, 2\}に含まれない最小非負整数は 3 なので，$ g(3)=3
以下同様に，$ g(n)=n．つまり，Grundy数 ＝ 山の石数になる．
(2) 山の数が複数のときのNim
スプレイグ・グランディの定理（詳しくは，参考サイト1）を用いる 複数の山を扱うゲームを，1つしか山がない部分ゲームに分割する．
各山（各ゲーム）に対するGrundy数を求める．
各山のGrundy数のXORを計算する．= 0 なら必勝形，つまり後手が勝ち．≠0なら先手が勝ち，となる．
(1)の結果より，Grundy数＝山の石数なので，各山の数のXOR = 0なら 後手の勝ち，≠0なら 先手の勝ち，となる．
1つの山からとれる石の個数が$ Lから$ Rの間に限定されたNim．
(1)山の数が1つで，$ (L, R) = (2, 3)のとき
山の石数$ nに対するGrundy数を$ g(n)としよう．
$ n = 0, 1のとき，何もできない必勝形なので，$ g(0)=g(1)=0
$ n=2のとき，遷移可能な状態は$ n=0．$ \{g(0)\}=\{0\}に含まれない最小非負整数は 1 なので，$ g(2)=1
$ n=3のとき，遷移可能な状態は$ n=0, 1．$ \{g(0), g(1)\}=\{0\}に含まれない最小非負整数は 1 なので，$ g(3)=1
$ n=4のとき，遷移可能な状態は$ n=1, 2．$ \{g(1), g(2)\}=\{0, 1\}に含まれない最小非負整数は 2 なので，$ g(4)=2
$ n=5のとき，遷移可能な状態は$ n=2, 3．$ \{g(2), g(3)\}=\{1\}に含まれない最小非負整数は 0 なので，$ g(5)=0．よって，$ n=5のときは必勝形
$ n=6のとき，遷移可能な状態は$ n=3, 4．$ \{g(3), g(4)\}=\{1, 2\}に含まれない最小非負整数は 0 なので，$ g(6)=0．よって，$ n=6のときは必勝形
$ n=7のとき，遷移可能な状態は$ n=4, 5．$ \{g(4), g(5)\}=\{2, 0\}に含まれない最小非負整数は 1 なので，$ g(7)=1．
$ n=8のとき，遷移可能な状態は$ n=5, 6．$ \{g(5), g(6)\}=\{0\}に含まれない最小非負整数は 1 なので，$ g(8)=1．
$ n=9のとき，遷移可能な状態は$ n=6, 7．$ \{g(6), g(7)\}=\{0, 1\}に含まれない最小非負整数は 2 なので，$ g(9)=2
$ n=10のとき，遷移可能な状態は$ n=7, 8．$ \{g(7), g(8)\}=\{1\}に含まれない最小非負整数は 0 なので，$ g(10)=0．よって，$ n=10のときは必勝形
$ n=11のとき，遷移可能な状態は$ n=8, 9．$ \{g(8), g(9)\}=\{1, 2\}に含まれない最小非負整数は 0 なので，$ g(11)=0．よって，$ n=11のときは必勝形
以下同様に，$ g(n)を求めると，次のようになる．
table: (L, R) =(2, 3)のときの g(n)
n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...
g(n) 0 0 1 1 2 0 0 1 1 2 0 0 1 1 2 ...
(2)山の数が1つで，$ (L, R) = (2, 5)のとき， $ (L, R) = (3, 4)のとき
初めから表を使って，$ g(n)を求めてみる．
table: (L, R)=(2, 5)のときのg(n)
n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
g(n) 0 0 1 1 2 2 3 0 0 1 1 2 2 3 0 0 1 1 2 2 3
table: (L, R)=(3, 4)のときのg(n)
n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
g(n) 0 0 0 1 1 1 2 0 0 0 1 1 1 2 0 0 0 1 1 1 2
(1), (2) をまとめると，$ g(n)=\lfloor\frac{n\ \% \ (L+R)}{L}\rfloor となる．$ \%は剰余，$ \lfloor x\rfloorは小数切り捨て．
(2) 山の数が複数のときのNim
スプレイグ・グランディの定理を使うと，通常のNimと同じように解ける．
各山の数のGrundy数のXOR = 0なら後手の勝ち，≠0なら先手の勝ち，となる．
参考サイト：