Grundy数に関するメモ

若干勉強した。

Nimというゲームがあって、初期の石の数のxorを取った結果が0かそうでないかで
何故か勝敗が解る。Grundy数というのが関係あるらしい。
Nim以外のゲームでどうやって使うのか(何に対してxor取るのか)解らない。

.@nanikakaさんのd.hatena.ne.jp/nanikaka/20120…　がとても役に立った
— いささん (@Isa_rentacs) 12月 21, 2012

ゲームの状態には2つの状態がある。

ある盤面の状態は、現在の状態から遷移できる盤面の状態にlosingがあればwinning、そうでなければlosingとして決定できる。

ここで、あるゲームのルールと盤面の状態sに対して

sからルールに従って遷移できる盤面の状態の集合をs'とし、
s'の中の任意の状態に対するGrundy数の集合に含まれない最小の非負整数

を状態sのGrundy数として定義する。

sが終端状態(これ以上ゲームを継続できない)ならs'は空集合になるので
grundyNum(s)=0になる。

また、定義よりGrundy数がnの盤面からはGrundy数が0からn-1までの任意の状態に遷移できる。
(nが遷移先(の状態のGrundy数の集合)に含まれない最小の非負整数だから)
また0からは遷移ができないか、Grundy数が0でない状態に遷移できる。

このように盤面の状態を定義することで

-遷移先にlosingがあれば現在の状態はwinning
と
-遷移先にGrundy数==0の状態があれば現在の状態のGrundy数!=0

という対応付けができる。
ここから終端状態(Grundy数==0)はlosingになるように決めなければならない
(と思う)

Nimは複数山で解り辛いし、チェスボード的なのも初めはわかりづらいので

石がn個あり、2人のプレイヤーが交互に石を取っていく。取れる個数は1個か2個であり、
最後の石を取ったほうが勝ちとする

というゲームを考えてみる。と、明らかにn%3==0なら後手必勝、そうでないなら先手必勝である。

例)n%3==0のとき
先手が1個取ったら後手が2個、先手が2個なら後手が1個取って行くと後手が勝てる。

それ以外のとき
先手がn%3個取ると(残りの数)%3==0の状態に後手が手番を持った状態で回ってくる

これをn=10個のときにそれぞれの個数に対するGrundy数を手計算で求めてみると

n    10 9 8 7 6 5 4 3 2 1 0
g(n)  1 0 2 1 0 2 1 0 2 1 0

となるのが解る。
つまり、このゲームの場合はn%3というのがその状態に対するGrundy数になっているので
それが0かどうかで勝敗が解るようになっていたのだった。
また、これでNimと同様に複数山あるならそれぞれのGrundy数を求めてxorを取れば勝敗が解る。

他のルールのゲームでもGrundy数を求めれば勝敗は解るので

という解き方になっていきそう。

問題探して練習してみたいと思います。
間違い等あれば指摘していただければと思います。

Isa@Diary