グリーン・ハッケンブッシュとGrundy数

### ハッケンブッシュ ゲーム

ハッケンブッシュ ゲームは、[Hackenbush (Wikipedia) 英語](https://en.wikipedia.org/wiki/Hackenbush)によれば、

> ハッケンブッシュは、数学者ジョン・ホートン・コンウェイによって発明された2人用のゲームです。端点と地面で互いに接続した線分の任意の構成でプレイできます。プレイヤーは自分の番になると、任意の線分を「カット」(消去) します。どのパスでも地面に接続されなくなった線分はすべて「落ちる」(つまり消去される) ことになります。動けなくなった最初のプレイヤーが負けとなります。



<img width=10%><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/f581ab51-4d6b-482b-8d81-ec3b69e6e947.png" width=70%>

ハッケンブッシュは幾つかのバリエーションがありますが、今回は色のついていない「グリーン・ハッケンブッシュ」に対してGrundy数を求めて、「勝つための次の一手」は何かを考えます。

### 枝のないハッケンブッシュ

まず最初に以下のようなシンプルな枝のない例を考えます。

<img width=20%><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/c2c7f890-1d9a-482b-9d81-e850e6c737dc.png"  width=50%>


これは[石取りゲームとGrundy数](https://qiita.com/masa0599/items/be77f263e54f36943a8f)で紹介した
「３つの山に、それぞれ1個、3個、3個の石ある石取りゲーム（取る数制限なし）」と同じになります。
従ってそのGrundy数は各々の数のXORを取ればよいので**7**になります。
```math
\begin{align}
&G(1,3,5) = G(1) \oplus G(3) \oplus G(5) = 1 \oplus 3 \oplus 5 = 7   \\
\end{align}
```
### 木のハッケンブッシュ

以下の図を例として枝分かれのある木のハッケンブッシュのGrundy数を求めます。

<img width=30%><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/3c4ad9d4-607d-4f68-8e3f-551bbadebc27.png"  width=50%>


枝分かれのところではColonの原理が利用できます。枝の各々をサブゲームと考えてスプレイグ・グランディの定理を適用したと考えれば納得します。

> **Colonの原理：**　枝が頂点で集まる場合、各々の枝のGrundy数のXORを取ったものがその頂点のGrundy数になる

したがって木のGrundy数は再帰的に頂点を訪れて各枝のGrundy数のXORを取ればよいので以下のようなシンプルなコードで求めることができます。次の「勝つための一手」を求めるために、各ノードに入ってくる各枝からのGrundy数をDICT変数の**grs**に記録しておきます。

```python 
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数が求まっていく様子を図にしました。


<img width=20%><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/b2aa189d-8c8b-4760-a16b-49164fcc6e76.png"  width=80%>


### 木のハッケンブッシュでの「勝つための一手」

それでは、現在Grundy数が６である木のハッケンブッシュのどの枝を切り取れば「勝つための一手」になるかを考えます。それは、

* その枝を切り取ったあとの全体のGrundy数が０になる

ということです。従って、ノードiでの目標値を$T(i)$、Grundy数を$G(i)$とすると、以下のように考えられます。

1. ます最初の目標値は$T(1)=０$
1. ノード１の枝２をチェックします
1. ３からの$G(3)+1='10'$なので２からの値も$'10'$であれば$T(1)=0$になるので、$T(2)$は1を引いて$'1'$になります
1. ノード２の枝4をチェックします
1. ５からの$G(5)+1='1'な$ので４からの値が'0'であれば$T(2)='1'$になります
1. ４からの値が$'0'$ということはこの枝がないのと同じなので、4の枝を切り取るのが答えとなります。このとき$T(4)$は1を引いて$-1$です。

ノードiに接続した枝ｊの$T(j)$は、以下の式で求められます。

```math
\begin{align}
 T(j) &=T(i) \oplus (j 以外の枝の Grundy数の XOR) \\
 &= T(i) \oplus (G(i) \oplus G(j))   \\
\end{align}
```

やや複雑ですが、これをコードにします。各ノードのGrundy数は**grs**に格納されていることを仮定しています。$target==-1$になれば「勝つための一手」の場所が見つかったということです。この流れを図４に示します。

```python 
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]
```

<img width=20%><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/15dbeef4-9853-4427-a69f-7160bdd5ebe1.png"  width=80%>

同じコードを使って、もう少し複雑な木で「勝つための一手」３個見つけた例を図５に示します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/c4b86190-f5ad-4f61-bead-5fdcc1913fce.png)

（開発環境：Google Colab、図の作成はgraphvizを使用）

この考え方はProject Euler Problem 400: Fibonacci Tree Gameを解くのに役に立ちます