はじめに

先日参加していた競技プログラミングコンテスト，ARC（AtCoder Regular Contest）でGrundy数に関する問題が出ました． この記事では私自身の勉強とまとめのため，Grundy数とSprague-Grundy定理について説明していきます．¹²

最初は一般の不偏ゲームについて述べて，後で上記の具体的な問題の設定を例にあげます．具体例を先に確認したい方は後半から読まれても良いかもしれません．(疲れたのでいったん一般の不偏ゲームについての議論のみで公開しちゃいます．その問題設定を用いた具体例の説明はやる気が出たら多分週末に書きます．)．

不偏ゲーム（Impartial Game）

ここでとりあげる 不偏ゲーム（Impartial Game）³ とは，次のような特徴をもつゲームのことを呼びます：

• 2人のプレイヤーがおり，交互に手番プレイヤーとなって行動を行う．
• 生じうるゲーム状態，および可能な行動の数は有限．
• ゲーム状態ごとに可能な行動が定められ，手番プレイヤーの操作によって別のゲーム状態に遷移し，相手の手番となる．
• 初期状態，および先手プレイヤー（最初に行動を選択する人）が定められている．
• 可能な行動のない状態（終了状態）がある．
• 終了状態に至ったときに手番プレイヤーであったプレイヤーの負け（自身のの行動によって終了状態に遷移したプレイヤーの勝ち），
• ゲームの状態や行動は両者間ですべて確認され（完全情報），また状態遷移に不確実性を含まない．
• どのような行動が取られても必ず有限回の行動で終了状態に至る．⁴

モデル

この不偏ゲームは，以下のようにフォーマルな数理モデルで定式化できます．

定義 1． 不偏ゲーム：$I = (S, s_0, T)$ は

• $S$：とりうる全てのゲーム状態からなる有限集合．
• $s_0 \in S$：初期状態．
• $T:S \to 2^S$：状態 $s$ から手番プレイヤーの行動によって遷移できる状態の集合 $T(s) \subseteq S$ をあらわす写像．

で表される．

戦略

ここでプレイヤーにとっての戦略（Strategy）を定義します．

定義 2． 不偏ゲーム$I = (S, s_0, T)$におけるプレイヤー$i$の戦略とは，与えられた状態から遷移先状態をしめす写像 $ \beta_i:S \to S\cup \{ \emptyset \} $ で，

• もし $T(s) \ne \emptyset$ （終了状態でない）なら，$\beta_i(s) \in T(s)$．
• もし $T(s) = \emptyset$（終了状態）なら，$\beta_i(s) = \emptyset$．

を満たすもののことをいう．

必勝戦略

必勝戦略とはなにかを定義しましょう．

先手プレイヤーを $A$，後手プレイヤーを $B$とし，それぞれについて戦略 $\beta_A, \beta_B$ が与えられたとします．この戦略のもとでゲームがが進められたとき，状態は

• $s_1 = \beta_A(s_0)$,
• $s_2 = \beta_B(s_1)$,
• $s_3 = \beta_A(s_2)$,
• …

と遷移していきますが，有限回でゲームは終了するので，どこかである $k$ が存在して

• $\beta_i(s_k) = \emptyset$

となり，このときの手番プレイヤー $i$ が負け，もう一方のプレイヤーが勝利します．

したがって，戦略の組 $(\beta_A, \beta_B)$ が与えられると勝者が決まるため，これを勝者関数とすることにします．

• $W(\beta_A, \beta_B) \in \{A, B\}$：戦略 $\beta_A, \beta_B$ が与えられたときの勝者．

するとプレイヤー $i$ の必勝戦略とは，以下のように定義することができます．

定義 3． 不偏ゲーム $I = (S, s_0, T)$ において，戦略 $\beta_i^*$ がプレイヤー $i$ の必勝戦略であるとは，もう一方のプレイヤー $j$ の任意の戦略 $\beta_j$ に対してもプレイヤー $i$ が勝者となること，つまり

$$ W(\beta_i^*, \beta_j) = i, ~ \forall \beta_j $$

が成り立つことをいう．

必勝戦略の存在性

では必勝戦略なんて存在するのか，という話なんですが，先手と後手の両方に必勝戦略が存在するということはもちろんありません（両者が必勝戦略を取った場合を考えると，どちらか一方は負けるので必勝戦略であることに矛盾します）．

ただし，どちらか一方には必ず必勝戦略がが存在します．

定理 1． 不偏ゲームには，先手プレイヤーと後手プレイヤーのどちらか一方に必ず必勝戦略が存在する．

不偏ゲームを含むより一般的な二人逐次手番完全情報有限確定ゲームにおけるZermeloの定理からただちに成り立ちます．⁵⁶

Grundy数

さて，やっとここから本題です．この不偏ゲームはGrundy数によって分析できます．

不偏ゲームの Grundy数 $g : S \to \mathbb{Z}_{\ge 0}$ （あるいはNim数，Nimber，Sprague-Grundy関数，など）は，各状態に対して以下のように帰納的に定められます．⁷

• $S^{(0)} = \{s \in S \mid T(s) = \emptyset \}$ （終了状態の集合）．
• 各 $k = 0, 1, 2, \dots $ について, 以下を繰り返し行う．
  • 各 $s \in S^{(k)}\setminus S^{(k-1)}$ について，以下のように定める．⁸
    • $E = \{ g(s’) \mid s’ \in T(s)\}$ （つまり，$s$ からの遷移先状態におけるgrundy数の集合）として， $$ g(s) := \mathrm{mex} ~ E $$ とする（$ \mathrm{mex} $ は最小除外数（the minimum excluded value），つまり $\mathrm{mex} ~ E = \min \mathbb{Z}_{\ge 0}\setminus E$）．
  • $S^{k} = S$ なら終了．そうでないなら $S^{(k+1)} = \{s \in S \mid T(s) \subseteq S^{(k)} \}$ として次の $k$ に進む．

不偏ゲームは有限回の行動で必ず終了するので，終了状態から遡ることで必ず全ての状態にGrundy数を定めることができます．

このGrundy数から，以下のことが示されます:

定理 2. 不偏ゲーム $I = (S, s_0, T)$ と状態 $s \in S$について，

• $g(s) \ne 0$ なら，そこからの手番プレイヤーの必勝戦略がが存在する（つまり，$I’ = (S, s, T)$ に先手必勝戦略がが存在する）．
• $g(s) = 0$ なら，そこからの非手番プレイヤーの必勝戦略が存在する（つまり，$I’$に後手必勝戦略がが存在する）．

証明． 上記のgrundy数の定め方の中の $k$ についての帰納法によって示します．

• $k = 0$ について：状態 $s \in S^{(0)}$ は，すべて終了状態です．したがって，$s$ においては手番プレイヤーの必敗なので，非手番プレイヤーの必勝戦略が存在します．また定義より，$E = \emptyset$ なので $g(s) = \mathrm{mex}~E = 0$ です．よって，$s \in S^{0}$ については主張が成り立ちます．
• $k \ge 1$ について：すべての $s’ \in S^{k-1}$ において主張が成り立っていると仮定します．各 $s \in S^{(k)}\setminus S^{(k-1)}$ について，$g(s) = 0$ の場合と $g(s)\ne 0$ の場合について考えます．
  • $g(s) = 0$ の場合：任意の $s’ \in T(s)$ について，$g(s’) \ne 0$ であり，またその $s’$ らはすべて $s’ \in S^{(k-1)}$ なので，$s’$ 以後は手番プレイヤーの必勝戦略が存在します．よって, $s$ からは非手番プレイヤーの必勝戦略が存在します．
  • $g(s) \ne 0$の場合：ある $s’ \in T(s)$ が存在して，$g(s’) = 0$ です．したがって $s’$ からは非手番プレイヤーの必勝戦略がが存在するので，今の $s$ からは $s’$ に遷移させるような現手番プレイヤーの必勝戦略が存在します．$\Box$

Sprague-Grundy 定理

不偏ゲームが $2$ 個 $I_1 = (S_1, s_1, T_1), I_2 = (S_2, s_2, T_2)$ の二つ与えられ，以下のゲームを行うこととします．

• 手番プレイヤーは, $I_1, I_2$ のうちいずれかを選び，行動を行います．
  • ここで選んだ方を $I_j = (S_j, s_j, T_j)$ とし，手番プレイヤーが選んだ遷移先を $\bar{s}_j \in T_j(s_j)$ とする．
  • $I_j$ の状態を $\bar{s}_j$ に更新し，$I_j = (S_j, \bar{s}_j, T_j)$ とする．
• 更新されたら，相手の手番となる．
• 自身の手番となったときに，$I_1, I_2$ の両方で行動が不可能である場合，その手番プレイヤーの負けとする．

このようにして2つの不偏ゲームから作られるゲームも不偏ゲームとなります．これを $I = I_1 + I_2$ と書くことにすると，

• 状態集合： $S = S_1 \times S_2$
• 初期状態： $s = (s_1, s_2)$
• 遷移関数： $T(s) = \{ (\bar{s}_1, \bar{s}_2) \in S \mid \left(\bar{s}_1 = s_1 ~ \mathrm{and} ~ \bar{s}_2 \in T_2(s_2)\right) ~ \mathrm{or} ~ \left(\bar{s}_2 = s_2~ \mathrm{and}~ \bar{s}_1 \in T_1(s_1)\right) \},$ (for $s = (s_1, s_2)$)

となります．

そのようにして作られた不偏ゲームについて，以下が成り立ちます：

定理 3．（Sprague-Grundy） 二つの不偏ゲーム $I_1, I_2$ についてgrundy関数をそれぞれ $g_1,g_2$ とし，またそれらから作られる不偏ゲーム $I = I_1+I_2$ のgrundy関数を $g$ とする．このとき任意の状態 $s = (s_1, s_2)$ について $$ g(s) = g_{1}(s_1) \oplus g_2(s_2) $$ が成り立つ（ここで $x\oplus y$ は$x,y$を二進数表現したときのビットごとの排他的論理和）．

証明. 定理2と同様，Grundy数の定義で出てきたステップ数 $k$ についての帰納法で示します．

• $k = 0$ の場合：$s = (s_1, s_2) \in S^{(0)}$ とします．このとき, $s$ は $I$ の終了状態なので，$s_1, s_2$ はそれぞれ $I_1, I_2$ の終了状態です．したがって，$g(s) = g_1(s_1) = g_2(s_2) = 0$ なので成り立ちます．
• $k \ge 1$ の場合：任意の $s’ \in S^{(k-1)}$ において主張が成り立っているものと仮定します． $s \in S^{(k)}$をとります．示すべきことは以下の二つです．
  • (1)「$s$ からの任意の遷移先 $\bar{s} \in T(s)$ において $g(\bar{s}) \ne g_1(s_1)\oplus g_2(s_2)$であること」を示します．
    • 任意の遷移先 $\bar{s}$ をとります．$\bar{s}_1, \bar{s}_2$ のどちらか一方のみ $s_1,s_2$ と異なるので，仮に$\bar{s}_1 \ne s_1$かつ$\bar{s}_2 = s_2$としましょう．すると，$g_1(\bar{s}_1) \ne g_1(s_1)$ なので，$$g(\bar{s}) = g_1(\bar{s}_1)\oplus g_2(\bar{s}_2) = g_1(\bar{s}_1)\oplus g_2(s_2) \ne g_1(\bar{s}_1) \oplus g_2(\bar{s}_2) $$ となります．$\bar{s}_2$ のみ異なるケースも同様です．
  • (2)「$0 \le z < g_1(s_1)\oplus g_2(s_2)$ なる任意の整数 $z$ に対して，ある状態 $\bar{s} \in T(s)$ が存在して，$g(\bar{s}) = z$ となること」
    • $g_1(s_1)\oplus g_2(s_2) = y$ とし，$0 \le z < y$ なる整数 $z$ を一つとります．また，$z$ と $y$ を二進数表示したときにビット値の異なるような最も大きい桁番号を $\ell$ とします． すると，$y_\ell = 1$ かつ $z_\ell = 0$ です（そうでなければ大小が逆転します）， したがって，$g_1(s_1), g_2(s_2)$ のどちらか一方のみ，二進数表記時の $\ell$ 桁目が $1$ となります． それが仮に $g_1(s_1)$ で成り立つとしましょう ($g_2(s_2)$ なら以下 $I_2$ について読み替えれば同様に成り立ちます)． $x = g_1(s_1)$ とし，$y$ と $z$ の二進数表記時にビット値の異なる桁について $x$ のビット値を反転させたものを $\bar{x}$ とすると，必ず $\bar{x} < x$ となります（なぜなら，$\bar{x}$と$x$で異なる桁で最も大きいのは $\ell$ で，構成より $x_\ell = 1, \bar{x}_\ell = 0$ なので）． したがって，$\bar{x} = g_1(\bar{s}_1)$ となるような $I_1$ の状態 $\bar{s}_1 \in T_1(s_1)$ が存在するため，$\bar{s} = (\bar{s}_1, s_2)$ とすると， $$g(\bar{s}) = g_1(\bar{s}_1) \oplus g_2(s_2) = \bar{x} \oplus g_2(s_2) = z$$ となります（最後の等号は $\bar{x}$ の構成より）．
  • よって(1)-(2)より，$s \in S^{(k)}$ について $g(s) = g_1(s_1) \oplus g_2(s_2)$ となります．$\Box$

もちろん，以上の議論を $n$ 個の不偏ゲーム $I_1, I_2, \dots, I_n$ の和にただちに拡張することができ，$I = I_1 + I_2 + \dots + I_n$ の不偏ゲームについて，そのgrundy数は $$ g(s) = g_1(s_1) \oplus g_2(s_2) \oplus \dots \oplus g_n(s_n) $$ となります．

具体例：ARC168B

To be written（多分）．

おわりに

ここ間違ってる！・ここがわかんない！・こう書いた方がわかりやすくなりそう！などご質問・ご意見・ご罵倒ございましたらぜひみーとみまでご連絡ください！！