1. はじめに

Green Hackenbush は以下のルールをもつ有限型不偏ゲームです．

• 点線で表された「地面」，「点」，「点と点を結ぶ辺」からなる図形がある
• どの図形のどの部分も辺をたどると地面につながる
• 2 人のプレーヤーは交互に図形から 1 つの辺を選んで取り除く．選んだ辺を取り除くことで地面とつながらなくなってしまう部分は辺と同時に取り除かれる
• 最後の辺をとったプレーヤーの勝ち

Green Hackenbush は有限型不偏ゲームなので各図形のグランディ数を求めることができます．今回は木と呼ばれる図形のグランディ数を求めていきます．
節 2 と 節 3 では Green Hackenbush で一般に適用できる性質を確認します．節 4 と 節 5 ではこの性質を利用し具体的な図形のグランディ数を求める方法を示します．
最後に節 6 で Green Hackenbush の木のグランディ数を求める問題を紹介します． また，XOR を $\oplus$ で表します．

2. 地面の点の分割と移動

地面上にある点は，自由に移動させたり，複数の点に分割したり，逆に複数の点を 1 つにまとめたりしても，ゲームのグランディ数は変わりません．

3. コロン原理(Colon Principle)

図形 $A$ のグランディ数を $g(A)$ と表記する．
地面についている図形 $G$ と，地面には直接つながっていない図形 $H$ が 1 つの点 $a$ のみを共有してできる図形を $H \cup_a G$ と表す．
同様に，$G$ と点 $a$ のみを共有する図形 $K$ を考える．
ここで $g(H)$ は，点 $a$ を地面とみなしたときの $H$ のグランディ数とする．同様に $g(K)$ を定める．
このとき，$g(H) = g(K)$ ならば，$g(H \cup_a G) = g(K \cup_a G)$ となる．

3.1 コロン原理の証明

$H \cup_a G$ と $K \cup_a G$ の直和ゲームに含まれる辺の総数についての帰納法で示します．
辺が 0 本の場合は自明です．

示したい等式 $g(H \cup_a G) = g(K \cup_a G)$ は，$g(H \cup_a G) \oplus g(K \cup_a G) = 0$ と同値です． したがって，$H \cup_a G$ と $K \cup_a G$ の直和ゲームが後手必勝であることを示します． また，$H \cup_a G$ と $K \cup_a G$ は対称なので，$H \cup_a G$ から辺を取り除く場合のみ考えます．

先手の手は，「1. $G$ から辺を取り除く」，「2. $H$ から辺を取り除く」の 2 通りです．先手の各手について後手の必勝手を考えます．
グランディ数の定義より，グランディ数が $g$ の局面からは，$0, 1, \ldots, g - 1$ の各グランディ数をもつ局面へ遷移できることを利用します．

1. 先手が $H \cup_a G$ の $G$ から辺を取り除く場合

   • 後手は $K \cup_a G$ の $G$ から同じ辺を取り除けばいいです．
   • この操作によって点 $a$ が地面から切り離された場合は $H$ と $K$ もともに取り除かれ，残る 2 つの局面は同一になります．
     そうでなければ，$g(H) = g(K)$ を保ったまま辺の総数が減るため，帰納法の仮定を適用できます．

2. 先手が $H \cup_a G$ の $H$ から辺を取り除き，$H^\prime $ にした場合
   グランディ数の定義より，遷移先 $H^{\prime}$ が $g(H^{\prime}) = g(H)$ を満たすことはないため，以下の 2 通りに分けられます．

   • $g(H^\prime) < g(H)$ の場合

     • 仮定より $g(H) = g(K)$ なので，$K$ から辺を取り除いて遷移できる $K^\prime$ で，$g(K^\prime) = g(H^\prime)$ となるものがあります．
       後手は $K → K^\prime$ となる辺を取り除けばいいです．

   • $g(H^\prime) > g(H)$ の場合

     • $H^\prime$ から辺を取り除いて遷移できる $H^{\prime \prime}$ で， $g(H^{\prime \prime}) = g(H) = g(K)$ となるものがあります．
       後手は $H^\prime → H^{\prime \prime}$ となる辺を取り除けばいいです．

以上のいずれの場合も，後手の応手後には，対応する部分のグランディ数が等しいまま辺の総数が減った局面になります．
したがって，帰納法の仮定より，応手後の直和ゲームは後手必勝です．よって，元の直和ゲームも後手必勝です．

コロン原理を使うことで，残りの図形と $1$ 点だけを共有し，地面には直接つながっていない部分を同じグランディ数を持つより単純な図形に置き換えることができます．

4. 棒のグランディ数

まず，$1$ 本の棒のみからなるゲームのグランディ数について考えます．
棒に含まれる辺の本数を長さといいます．
長さ $m$ の棒からは，長さ $m$ 未満の棒に遷移できるため，長さ $m$ の棒のグランディ数は $m$ です．

次に，複数の棒からなるゲームのグランディ数を考えます．
各棒は独立したゲームの局面とみなせるので，複数の棒からなるゲームのグランディ数は各棒のグランディ数の XOR を取ることで求められます． 例えば，長さ $1, 1, 2$ の棒からなるゲームのグランディ数は $1 \oplus 1 \oplus 2 = 2$ です．

最後に，地面のある一点から複数の棒が伸びる図形のグランディ数を考えます．
地面の点は自由に分割して移動できるため，地面のある一点から複数の棒が伸びる図形は，複数の棒からなるゲームに帰着できます．
よって，地面のある一点から複数の棒が伸びる図形のグランディ数は，各棒の長さの XOR を取ることで求められます．

5. 木のグランディ数

以下では，地面に 1 つの頂点で接している木を考えます．地面に接している頂点を木の根とします． コロン原理を順次適用していくことによって，木のグランディ数を求められます．
地面のある一点から複数の棒が伸びている図形のグランディ数は，各棒の長さの XOR で求めることができたのでした．
コロン原理により，ある頂点から上に伸びる複数の棒は，それらの長さの XOR を長さとする 1 本の棒に置き換えることができます．
この操作を葉に近い頂点から順に繰り返すことで，木全体を 1 本の棒に変換し，木のグランディ数を求めることができます．

以下に例を示します．

• 頂点 $a$ からは，長さ $1$ の棒と長さ $3$ の棒が伸びています．よって，長さ $1 \oplus 3 = 2$ の棒に置き換えることができます．
• 頂点 $b$ からは，長さ $1$ の棒と長さ $3$ の棒が伸びています．よって，長さ $1 \oplus 3 = 2$ の棒に置き換えることができます．
• 頂点 $c$ からは，長さ $2$ の棒と長さ $3$ の棒と長さ $1$ の棒が伸びています．よって，長さ $2 \oplus 3 \oplus 1 = 0$ の棒に置き換えることができます．

以上のことからこの木のグランディ数は $0$ と求めることができました．

6. AGC017 D - Game on Tree

Green Hackenbush の木のグランディ数を利用する問題として，D - Game on Tree があります．

各頂点 $v$ について，$v$ を根とする部分木のグランディ数を $g(v)$ とします．
頂点 $v$ の子を $u_1,u_2,\ldots,u_k$ とすると，

となります．
ここで $+1$ は，$v$ と子 $u_i$ を結ぶ辺 1 本の分に対応します．
したがって，根から深さ優先探索を行い，帰りがけに各頂点の $g(v)$ を計算することで木全体のグランディ数を求められます．
AGC017 D では頂点 $1$ を根とし，$g(1) = 0$ なら Bob が，そうでなければ Alice が勝ちます．

提出コード

7. 参考

• 石取りゲームの数学
• Hackenbush