grundy数について勉強したのでお話します。
grundy数はご存知の通り、ゲームの勝敗を求める際に使う数なのですが、こんな感じの性質があると思います。
1.grundy数は非負整数であり、grundy数=0ならば負け、grundy数>=1ならば勝ちを意味する。
2.grundy数=kの状態からは、0...k-1の状態へ行ける。
3.grundy数を増やすmoveは意味がない
4.N個のgrundy数はXORを適応して一つのgrundy数にできる
1.2.まあこれは定義なんですが、ゲームの勝敗の決め方をきちんと押さえています。
ゲームにおける勝敗は次のように言い換えられます。
「勝ち」<=>次に遷移できる状態で「負け」が存在する。
「負け」<=>次に遷移できる状態がすべて「勝ち」である。
勝ちの条件は「存在する」なのに対し、負けの条件は「すべて」なので負けの方が条件が厳しいのがわかると思います。
なのでゲームの問題を解く際は「負け」の状態は何なのかを一番最初に考えるのがよさそうですね。
grundy数の話に戻すと、負けというのは次にどう行動しても「勝ち」の状態になってしまう、
いわばどんづまりの状況なのでgrundy数=0とする感じです。
3.grundy数を増やす行動をしたとしましょう、すると相手はgrundy数をもとに戻すような行動をとることが出来ますし、さらに元のgrundy数よりも小さいgrundy数の状態に遷移するような行動をした場合、自分はターンを無駄にしたということになります。
grundy数を求める際、遷移できない状態の最小のgrundy数を考え、それよりも大きい遷移可能な状態のgrundy数は無視しますが、これは3が成立するからです。
4.Nimの考え方と同じです。
Nimでは
「負け」=N個の値をXORした値が0になる
ですが、これは上のゲームの勝敗の言い換えを適応すると簡単に示せます。
複数の値を1つの値で扱えるのはXORの結合法則(演算の順番が関係ない性質)のおかげですね。
grundyも1.2.3の性質から4を示すことが出来ます。
ゲームの問題は苦手意識があったけど、grundy数を学ぶことによって、少し考え方がわかった気がする。
