オンライン整数列大辞典にあるドミノ置きゲームの問題をプログラムで解くことを考えます。
ドミノ置きゲームて先手が負ける場合
【問題】1次元のマス目（1xN）に交互にドミノ（1x2）を置いて行って置けなくなった方が負けというゲームで、先手が必ず負けになるN<100をリストせよ
例えばN=4の時、先手は以下のように対称性を考慮すると2通りの置き方があり、(1)では先手の勝ち、(2)では後手の勝ちとなります。
N=5の時も2通りの置き方がありますが、どちらの場合も後手が置くと次はもう置けなくなるので先手の負けとなります。
Grundy数で勝敗の判定
どうやらこの問題を解くためにはGrundy数というのが関係しそうだということで、こちらの説明を参考にさせていただきました。
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$となります
このゲームの場合N=0,1の時、先手は明らかに負けなので$G(0),G(1)=0$,
N=2の時は1手で$G(0)$となるので$G(2)=mex(G(0))=mex(0)=1$
N=4のときはG(1)とG(2)に移行できるので、それぞれの値(0,1)に対してmexが2となります。これを表にすると、
| N | mex | G(N) |
|---|---|---|
| N=0 | 0 | |
| N=1 | 0 | |
| N=2 | $mex(G(0))$ | 1 |
| N=3 | $mex(G(1))$ | 1 |
| N=4 | $mex(G(1),G(2))=mex(0,1)$ | 2 |
この表によりN=0,1では先手の負け、N=2,3,4では先手の勝ちと言うことが分かります。
スプレイグ・グランディの定理
しかしN=5の(1)の例になると、次の空きのマスが1と2にの部分ゲーム分かれてしまうので、それぞれのGrundy数を求めて結合する必要が出てきます。ここで使うのがスプレイグ・グランディの定理で、簡単に言うと以下のようになります。
N個の部分ゲームに対するGrundy数を求めてXORを取ったものが全体のGrundy数となる
すなわちN=5の(1)の場合のGrundy数は$G(1)\oplus G(2)=1$となり,(2)の$G(3)$と合わせると、$mex(G(3),G(1)\oplus G(2))=mex(1,1)=0$となります。同様にしてN=5以降のGrundy数を求めると。
| N | mex | G(N) |
|---|---|---|
| N=5 | $mex(G(3),G(1)\oplus G(2))=mex(1,1)$ | 0 |
| N=6 | $mex(G(4),G(1)\oplus G(3),G(2)\oplus G(2))=mex(2,1,0)$ | 3 |
| N=7 | $mex(G(5),G(1)\oplus G(4),G(2)\oplus G(3))=mex(0,2,0)$ | 1 |
これを見ると規則性が見えてきたようです。次回ではこれをプログラムにしたいと思います。