0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

Grundy数を使って1次元ドミノ置きゲームを解く(その1)

Posted at

オンライン整数列大辞典に以下のような問題がありました。これをプログラムで解くことを考えます。

#####【問題】1次元のマス目(1xN)に交互にドミノ(1x2)を置いて行って置けなくなった方が負けというゲームで、先手が必ず負けになるN<100をリストせよ。

例えばN=4の時、先手は以下のように対称性を考慮すると2通りの置き方があり、(1)では先手の勝ち、(2)では後手の勝ちとなります。

N=5の時も2通りの置き方がありますが、どちらの場合も後手が置くと次はもう置けなくなるので先手の負けとなります。

Grundy数で勝敗の判定

どうやらこの問題を解くためには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 Grundy数
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=1の(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 Grundy数
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

これを見ると規則性が見えてきたようです。次回ではこれをプログラムを書いていきたいと思います。

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?