ハッケンブッシュ ゲーム
ハッケンブッシュ ゲームは、Hackenbush (Wikipedia) 英語によれば、
ハッケンブッシュは、数学者ジョン・ホートン・コンウェイによって発明された2人用のゲームです。端点と地面で互いに接続した線分の任意の構成でプレイできます。プレイヤーは自分の番になると、任意の線分を「カット」(消去) します。どのパスでも地面に接続されなくなった線分はすべて「落ちる」(つまり消去される) ことになります。動けなくなった最初のプレイヤーが負けとなります。
ハッケンブッシュは幾つかのバリエーションがありますが、今回は色のついていない「グリーン・ハッケンブッシュ」に対してGrundy数を求めて、「勝つための次の一手」は何かを考えます。
枝のないハッケンブッシュ
まず最初に以下のようなシンプルな枝のない例を考えます。
これは石取りゲームとGrundy数で紹介した
「３つの山に、それぞれ1個、3個、3個の石ある石取りゲーム（取る数制限なし）」と同じになります。
従ってそのGrundy数は各々の数のXORを取ればよいので7になります。
\begin{align}
&G(1,3,5) = G(1) \oplus G(3) \oplus G(5) = 1 \oplus 3 \oplus 5 = 7 \\
\end{align}
木のハッケンブッシュ
以下の図を例として枝分かれのある木のハッケンブッシュのGrundy数を求めます。
枝分かれのところではColonの原理が利用できます。枝の各々をサブゲームと考えてスプレイグ・グランディの定理を適用したと考えれば納得します。
Colonの原理： 枝が頂点で集まる場合、各々の枝のGrundy数のXORを取ったものがその頂点のGrundy数になる
したがって木のGrundy数は再帰的に頂点を訪れて各枝のGrundy数のXORを取ればよいので以下のようなシンプルなコードで求めることができます。次の「勝つための一手」を求めるために、各ノードに入ってくる各枝からのGrundy数をDICT変数のgrsに記録しておきます。
from functools import reduce
from operator import xor
grs = dict()
def gr_tree(n):
if n not in edges: return 0 # gr = 0 if no further branch
grs[n] = [gr_tree(br)+1 for br in edges[n]] #
return reduce(xor,grs[n])
edges = {1:(2,3), 2:(4,5), 4:(7,), 3:(6,)} # T(4)
print(f"Grundy number of the tree is {gr_tree(1)}")
print(f"Grundy number of branches to the node: {grs}")
# GN of the tree is 6
# GN of branches to the node: {4: [1], 2: [2, 1], 3: [1], 1: [4, 2]}
このコードでGrundy数が求まっていく様子を図にしました。
木のハッケンブッシュでの「勝つための一手」
それでは、現在Grundy数が６である木のハッケンブッシュのどの枝を切り取れば「勝つための一手」になるかを考えます。それは、
- その枝を切り取ったあとの全体のGrundy数が０になる
ということです。従って、ノードiでの目標値を$T(i)$、Grundy数を$G(i)$とすると、以下のように考えられます。
- ます最初の目標値は$T(1)=０$
- ノード１の枝２をチェックします
- ３からの$G(3)+1='10'$なので２からの値も$'10'$であれば$T(1)=0$になるので、$T(2)$は1を引いて$'1'$になります
- ノード２の枝4をチェックします
- ５からの$G(5)+1='1'な$ので４からの値が'0'であれば$T(2)='1'$になります
- ４からの値が$'0'$ということはこの枝がないのと同じなので、4の枝を切り取るのが答えとなります。このとき$T(4)$は1を引いて$-1$です。
ノードiに接続した枝ｊの$T(j)$は、以下の式で求められます。
\begin{align}
T(j) &=T(i) \oplus (j 以外の枝の Grundy数の XOR) \\
&= T(i) \oplus (G(i) \oplus G(j)) \\
\end{align}
やや複雑ですが、これをコードにします。各ノードのGrundy数はgrsに格納されていることを仮定しています。$target==-1$になれば「勝つための一手」の場所が見つかったということです。この流れを図４に示します。
def winMoves(n, target):
tgt[n] = target
if target == -1: return [n] # Target is 0 on the parent node
if n not in edges: return [] # reach to the end of the brancd\h
gall = reduce(xor,[g for g in grs[n]]) # GN of note n
ret = []
for i in range(len(edges[n])): # for each branch
ret += winMoves(edges[n][i], (gall^grs[n][i]^target)-1)
return ret
wp = winMoves(n,0)
print(f"Winning moves are: {wp}")
# Winning moves are: [4]
同じコードを使って、もう少し複雑な木で「勝つための一手」３個見つけた例を図５に示します。
（開発環境：Google Colab、図の作成はgraphvizを使用）
この考え方はProject Euler Problem 400: Fibonacci Tree Gameを解くのに役に立ちます