Grundy数のおはなし(前編)

組み合わせ論

1522

　これは AMC2023 (Advent Math Calender 2023)の1日目の記事です．2日目以降の担当の方々はとても素晴らしい記事を書かれている(断定)ので，そちらの方も是非～！

0. 導入

　今回は主に(というか全て)ゲーム理論についてのお話です．きっと後編の応用を見たら面白いと思ってもらえるんじゃないかなと思います．
　あと，これを追記して欲しいというのがあれば教えて下さい！　私が宿題をする時間を削って書きます

1. 不偏ゲーム？

　今回の本題になっているGrundy数は， $不偏ゲーム$ と呼ばれるゲームに適用することができます．では，不偏ゲームとは何なのでしょうか．ざっくり言うと "2人でして、運が関係なく、平等なゲーム" です．厳密には

・ $2$ 人のプレーヤーは，"操作できない状態"(原文 : terminal position)に達するまで交互に交代しなければならない．
・ $1$ 人のプレイヤーが"操作できない状態"に達したとき，勝者が決まる．
・有限回の操作で"操作できない状態"に達する．
・各状態でどちらのプレイヤーが手を打つにしても，動かせる選択肢の集合が常に等しい．
・常にお互い全ての情報を持っていて，偶然性に決して左右されない．　(wikipediaより)

を全て満たすものをいうそうです．

　不偏ゲーム(に限らず運に左右されないゲーム)は $2$ 人が最適な手を選べば，必ずどっちが勝つか決まります．

2. 漸化式

　ここからが本題です．

　実は全ての不偏ゲームは，漸化式(dp)によってどっちが勝てるか判定することができます．(！)　次のようなゲームを考えてみます．

　 $n$ 個の石があり，先手・後手はここから石を $1$ 個または $2$ 個交互に取る．残りの石を $0$ 個にした方が $勝ち$ である．
　両者が最適に行動するとき，どちらが勝つか？

　これを漸化式で解いてみます．
$A_{i} (i = 0, 1, \dots) = (自分から石が i 個の状態から始めるとき，自分必勝か相手必勝か)$
(つまり，自分を先手として自分が勝つか相手が勝つか)と定めます．

　まず，最初の項が分からないと何もできないので $A_{0}$ を求めます．これはあれですが，便宜上 $A_{0} = 相手必勝$ とします．(一般に，操作できなくなった状態は後手必勝とした方が都合が良いです)

　次に $A_{1}$ を考えてみます．{石が $1$ つだけ残った状態} から自分が $1$ つ石をとると｢相手のターンで{石が $0$ 個残った状態}｣になります．つまり相手にとって $A_{0} =$ 相手必勝なので， $A_{1} = 自分必勝$ ということが分かります．

　次に次に， $A_{2}$ を考えます．{石が $2$ つだけ残った状態} からは次の $2$ つの場合に分けられます．

①自分が石を $1$ 個とると {石が $1$ つだけ残った状態}　→　相手にとって $A_{1} =$ 自分必勝　つまり相手必勝
②自分が石を $2$ 個とると {石が $0$ つだけ残った状態}　→　相手にとって $A_{0} =$ 相手必勝　つまり自分必勝

　どっちを選ぶのとなりますが，｢自分｣は常に勝つために動くので，無言で自分必勝の方(②)を選びます．したがって $A_{2} = 自分必勝$ です．

　同様に $A_{3}$ もすると，

①自分が石を $1$ 個とると {石が $2$ つだけ残った状態}　→　相手にとって $A_{2} =$ 自分必勝　つまり相手必勝
②自分が石を $2$ 個とると {石が $1$ つだけ残った状態}　→　相手にとって $A_{1} =$ 自分必勝　つまり相手必勝

　これは、｢自分｣はどう頑張っても相手必勝になってしまいました．~~(悔しい)~~　つまりこの場合は $A_{3} = 相手必勝$ です．

　...という風に計算していくと， $A_{3 m + 1}, A_{3 m + 2}$ のとき自分必勝， $A_{3 m}$ のとき相手必勝となることが帰納的に分かります．なので答えは

　 $n = 3 m + 1, 3 m + 2$ のとき先手必勝， $n = 3 m$ のとき後手必勝 ( $m$ は整数)

となります．

　上で言ったことを一般化すると次のようになります．~~やっと数学っぽいことが書ける~~

　漸化式の遷移

　不偏ゲームでのある局面 $V$ (先手が行う)について，その $1$ つ後の局面としてありうるものが $V_{1}, V_{2}, \dots, V_{n}$ だとする． $V$ が先手必勝なら $f (V) = 1$ ，後手必勝なら $f (V) = 0$ とすると，
$f (V) = \overset{―}{f (V_{1}) & f (V_{2}) & \dots & f (V_{n})}$
　ただし， $0 & 0 = 0 & 1 = 1 & 0 = 0, 1 & 1 = 1,$ $\overset{―}{0} = 1, \overset{―}{1} = 0$ とする．

(上とほぼ同じ)

　 $f (V)$ の定義を，｢自分から $V$ の状態から始めるとき，自分必勝なら $1$ ，相手必勝なら $0$ ｣と言い換える．
　自分の番で $V_{1}, V_{2}, \dots, V_{n}$ にできるため，これらの局面での $f$ の値は $f (V_{1}), f (V_{2}), \dots, f (V_{n})$ である．この中に $0$ が存在するとき，それを選ぶことで｢相手にとって $0$ ｣，すなわち｢自分にとって $1$ ｣の状態をつくることができるため， $f (V) = 1$ となる．逆に全て $1$ のとき，どのように操作を行っても｢相手にとって $1$ ｣すなわち｢自分にとって $0$ ｣となるため， $f (V) = 0$ となる．

　これを使ってもう $1$ 問不偏ゲームの問題を解いてみましょう．

　 $1$ から $30$ までの整数を小さい順に先手・後手で交互に言っていく．数は一度に $1$ 個以上 $3$ 個以下言ってよく， $30$ を言ったら $勝ち$ である．
　このゲームは両者が最適に行動すると，どちらが勝つか？

※上が伝わりにくいと思うので例を出すと，

先｢ $1, 2$ ｣　後｢ $3, 4, 5$ ｣　先｢ $6$ ｣　後｢ $7, 8, 9$ ｣ ...

のような感じです．　地味

　上の命題を使います！
　
$f (n) =$ 本問題の $1$ から $n$ までの整数で $n$ を言ったら勝ちの場合で，先手必勝なら $1$ ，後手必勝なら $0$
　
とします．
　まず，便宜上 $f (0) = 0$ とします．そこから次のように計算できます．
$f (1) = \overset{―}{f (0)} = 1, f (2) = \overset{―}{f (0) & f (1)} = 1, f (3) = \overset{―}{f (0) & f (1) & f (2)} = 1, f (4) = \overset{―}{f (1) & f (2) & f (3)} = 0, f (5) = \overset{―}{f (2) & f (3) & f (4)} = 1, f (6) = \overset{―}{f (3) & f (4) & f (5)} = 1 \dots$
　勘の良い人は気付いたかもしれませんが，実はこれは $0, 1, 1, 1$ を繰り返しています．(これは実際に帰納法で示すことができます)　よって， $f (30) = 1$ なので，先手必勝と分かります．

　これで私たちは不偏ゲームを(理論上)全て判定することができるようになりました．これの上級者向けver(？)が次に紹介する Grundy数というものです．

3. Grundy数？

　Grundy数は，主に同じ不偏ゲームを同時進行するときに使うことができます(もうちょっと広く使えるかもしれません　怪しい)．次のようなゲームを考えてみます．

　机の上に $n$ 個の石が $積み重なった山$ と $m$ 個の石が積み重なった山が $1$ つずつある．先手・後手は $1$ つの山を選び，そこから石を $1$ 個または $2$ 個交互に取る．机の上の残りの石を $0$ 個にした方が $勝ち$ である．
　両者が最適に行動するとき，どちらが勝つか？

　例えば $n = m = 7$ なら，
$(7, 7) \to (7, 6) \to (7, 4) \to (6, 4) \to (6, 3) \to (4, 3) \to \dots$
という風に進んでいきます．

　今回なら最初のゲームを $2$ つ同時にやっているような感じです．こんなときはGrundy数の出番というわけです．

　Grundy数は同じゲームを同時にするときに使えると言いましたが，このゲームの｢ $1$ つ分のゲーム｣について定義されます．例えば，先程の問題 $3$ の例なら，問題 $1$ が｢ $1$ つ分のゲーム｣です．
　以下では，ある局面 $V$ のGrundy数は $g (V)$ で表します．

　まず，操作できなくなった状態のGrundy数は $0$ とします．
　今，ある局面 $V$ について，そこから遷移できる局面が $V_{1}, V_{2}, \dots, V_{n}$ だとします．すると， $V$ のGrundy数 $g (V)$ は
$g (V) = mex (g (V_{1}), g (V_{2}), \dots, g (V_{n}))$ で求めることができます．
　ここで， $mex$ とは｢その集合の中に含まれていない最小の非負整数｣と定義されているものです．例えば， $mex (0, 1, 3) = 2, mex (0, 1, 0, 2) = 3, mex (100, 100, 200, 200) = 0$ です．

　試しに問題 $1$ のGrundy数を求めてみましょう．みやすいように，

$G (n) =$ 石が $n$ 個のときのGrundy数

とします．
　まず， $G (0) = 0$ です．そこから，次のように計算できます．
$G (1) = mex (G (0)) = 1, G (2) = mex (G (0), G (1)) = 2, G (3) = mex (G (1), G (2)) = 0, G (4) = mex (G (2), G (3)) = 1, \dots$
　勘の良い人はもう気付いたかもしれません(2回目)が， $0, 1, 2$ が繰り返されています． $G (n)$ は $n$ を $3$ で割った余りになっていますね．
　実は，Grundy数は先手必勝なら $1$ 以上，後手必勝なら $0$ になります．

　｢...でこれがどう役に立つんだよ！｣と思った方も多いと思います．なんと次のような偉大な定理が知られています．

Sprague–Grundyの定理

　あるゲームの状態 $P$ がいくつかの独立なゲームの状態 $Q_{1}, Q_{2}, \dots, Q_{n}$ の和であるとき，
$g (P) = g (Q_{1}) \oplus g (Q_{2}) \oplus \dots \oplus g (Q_{n})$ が成り立つ．

　ただし， $\oplus$ は $2$ 進法での排他的論理和とする．

　じゃあ証明を...　としたいところですが，難しくてまだ理解できていません...　気が向いたら書こうと思うので，とりあえず今はこの定理を発見した方に感謝しながら食べたいと思います．

　これを問題 $3$ に使ってみます． $Q_{1}$ は $n$ 個の山， $Q_{2}$ は $m$ 個の山とすると， $G (n) \oplus G (m) \geq 1$ なら先手必勝， $G (n) \oplus G (m) = 0$ なら後手必勝となります！
(この先手必勝の条件は $n - m$ が $3$ の倍数でないことと同値になっていることも分かりますね．)