■「競プロでのゲーム問題って得意？」
●「ゲーム問題ですか。ものによりますけど、Grundy 数で解ける問題は得意ですね。先輩は得意ですか？」
■「その Grundy 数がよくわからないんだよね。最後から逆にたどると解ける問題とかは分かるんだけど、Grundy 数の何が嬉しいのかよくわからない」
●「じゃあ今日はGrundy数のお話をしましょうか」
Grundy数を扱えるゲーム
●「Grundy 数は、ゲームの局面に非負整数を割り当てて必勝法や勝敗判定を行うというものです」
■「ゲームなら何でも Grundy 数が使えるの？」
●「そういうわけではないんですが、競プロで出てくるゲームなら使えるものは多いですね」
■「何か必要条件があるってこと？」
●「はい。公平ゲーム（不偏ゲーム）と呼ばれるゲームである必要があります。それにはこんな条件が必要です」
- 2人のプレーヤーは、terminal position（それ以上操作できない状態）に達するまで交互に交代しなければならない。
- あるプレイヤーの操作でterminal positionに達したとき、そのプレイヤーが勝つ（動かせなくなったほうが負ける）。
- 有限回の操作でterminal positionに達する。
- 各状態でどちらのプレーヤが手を打つにしても、動かす選択肢の集合が常に等しい。
- 常にお互い全ての情報を持っていて、偶然性に決して左右されない。
■「それ以上操作できない局面にした方が勝ちなんだね」
●「はい。”操作できなくなった方が勝ち” にしても Grundy 数を定義することはできるんですが、利点を活用するのが難しいんですよね。競プロでも普通は “操作できなくなった方が負け” になっています。また、特に重要な条件は 4 つ目です」
■「これは、ある局面の手番が先手か後手かで打てる一手が変わらないということだよね」
●「はい。オセロや将棋などは、各プレイヤーが行える手が異なるので、この定義に当てはまりません。マルバツゲーム（三目並べ）もダメですね。クアルトというゲームが条件を満たすんですが、メジャーではないですね…… 具体的なゲームの例は後で出します」
■「競プロでちょこちょここの条件が満たされているゲームを見るね」
●「また、3 つ目の条件から、同じ局面の繰り返し（ループ）が禁止されます。そのため、局面を頂点として、一手による遷移を有効辺としたグラフは、閉路が無い有向グラフ（有向非巡回グラフ）になります。英語で言うと DAG (Directed Acyclic Graph) ですね」
■「競プロだと、モノが減ったり空きマスが埋まったりして、どんどん打てる手が少なくなっていくゲームが多いね。そういうゲームは必ず有限手数で終わるね」
●「具体的なゲームの話をする前に、Grundy 数の定義についてお話しますね」
Grundy 数の定義
●「Grundy 数というのは、ゲームの局面に対して割り当てられる、0 以上の整数です」
■「指し手ではなくて、局面に割り当てられるんだね」
●「はい。そして、terminal position（決着が着く状態）の Grundy 数は 0 です。簡単にするために、terminal position でターンが回ってきたプレイヤーが負けというルールにしましょう。手が打てなければ負けです」
■「ということは、負けるときの Grundy 数は 0 ってことだね」
●「その通りです。そして、途中の状態の Grundy 数は、必勝局面で 0 以外、必敗局面で 0 になるように設定します」
■「どうやって？」
●「具体的な設定方法は後で説明しますが、ある局面から必敗局面に遷移できる場合は、その局面は必勝ですよね？」
■「えっと、必敗局面に一手で変えられる場合は、その手を打って相手にターンを渡せるから、自分は必勝ってことだね」
●「つまり、ある局面から一手で移動できる局面の中に、Grundy 数が 0 の局面があれば、その局面の Grundy 数は 0 以外にします」
■「なるほど」
●「逆に、ある局面から必勝局面にしか行けない場合は、その局面は必敗です」
■「どうやっても相手を勝たせてしまうってことだね」
●「なので、ある局面から一手で移動できる局面の中に、Grundy 数が 0 以外の局面しか無ければ、その局面の Grundy 数は 0 にします」
■「そうか、これを terminal position から逆にたどって決めていけば、全ての局面が必勝か必敗になるんだね」
●「はい。イメージとしては、こんな図になります。丸が局面、矢印が指し手です。一番下のオレンジの丸が terminal position ですね。ここが 0 で、そこから矢印を逆にたどって、0 に行ける場合は＊（0 以外の意味）として、＊にしか行けない場合は 0 にしています」
■「この図のゲームで、最初に左上の青い丸から始まる場合、先手の負けってこと？」
●「そうですね。先手は必ず＊の状態で相手にターンを渡しますが、相手は必ず 0 に戻すことができます。これを繰り返すと、一番下の状態で先手に手番が渡ります」
■「実際には、＊の状態には 1 以上の整数が割り当てられるんだよね？」
●「はい。Grundy 数の決め方は、“その局面から一手で移動できる局面の Grundy 数の mex “ です」
■「mex っていうのは確か、“集合に含まれない最小の非負整数” だったよね。minimum excluded の略だったか」
●「はい。例えば mex{1, 1, 2} = 0、mex{0, 1, 3} = 2、ということですね。また、空集合の mex は 0 です。つまり、terminal position の Grundy 数は 0 ですね」
■「この決め方だと、自動的に『 0 に行けるなら 0 以外、0 に行けないなら 0 』になってくれるね」
●「さっきの図だとこのようになります」
■「1 や 2 の値に意味はあるの？」
●「もちろんです。でも 1 つのゲームだけ扱う場合は意味がないので、とりあえず今は『Grundy 数が 1 以上の状態からは、その値未満の任意の非負整数に変化させられる。Grundy 数が 0 の状態からは 1 以上の状態にしか変化させられない』と覚えておいてください」
■「『その値未満の任意の非負整数に変化させられる』というのが重要っぽいね」
●「では、具体的なゲームの話に入りましょう」
Grundy 数の定番ゲーム「Nim」
●「Nim というゲームを考えましょう」
■「競プロerがよく『Nim に帰着できる』とか言ってるね」
●「はい。でもそういう場面では、『Grundy 数で解ける』ということを『Nim に帰着できる』と表現していて、わざわざ Nim の形に言い換えることはしていない場合が多そうですけどね」
■「どんなゲームだっけ？」
●「石が複数集められた山がいくつかあります。例えば、山が 3 個あって、それぞれの山に石が 3, 5, 2 個ある場合は、こんな状態です」
■「うん」
●「そして、各プレイヤーは自分のターンに、この山の中から1つ選んで、選んだ山にある石を 1 つ以上取り除きます」
■「上限は無いんだね。ということは、上の図だと、左の山から 1 つだけ取り除くこともできるし、真ん中の山から 5 つ全部取り除くこともできるんだね」
●「はい。ただし、複数の山から一緒に石を取り除くことはできません」
■「交互に取り除いていくんだよね」
●「はい。操作ができなかったら負けです。つまり、自分のターンが回ってきたときに、石が無くなっていたら負けです」
■「なるほど、じゃあ最後の石を取り除いたら勝ちなんだね」
●「このゲームの Grundy 数を考えてみましょう」
一山 Nim
●「まず、一山 Nim を考えましょう」
■「一山 Nim って、山が 1 つってこと？」
●「はい」
■「じゃあ初手で全部取って勝ちだよね？」
●「それはそうなんですが、せっかくなので Grundy 数を定義に従って考えてみましょう」
■「えっと、Grundy 数の定義は『可能な遷移先の Grundy 数の mex（そこに含まれない 0 以上の整数の最小値）』だよね。まず、石が 0 個なら Grundy 数は 0 だね。遷移先がもう無いから、空集合の mex になって 0 ってことでいいんだよね」
●「そうですね。石が 1 個ならどうですか？」
■「石が 1 個の状態からは、0 個の状態にしか行けなくて、行き先の Grundy 数が 0 だから、mex{0} = 1 だね。石が 1 個ならGrundy 数 は 1 だ」
●「その調子で石が 2, 3 個の場合も考えましょう」
■「石が 2 個の状態からは、石が 0, 1 個の状態に変化できるから、Grundy 数は mex{0, 1} = 2 だね。って、石の数と Grundy 数は一致するんじゃないの？」
●「その通りです！ そりゃそうですよね、という感じですが、石の数が n 個の状態からは 0〜n-1 個の状態全てに遷移できるので、Grundy 数は n になります。数学的帰納法ですね」
■「一山 Nim の Grundy 数は石の数と一致することは分かったけど、山が複数あるとどうなるの？」
●「複数山 Nim には不思議な必勝法があるんです」
Nim必勝法
●「実は、Nim の勝敗は、各山の Grundy 数を二進数で表現したときの XOR で分かるんです。
■「各山の Grundy 数っていうのは、石の数のことだよね？」
●「はい。上の例だと、3, 5, 2 すなわち 011, 101, 010 の XOR は 100=4 です。これが 0 ではないので、先手の勝ちです」
■「Grundy数について調べてるとそういう話が出てくるね。でも、どうしてそうなるの？」
●「それは、各山の石の数（Grundy 数）の XOR が、Grundy 数の定義を満たすからなんです」
■「どういうこと？」
●「Grundy 数の定義とは何でしたか？」
■「えっと、その状態から遷移できる状態の Grundy 数に含まれない最小の非負整数だよね」
●「はい。では、石数の XOR がこの条件を満たすことは、どうやって確かめたらいいですか？」
■「ある状態の Grundy 数が g だとして、『Grundy 数を g 未満の任意の非負整数に変化させられること』と『Grundy 数が g の状態には遷移できないこと』を確認すれば大丈夫か」
●「そうですね。後者は簡単です」
■「どれかの山から 1 つ以上の石を取り除いて、石数の XOR を維持できるか、か。確かに無理だね」
●「どうしてですか？」
■「1 つの値だけを変化させると、その値のいずれかの桁が変化するから、必ず全体の XOR におけるその桁が変化してしまう」
●「そうですね。1 つの山の石数だけを変えて全体の石数の XOR を変えないのは不可能ですね」
●「前者については、とりあえず『Grundy 数が 0 以外の状態でターンが回ってきたら、必ず 0 にできる』ということの証明だけやってみましょう」
■「そもそも 0 が負け状態だから、0 にできるなら 0 にするのが必勝法だね」
●「今回の場合でやってみましょう」
■「Grundy 数が二進数で 100 だから、四の位を変化させる必要がある。だから、 3 個の山や 2 個の山を減らしてもダメだね。つまり、選ぶ山は真ん中の 5 の山だね。5 の山以外の石数の XOR が 011 xor 010 = 001 だから、5 の山を 1 に変えれば、全部の XOR が 0 になるね。だから、真ん中の山から 4 個取り除いて (3, 1, 2) にすればいいんだ」
●「その通りです」
■「でも、これが必ずできる保証はあるの？」
●「はい。まず、Grundy 数を二進数で表現したときの、最も大きな桁に注目します。今回だと四の位ですね」
■「うん」
●「Grundy 数の最上位が四の位ということは、各山の石数を二進数表現したときに、四の位が 1 になる山が存在するということになります」
■「そうだね。もし全ての山の石数の、二進数表現の四の位が 0 なら、その XOR でも四の位は 0 になるからね」
●「そこで、四の位が 1 である山を選択します。ここで、選択した山の石数に Grundy 数を XOR すると、必ずもとの石数より小さくなります」
■「それはどうして？」
●「今は四の位が Grundy 数における最上位なので、Grundy 数を石数に XOR しても、四の位より大きい位の値は変化しません。そして、今は四の位が 1 である数を選択したので、 Grundy 数を XOR すると四の位は必ず 0 になります。四の位より上が変化せず、四の位が小さくなるのですから、二の位以下がどう変化しても、値としては小さくなります」
■「なるほど、Grundy 数を XOR することで変化する桁の中で最も大きな桁（今回は四の位）については、小さくなる方に変化するんだね」
●「はい。そのため、選んだ山の石数を “もとの石数 xor Grundy 数” に変化させることは Nim のルール上可能です。これをします」
■「そうすると、全体の Grundy 数はどう変化するの？」
●「Grundy 数の設定から考えて、以下の関係式が成り立ちます」
(選ばなかった山の石数の XOR) xor (選んだ山のもとの石数) = もとの Grundy 数
■「うん。Grundy 数は、全ての山の石数の XOR だからね」
●「そして今の手で、選んだ山の石数を “もとの石数 xor Grundy 数” に変化させました。なので、新しい Grundy 数はこうなります」
(選ばなかった山の石数の XOR) xor (選んだ山の新しい石数) = 新しい Grundy 数
すなわち
(選ばなかった山の石数の XOR) xor ((選んだ山のもとの石数) xor (前の Grundy 数)) = 新しい Grundy 数
■「うん」
●「そして、xor には結合法則が成り立つ（どの順番で xor を取っても同じ値になる）ので、こう考えられます」
((選ばなかった山の石数の XOR) xor (選んだ山のもとの石数)) xor (前の Grundy 数) = 新しい Grundy 数
■「この、左の 2 つの XOR は、前の Grundy 数になるね」
(前の Grundy 数) xor (前の Grundy 数) = 新しい Grundy 数
●「そして、同じ値の XOR は 0 になるので、新しい Grundy 数は 0 になります！」
■「なるほど、今回でいうと、前の Grundy 数は 3 xor 5 xor 2 = 4 だったけど、5 を 5 xor 4 の値に変えることで、新しい Grundy 数が 3 xor (5 xor 4) xor 2 = 0 になるんだね。実際、5 xor 4 = 1 で、3 xor 1 xor 2 = 0 になっているね」
●「これで、Grundy 数が 0 以外の状態にいるときに、必ず 0 の状態に一手で変化させることができるということが説明できました」
■「各山の Grundy 数（石の数）について『その値未満の任意の非負整数に変化させられる』という性質が重要なんだね」
●「はい。この考え方で、『Grundy 数が g の状態から g 未満の任意の状態に変化させられること』も証明できます」
■「今回は、Grundy 数を g から 0 にするんじゃなくて、 g 未満の非負整数 h に変化させるんだね」
●「先ほどと同じように考えます。まず、変化させる前に下の等式が成り立っています」
(選ばなかった山の石数の XOR) xor (選んだ山のもとの石数) = g（もとの Grundy 数）
■「うん」
●「次に、選んだ山の石の数を（もとの石数 xor g xor h）に変化させます。すると、こうなります」
(選ばなかった山の石数の XOR) xor (選んだ山のもとの石数 xor g xor h) = 新しい Grundy 数
■「さっきと同じように、xor の結合法則を使って、こうなるね」
左辺 = g xor g xor h = h
●「はい。これで Grundy 数を h に変化させられました」
■「ここで確認しないといけないのは、（もとの石数 xor g xor h）がもとの石数より小さいということだよね」
●「はい。これも先程と同じように考えられます。
●「今回は、g xor h の最上位が 1 になっている山を選ぶとします」
■「さっきは g の最上位を見たけど、今回は g xor h なんだね。あれ、そんな山が存在する保証はあるの？」
●「鋭いですね」
■「g は全山の石数の XOR だから、g で 1 になっているビットについては、どれかの山で 1 になっているという話だったけど、今回は h という無関係な数が入っているよね？」
●「はい。でも実は、 g xor h の最上位では必ず、g のビットが 1 で h のビットが 0 になっているんです」
■「どういうこと？ たとえば g の二進数表現が 110010 だとして、h の二進数表現が 111010 だったら、g xor h は 1000 だけど、その最上位ビット（八の位）で g は 0 だよね」
●「先輩、それだと g > h を満たしてないですよ」
■「あ、本当だ。そうか、上の位から見ていって初めて g と h で値が変わる桁は、g > h の制約から必ず g が 1 で h が 0 になるのか！」
●「その通りです。なので、g xor h の最上位が 1 になっている山が存在して、その山の石数を（もとの石数 xor g xor h）にすることは必ずできます。たとえば {5, 26, 11} の場合、Grundy 数は 5 xor 26 xor 11 = 20 です。これを 19 に変えたい場合は、 20 xo 19 = 7 に注目します。7 の最上位である四の位は Grundy 数の 20 においても 1 なので、{5, 26, 11} のいずれかでも 1 になっているはずです。今回だと 5 ですね。そのため、5 の山の石数を 5 xor 7 = 2 に減らします。そうすると、Grundy 数は 2 xor 26 xor 11 = 19 になっています。目標達成ですね」
■「なるほど、うまいね」
●「Grundy 数は、Nim 以外のゲームでも使えるんですよ」
Grundy 数の応用
●「Grundy 数の性質として重要なのは、『複数のゲームが並立しているときに全体の Grundy 数が各ゲームの Grundy 数の XOR になる』ということです」
■「なるほど、各ゲームは Nim でなくてもいいんだね」
●「はい。ただし、交互にゲームを 1 つ選んで手を進めるというルールでないといけません。また、各ゲームが最初に言った “公平ゲーム” の性質を満たしている必要があります」
■「例えばどんな問題があるの？」
●「最近だと、Google Code Jam 2019 Round 1C の 3 問目 に出ましたね」
■「このゲームだと、二次元グリッドの盤面が分断された後はそれぞれが干渉しないから、部分長方形での Grundy 数を計算できていれば良いということか」
●「はい。解説にも Grundy 数についての言及がありますね」
■「ここまで理解すれば、Grundy 数の問題が出ても大丈夫かな」
●「ゲーム問題だと、難しい場合はとりあえず Grundy 数を計算してみるのも良い手ですよ」