(cache)勝敗が周期34で変化するゲーム - フィボナッチ・フリーク

先日、いつものように夜眠れずに布団の中で数学のことを考えていたところ、ふと面白いゲームを思いつきました。

ルールは簡単です。 $1 \times n$ のマス目に2人で交互に $1 \times 2$ のタイルを置いていきます。タイルは重なってはいけません。先に置けなくなったプレイヤーが負けです。

f:id:fibonacci_freak:20170902015458p:plain

布団の中でしばらく考えたところ、まず $n$ が2以上の偶数の時は先手必勝であることがわかりました。必勝手順は次の通りです。

(1) 先手は最初に中央の2マスにタイルを置く。

(2) その後は後手が置いたタイルと左右対称な位置に置くことを繰り返す。

こうすれば先手が置いた後は常に盤面が左右対称になるため、先手が置けなくなることは決してありません。

次に $n$ が奇数の時を順番に考えていくと次のことがわかりました。

・ $n = 3$ は先手必勝。

・ $n = 5$ は後手必勝。

・ $n = 7$ は先手必勝。

・ $n = 9$ は後手必勝。

・ $n = 11$ は先手必勝。

・ $n = 13$ は先手必勝。

これらは単純に全ての手のパターンを考えることで得られます。

ここまでは特に規則性が無いように見えたので、何か手がかりになる情報がないかと思いネットで調べてみました。すると次のような記述が見つかりました（要約）。

このゲームはDawson's Kaylesと呼ばれ、octal gameという種類に属する。octal gameにはGuy-Smith periodicityという定理が知られており、それによればDawson's Kaylesの勝者は

n

について有限個の例外を除き周期34で繰り返す。具体的には後手必勝となるのは

n = 0, 1, 15, 35

または

n \equiv 5, 9, 21, 25, 29 m o d 34

の時に限る。

さすがにこれには驚きました。周期34で繰り返すなんて誰が予想できるでしょうか！

そういうわけで今回はこの周期性（Guy-Smith periodicity）をDawson's Kaylesの場合に限って証明したいと思います。

Grundy値について

今回の証明の鍵となるのが、ゲームの局面について定まるGrundy値と言う概念です。

ここでは「有限の手数で勝敗が決することが保証され、確率的要因が絡まず、両者の打てる手が対等で、盤面の情報が全て共有されており、打てる手が無くなった人が負ける」というタイプのゲームのみを考えることにします。Dawson's Kaylesはこのようなゲームの一例です。あとで見ますが、この種のゲームの局面についての命題を示す時は「ゲームが終わるまでの最長手数」に関する帰納法を使うことができる、ということに注意しましょう。

ゲームの局面 $G$ について、局面 $G^{'}$ が $G$ から一手で得られることを $G^{'} \in G$ と表記します。

定義. ゲームの局面

G

に対し、そのGrundy値

g (G)

を以下のように帰納的に定める。

g (G) = \underset{G^{'} \in G}{m e x} g (G^{'})

ただし

{m e x}_{x \in S} x

は

S

に現れない最小の非負整数（

S

が空なら0）を指す。

このとき局面 $G$ が後手必勝であることは $g (G) = 0$ と同値です。なぜなら（上に述べた帰納法で） $G$ が先手必勝となるのは $G^{'} \in G$ で後手必勝のものが存在することと同値で、これは帰納法の仮定から $g (G^{'}) = 0$ なる $G^{'}$ が存在すること、すなわちその $m e x$ が $0$ にならないことと同値だからです。

Grundy値はただの数字の割り当てではなく、際立った性質を持っています。それは「局面の直和」に対してうまく振る舞うということです。2つの局面 $G_{1}, G_{2}$ の直和 $G_{1} + G_{2}$ とは「2つの局面を並べた*1ゲームの局面」のことです。例えば $1 \times n$ のDawson's Kaylesの初期局面を $K_{n}$ とすると、 $K_{10}$ の中央にタイルを置いた局面は $K_{4} + K_{4}$ と書くことができます。

定理(Sprague-Grundy). ゲームの局面

G_{1}, G_{2}

について

g (G_{1} + G_{2}) = g (G_{1}) \oplus g (G_{2}) .

ただし

A \oplus B

は

A, B

の2進表記の排他的論理和である。

証明. 帰納法で示す。 $G^{'} \in (G_{1} + G_{2})$ は $G_{1}^{'} + G_{2} (G_{1}^{'} \in G_{1})$ または $G_{1} + G_{2}^{'} (G_{2}^{'} \in G_{2})$ と書くことができる。よって帰納法の仮定より

S = {g (G_{1}^{'}) \oplus g (G_{2}) ∣ G_{1}^{'} \in G_{1}} \cup {g (G_{1}) \oplus g (G_{2}^{'}) ∣ G_{2}^{'} \in G_{2}}

と定めた時

g (G_{1} + G_{2}) = \underset{x \in S}{m e x} x .

$g (G_{1}) \oplus g (G_{2}) \notin S$ に注意すれば、示すべきことは $x < g (G_{1}) \oplus g (G_{2}) \Rightarrow x \in S$ と言い換えることができる。以下これを示す。

$g (G_{1}) \oplus g (G_{2}) \oplus x$ の2進表記の桁数を $m$ とする。自然数 $a$ の2進表記の下から $m$ 桁目を $[a]_{m}$ と書くことにすると

[g (G_{1}) \oplus g (G_{2}) \oplus x]_{m} = 1.

$x < g (G_{1}) \oplus g (G_{2})$ なので $[x]_{m} = 0$ , $[g (G_{1})]_{m} = 0$ , $[g (G_{2})]_{m} = 1$ としてよい。すると $g (G_{1}) \oplus x < g (G_{2})$ なので、 $g (G_{2})$ の定義を考えればある $G_{2}^{'} \in G_{2}$ があって $g (G_{2}^{'}) = g (G_{1}) \oplus x$ となる。移項して $x = g (G_{1}) \oplus g (G_{2}^{'})$ なので $x \in S$ がわかった。 $◻$

周期性の証明

さて、Dawson's Kaylesに話を戻しましょう。 $H_{n} := g (K_{n})$ と書くことにします。定義より $H_{0} = 0$ です。

これから示すGuy-Smith periodicityというのは大雑把に言うと「Grundy値がある範囲で周期的になっていればそこから先ずっと周期的になる」という定理です。これにより、数の小さい範囲で具体的に勝敗を計算して周期34の部分を見つけるだけで、その先の周期性まで示すことができるというわけです。

定理. 正整数

i, p

が存在して

H_{n + p} = H_{n}

が

i \leq n < 2 i + p + 2

に対して成り立つならば、任意の

n > i

に対しても成り立つ。

証明. $n \geq 2 i + p + 2$ について $H_{n + p} = H_{n}$ であることを帰納法により示す。 $K_{n}$ から一手だけ打った後の局面は、 $a + b + 2 = n$ を満たすある非負整数 $a, b$ に対する直和 $K_{a} + K_{b}$ である。よってGrundy値の定義とSprague-Grundyの定理より

H_{n + p} = \underset{a + b = n + p - 2}{m e x} H_{a} \oplus H_{b} .

ここで $a + b = n + p - 2 \geq 2 (i + p)$ より $a, b$ の少なくとも片方は $i + p$ 以上なので、 $b \geq i + p$ としてよい。すると帰納法の仮定より $H_{b} = H_{b - p}$ なので、 $c = b - p$ とおけば

H_{n + p} = \underset{a + c = n - 2, c \geq i}{m e x} H_{a} \oplus H_{c} .

$n - 2 \geq 2 i$ より、 $a + c = n - 2$ という分解において $c \geq i$ と仮定しても一般性を失っていない。よって上式は

\underset{a + c = n - 2}{m e x} H_{a} \oplus H_{c} = H_{n}

に等しい。 $◻$

具体的な計算

それではDawson's KaylesのGrundy値が本当に周期34を持つのか確かめてみましょう。愚直に計算すると（コンピュータに計算させると）以下の結果が得られます。字が細いので別タブなどで拡大して見てください。

f:id:fibonacci_freak:20170904011542p:plain

$H_{n + 34} \neq H_{n}$ であるものは桃色で示されています。青で示した $i = 53 \leq n < 2 i + 34 + 2 = 142$ の部分は $H_{n + 34} = H_{n}$ を満たしています。ゆえに先ほど示した定理により、この後もずっと周期34で繰り返すことがわかりました！

感想

ところで上の表を見ていると、私にはこの周期性が「数列の途中で偶然生じたものがGuy-Smith periodicityによって繰り返されてしまった」というものには思えず、最初から何か別の理由で周期性が生じているのではないか、という感覚が拭きれません（数学的ではありませんが）。青で塗られた周期的な列は、偶然できたにしては長すぎるように感じます。

今のところGrundy値の周期の長さを計算する方法は、上のように愚直に計算していって周期らしきものを見つける以外ありません。しかし私はいつか必ず34という数の本当の理由が明かされる日が来ると信じています。

*1:一度にどちらか一方だけに打てる。