Grundy数 その2
前回はGrundy数とは何かを説明しました。Grundy数に関する基本的な求め方は前の記事をご覧ください。augusuto04.hatenablog.com
ただ、これだけではあまり多くの問題に使えないのでもう少し発展的な使い方を紹介します。
Nim
私は知りませんでしたが、有名なゲームらしいですね。ルールは次の通り。
n個のコインの山があります。プレーヤーは１つの山を選んで、その山から1枚以上のコインを取り除きます。これを2人で交互に行い、取り除くコインがなかったらその時点で負けになります。
ここで、上のような場合を(4, 2, 1)と今回は表します。
とりあえず各山についてGrundy数を求める
まずは、各山についてGrundy数を求めます。
もし、0枚の山があるとするとここからは遷移できないのでGrundy数は0。
1枚の山からは0枚の山に遷移できるのでこれ以外で最小は1。
2枚の山からは0, 1枚の山に遷移できるのでこれ以外で最小は2。
このように、今回は山にあるコインの枚数とGrundy数は等しくなる。
つまり、今回の例におけるGrundy数は次の通り。
| コインの枚数 | 4 | 2 | 1 |
|---|---|---|---|
| Grundy数 | 4 | 2 | 1 |
全体について考える
では、今回は(4, 2, 1)と3つの山がありますが、この状態におけるGrundy数はどうやって求めればいいのでしょうか。結論からいいます。4 xor 2 xor 1を計算すればよいのです。つまり、この状態におけるGrundy数は7である。と言うことで今までのようにGrundy数が0より大きいので最適な行動をとれば先手の勝ちとなります。なお、xorってなんだって方はこちらをどうぞ。augusuto04.hatenablog.com
では、なぜこれでよいのでしょうか。(4, 2, 1)から遷移できるすべての状態おいて同じようにしてGrundy数を求めると次のようになります。
| 状態 | Grundy数 |
|---|---|
| (3, 2, 1) | 0 |
| (2, 2, 1) | 1 |
| (1, 2, 1) | 2 |
| (0, 2, 1) | 3 |
| (3, 1, 1) | 3 |
| (3, 0, 1) | 2 |
| (3, 2, 0) | 1 |
このようにして、Grundy数が0になるような場合か必ず存在します。では、Grundy数が0である(3, 2, 1)からの遷移を次は考えてみます。
| 状態 | Grundy数 |
|---|---|
| (2, 2, 1) | 1 |
| (1, 2, 1) | 2 |
| (0, 2, 1) | 3 |
| (3, 1, 1) | 3 |
| (3, 0, 1) | 2 |
| (3, 2, 0) | 1 |
このようにGrundy数が0になるような遷移は存在しません。前回と同じように次のことが言えます。
→相手が最適な行動をとれば負け
→自分が最適な行動をとれば勝ち
思ったよりも書きたいことが多い・・・。次の記事で実際にコードを紹介して終了にします。augusuto04.hatenablog.com
