Grundy 数をなんとなく理解したい
■ はじめに
この記事は、Grundy 数について「Nim の各山の石の数の xor=0 でなければ先手必勝」「Nim でないゲームでも、Grundy 数を定義して xor=0 でなければ先手必勝」くらいの知識から、なぜそうなるのか、また Nim でないゲームに拡張できるのはなぜか、を直感的に理解した解釈を書いたものです。たぶん、あまり厳密ではありませんのでご注意ください。（ご指摘は歓迎しています）
なお、Nim というゲームについては既知とします。
■ Nim で 2 つの山しかない場合の必勝法
まずは簡単な場合を考えます。
山が 2 つの Nim においては、「両方の山を同じ数にして相手に渡す」ことが必勝法です。直感的に明らかかもしれませんが、これがなぜ「必勝法」として機能するかを考えてみましょう。
まず、「両方の山が同じ数」というのは、ゲームの最終形である、石がすべて無くなった場合にも当てはまる性質です。したがって、石の数が全体として減っていくことを考えると、常に「両方の山が同じ数」で渡し続ければ、最終的には「両方の山が 0 個」で渡すことになり、勝利することが出来ます。
次に、「両方の山が同じ数」という状態で相手に渡した場合、相手から「両方の山が同じ数」で返ってくることはあり得ません。さらに、「両方の山が同じ数」でない状態で返ってくれば、「両方の山が同じ数」にして渡すことが必ず可能です。
まとめると、ある時点の盤面について、「性質 A」があり
1. 「性質 A」はゲームの終着点の「負けの盤面」の状態にも当てはまる
2. 「性質 A」の盤面から 1 手で「性質 A」には遷移できない
3. 「性質 A」でない盤面からは必ず 1 手で「性質 A」に遷移できる
の 3 つの条件によって、「性質 A を満たす盤面で相手に渡し続ける」ことが必勝法として機能することが保証されます。もちろんここでは、「性質 A」とは「両方の山が同じ数」ということを表しています。
■ 寄り道：非自明な必勝法の構築への応用
Nim の場合は必勝法がよく知られています（？）が、そうでないゲームにも、上記の 3 つの条件と、盤面がループしないという条件によって必勝法を構築できる場合があります。ネタバレ防止のため、問題名が見えないようにしていますが、リンクを踏む場合はご注意ください。
■ 山が 3 つ以上の Nim への拡張
山が 2 つであれば、必勝法はかなり直感的でした。3 つ以上での必勝法を自力で見つけ出すことは相当困難であると思われますが、しかし、「xor=0 で渡す」という必勝法が知られています。先人の知恵はすごいですね。
ここでは、「xor=0」が上で挙げた 3 つの条件を満たすことを確認しましょう。
1. 「性質 A」はゲームの終着点の「負けの盤面」の状態にも当てはまる
は自明です。
2. 「性質 A」の盤面から 1 手で「性質 A」には遷移できない
もほぼ自明です。「xor=0」の状態から、いずれかの山の石の数を a→b に変えると、全体のxor（=X とします）は X から X^(a^b) になります。X=0, a!=b ではこれは 0 にはなりません。
3. 「性質 A」でない盤面からは必ず 1 手で「性質 A」に遷移できる
はどうでしょうか。少しだけちゃんと検証する必要がありそうです。
現在の X における最上位 bit を 2**k （累乗） としましょう。全体の xor がこの bit を持つことから、いずれかの山にある石の数は、この bit を持っています。この山の石の数を a とします。このとき a → a^X という手を打てれば、全体の xor を 0 に出来ることになります。そして、それには a>(a^X) であればよいです。
a^X について、反転する最上位の bit は 2**k であり、a はもともとこの bit を持っていたことから、a より小さくなることが示せます。以上で、条件 3. も確かに満たしていることが確認できました。
したがって、「xor=0」を用いた必勝法は確かに成立している、と納得できるような気がします。
↓ 条件 3. の確認の例題
【How to Win】
— riano_ (@riano_17) 2022年6月12日
N 個の山があり、i 番目の山には a_i 個の石が積まれています。あなたはこれらを使って、N 回 Nim をプレイします。但し、i 回目の対戦では i 番目の山以外の全ての山を用います。
先手はあなたです。各回の対戦で、双方最善を尽くすとき、あなたが勝利できる初手は何通りありますか。
■ Nim でないゲームへの拡張
Nim でないゲームについても、Grundy 数という概念を用いて「xor=0」 による必勝法を構築することが出来る場合があります。
ざっくり言うと、
1. 先手と後手が同じ盤面を共有し、同じ盤面に対しては同じ手を打てる
2. 盤面が不可逆である
くらいが Grundy 数を適用できる条件と認識しています。（適用できるだけであり、それが問題を解くのに有用かどうかは別問題です：後述）
各盤面に対する Grundy 数は、これまたざっくり言うと、
「その盤面から 1 手で到達可能な盤面の Grundy 数の Mex」とされています。Grundy 数を用いる（特に、a という数を割り当てる）ということは、ある盤面を「Nim における a 個の石の山」とみなすということです。これが正当であると納得するには、また少し思考を要するように思います。
まず、Grundy 数の割り当て方より、a の盤面から 1 手で 0,1,2,...,a-1 の盤面に遷移できることは保証されています。これは、a 個の石の山と同じ性質であると言えます。
しかし、Mex で割り当てましたので、a より大きい Grundy 数（b とします）が割り当てられた盤面にも遷移できる可能性があります。これでは、Nim とは別のゲームになってしまいそうです。Grundy 数を割り当てたゲームが Nim と等価であると納得するには、このような手が実質的に無意味であることを示すことが必要になりそうです。
まずは、必勝側の打ち手を考えましょう。必勝側は、a→b とするような手を選ばなくても、全体の xor を 0 にできます。これは、上で示したように Nim の手の範囲で必勝手が存在することが保証されており、さらに Nim の手と等価な手は全て実行可能であることも保証されていることから言えます。すなわち、必勝側にとっては a→b のような手を打つ必要がありません。
次に、必敗側はどうでしょうか。Nim の範囲の手では負けるのは分かっているのですから、紛れを求めて a→b のような Nim ではあり得ない手を打ってみたくもなるでしょう。しかし、これをした場合、次の必勝側の手で b→a という手が可能なのです。すなわち、全く同じ状況に回帰してしまいます。しかも、ゲーム自体は不可逆という仮定がありますから、いずれはこのような手も打つことが出来なくなります。以上から、必敗側の抵抗としても a→b のような手は無意味とわかりました。
もう一つのポイントは、a→a 、すなわち同じ Grundy 数への遷移だけは明確に排除されているということです。このことが、必勝法構築の条件 2. （すなわち、xor=0 から xor=0 に 1 手で遷移できないこと）を保証しています。
これらによって、Grundy 数を割り当てることのできるゲームが、Nim と実質等価なゲームであると納得できそうな気分になりましたので、ひとまず飲み込んでおくことにします。
■ Grundy 数の有効性とは
最後に、Grundy 数を考えることが有効な問題はどんな問題か、を考えてみます。それは一言で言うなら、「独立した山（とみなせるもの）がいくつもあり、各手番でそのうちの一つに対して手を打つ場合」だと思っています。
例えば山が 1 つであるような場合は、もちろん Grundy 数を定義することはできますが、特にそれによる嬉しさは無いように思います。しかし Nim のように、山が複数ある場合には、その全体を一つの状態量で表せてしまえるという点が非常に強力な武器となりえます。さらに言えば、xor 演算によって、2 つの山でも 3 つの山でも、1 つの山と同等の状態量で表せますので、全体の中からいくつかの山を取り出して、それを都合よくひとまとめに考える、といったことも可能です。このことは特に、山が途中で分裂してしまうような場合に、分裂した 2 つの山を xor というツールによって 1 つの山と同一視し、再帰的に Grundy 数を計算するような場合に強力な威力を発揮します。
（おわり：考えが深まったら書き足すかもしれません）
お読みいただきありがとうございました。
