石取りゲーム（Nim）
1. 石取りゲーム（Nim）のルール
2人対戦ゲーム
プレイヤーが順番に石を取り，石が取れなくなった方が負け（最後まで取り切った方が勝ち）
$ N個の石の山から1つを選び，好きな数だけ石を取れる．
2. 数値例で具体的に考える
自分の手番が終わってこの状態にすれば，絶対に勝てる状態を必勝形と呼ぼう．
山が全くなくなった状態は，明白な必勝形である．
以下，開始直後の状態に対して，地道に場合分けをする．山は石の数に関して昇順に並べて考える．
$ N=1のとき
1山しかないので，全部取り切れば必勝形になる．よって先手の勝ち．
$ N = 2のとき
石数 (1, 1) のとき： どちらかの山を取り切るしかなく，$ N=1になるので，先手の負け．言い換えれば，自分の番が終わって(1, 1)になれば，相手が負ける→自分が勝てるので，(1, 1)は必勝形である．
石数 (1, 2+) のとき： 2+は2個以上を表す．2+→1とすれば(1, 1)という必勝形にできるので，先手の勝ち
石数 (2, 2) のとき： どうやっても$ N=1か(1, 2)になり，相手が勝つので，先手の負け．つまり，(2, 2)は必勝形．
石数 (2, 3+)のとき： 3+→2にすれば(2, 2)という必勝形にできるので，先手の勝ち
石数 (3, 3)のとき： どうやっても$ N=1か(2-, 3)になり，相手が勝つので，先手の負け．2-は2個以下を表す．つまり，(3, 3)は必勝形
石数 (3, 4+)のとき： 4+→3にすれば(3, 3)という必勝形にできるので，先手の勝ち
以下同様，(n, n)なら先手の負け，それ以外は先手の勝ち
$ N=3のとき
石数 (1, 1, 1+)のとき： 1+の山を除けば，(1, 1)という必勝形になるので，先手の勝ち
石数 (1, 2, 2)のとき： 1の山を除けば，(2, 2)という必勝形になるので，先手の勝ち
石数 (1, 2, 3)のとき： どうやっても$ N=2の必勝形にできず，$ N=3の必勝形は未発見なので，先手の負け．つまり，(1, 2, 3)は必勝形である．
石数 (1, 2, 4+)のとき： 4+→3にすれば(1, 2, 3)という必勝形にできるので，先手の勝ち
石数 (1, 3, 3+)のとき： 3+→2にすれば(1, 2, 3)という必勝形にできるので，先手の勝ち
石数 (1, 4, 4)のとき： 1の山を除けば，(4, 4)という必勝形になるので，先手の勝ち
石数 (1, 4, 5)のとき： $ N=2の必勝形にできず，必勝形の(1, 2, 3)にもならないので，先手の負け．つまり，(1, 4, 5)は必勝形
石数 (1, 4, 6+)のとき： 6+→5にすれば(1, 4, 5)という必勝形にできるので，先手の勝ち
石数 (1, 5, 5+)のとき： 5+→4にすれば(1, 4, 5)という必勝形にできるので，先手の勝ち
石数 (1, 6, 6)のとき： 1の山を除けば，(6, 6)という必勝形になるので，先手の勝ち
石数 (1, 6, 7)のとき： $ N=2の必勝形にできず，必勝形の(1, 2, 3)にも(1, 4, 5)にもならないので，先手の負け．(1, 6, 7)も必勝形
．．．法則性がワカラナイ．．．orz
3. 数値例で考えたまとめ
必勝形でない状態を，非必勝形と呼びます（呼びにくい）．
以下の2つの仮定をします．
どんな非必勝形からでも，1手で必ず必勝形にすることができる
どんな必勝形からでも１手行うと，非必勝形になる
この仮定が正しいとすると，次のことが言えます．
開始状態が非必勝形なら，次の1手で必勝形にできるので，先手の勝ち
開始状態が必勝形なら，先手の最初の1手で非必勝形になり，後手の次の1手で必勝形になるので，先手の負け
4. 必勝形か否かの判定
石取りゲームの場合，必勝形とは，すべての山の個数についてXORとると0になる 状態とのこと．
一般のゲームの場合には，Grundy数なるものを考えます．
確認：
石数 (n, n)のとき： n ^ n = 0
石数 (1, 2, 3)のとき： 1 ^ 2 ^ 3 =$ (01)_2^$ (10)_2^ $ (11)_2 = $ (00)_2
石数 (1, 4, 5)のとき： 1 ^ 4 ^ 5 =$ (001)_2^$ (100)_2^ $ (101)_2 = $ (000)_2
石数 (1, 6, 7)のとき： 1 ^ 6 ^ 7 =$ (001)_2^$ (110)_2^ $ (111)_2 = $ (000)_2
5. まとめ
必勝法の手順をざっくり言えば，
自分の番が終わった時の状態が必勝形になるようにする
→ 相手が何をしても，相手の番が終わったあとの状態は非必勝形になる
→ 自分の番で適切な手を選んで必勝形の状態にする
となります．自分の番が始まった時点ですでに必勝形だと，相手が必勝となる，ということですね．
参考ページ：