石取りゲームとGrundy数の基本的な考え方を説明したいと思います。
石取りゲーム（山が一つ）
【例題 １】以下の石取りゲームを勝つための最初の一手は？
- 10個の石を交互に取っていく
- 1回に取れるのは3個まで
- 最後に取れる石がなくなったほうが負け
これをGrundy数の考え方で解いて行きます。Grundy数を使って1次元ドミノ置きゲームを解く（その１）で紹介したようにに、Grundy数G(P)とは、
- 負けが確定した状態$P_{lost}$のとき$G(P_{lost})=0$
- $P$から1手で遷移できる状態が$P'_1, P'_2,..., P'_k$だとすると
$G(P)=mex(G(P'_1), G(P'_2),..., G(P'_k))$- ここでmex(Minimum excludant)は引数に含まれない最小の非負整数で、例えば$mex(0,1,3) = 2$となります
石の個数をPとすると$G(0)=0$でそれ以降3個まで取れるので、それぞれのG(P)を順次求めていくと以下のようになります。
| P | $P'_1,P'_2,P'_3$ | mex | G(P) |
|---|---|---|---|
| 0 | - | - | 0 |
| 1 | 0 | mex(0) | 1 |
| 2 | 0,1 | $mex(0,1)$ | 2 |
| 3 | 0,1,2 | $mex(0,1,2)$ | 3 |
| 4 | 1,2,3 | $mex(1,2,3)$ | 0 |
| 5 | 2,3,4 | $mex(2,3,0)$ | 1 |
| 6 | 3,4,5 | $mex(3,0,1)$ | 2 |
| 7 | 4,5,6 | $mex(0,1,2)$ | 3 |
これで先手は$G(P)=0$となる$P \equiv 0 \pmod 4$になるような手を打てば勝てるということが分かるので、最初に１０個あった場合には２個とって８個にすればよいということが分かります。
この例題の場合にはGrundy数が０の場合だけ分かればよかったのですが、$0$以外のGrundy数がどういう意味を持つのかはちょっとピントきませんね。それは山の数が2個以上になると意味を持ってます。
石取りゲーム（山が３つ）
【例題 ２】以下の石取りゲームを勝つための最初の一手は？
- ３つの山に、それぞれ3個、5個、7個の石がある
- 1回に取れるのは1つの山から3個まで
- 最後に取れる石がなくなった方が負け
ここで使うのがスプレイグ・グランディの定理で、簡単に言うと以下のようになります。
N個の部分ゲームに対するGrundy数を求めてXORを取ったものが全体のGrundy数となる
すでに部分ゲーム（山が一つの石取りゲーム）のGrundy数は分かっているのでそのXORを取ります。
\begin{align}
&G(3,5,7) = G(3) \oplus G(5) \oplus G(7) = 3 \oplus 1 \oplus 3 = 1 \\
\end{align}
従ってこれが０になるように石を取れば良いので、例えば5個の山から1個取ればよいことが分かります。その後はGrundy数が0になるように取っていけば勝てるということです。
山が３つでGrundy数が0になる配置
それではこのゲームでGrundy数が0になる配置は何個あるでしょう？
個々の山のGrundy数は$[0,1,2,3]$なので3個の重複組み合わせでXORが０になるもの求めるの以下の5個の配置があることが分かります。
from itertools import combinations_with_replacement
[(a,b,c) for a,b,c in combinations_with_replacement(range(4),3) if a^b^c == 0]
# [(0, 0, 0), (0, 1, 1), (0, 2, 2), (0, 3, 3), (1, 2, 3)]
この基本的な考え方をで、色々なパターンの石取りゲームの必勝パターンを求めることができますね。
（開発環境：Google Colab）