テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

Grundy数

ARC038の3問目は, Grundy数を知らないとまず解けない. 応用範囲の広い考え方なので, 今の理解をまとめておく.

もっとも参考になった文章はこちら: https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/

Grundy数は, プレイするゲームが, 「状態のみに依存して手番の勝ち負けが決定する」という性質を持っていることに依存している.

もっともシンプルな例としては, 山に積んであるコインをとっていって, 最後のコインをとった人を勝ち(or負け)とするというものである.

原始的な解法(WL-Algorithm)は, この状態変化における以下の事実を使う.

  • 次の状態変化のいずれかがloseである場合, 今の状態はwinである. ... (A)
  • 次の状態のすべてがwinである場合, 今の状態はloseである. ... (B)
boolean isWinning(position pos) {
    moves[] = possible positions to which I can move from the
position pos;
    for (all x in moves)
        if (!isWinning(x)) return true; // (A)の場合
    return false; // (B)の場合
}

しかしこの方法はもっとも簡素だが, ARC038-Cのような問題では確実にTLEする.

そこで, 今注目しているのは勝ち負けだけだから, その判定のみが出来るように状態変化を簡単にしよう!という作戦をとる. それがGrundy数である. 例えば, 通常であればコインを1個とる, 2個とる, ... という場合について枝分かれをして多大な計算が必要になる(N=100くらいでTLE不可避)が, Grundy数を導入すると, それがwinなのかloseなのかのみを判定しうる最低の情報以外は全部切り捨てるので高速に収束する(後に述べるように, 山が1つならばメモ化して同等と思う).

Grundy数の計算方法は,

  • 負けを0とする.
  • 状態変化のGrundy数集合のうち, 0以上の最低の整数を現状態のGrundy数とする. つまり, 今が1以上ならば, 0にもなりうるということであり, 上記(A)によってwinと分かる. 逆に, 現状態のGrundy数が0ならば, loseとなる.

この, Grundy数の算出方法は, 上の(A)(B)と同じことを言ってるので, Grundy数を使って勝ち負けを議論して良い.

さて, 山が複数の場合を考える. 山が1つの場合ではWL-Algorithmにメモ化を追加すればGrundy数を使う場合と変わらない性能が出ると思うが, 山が複数になるとメモ化は通用しなくなる.

ここでGrundy数がコインの減少について持つ奇跡的な性質が活きてくる. Grundy数においては, 結果的に, 以下が言える.

  • 山は独立に考えてよい
  • 山のGrundy数をxorすると, 山全体のGrundy数が求まる

理由は, xorが性質(A)(B)を保存するからである(試しにxorが0の状態からコインをいくつか増やすなり減らすなりしてみれば良い).
負けが確定した最小の最終状態からコインを左の山から置いていき, その都度Grundy数を計算していくことによって現状態を作り出したと考えてよく, 逆にこのGrundy数からどういう遷移でコインを変化させて収束しても, 最終状態にたどり着く. なので, 状態遷移の仕方(つまりゲームのルール)については何の関係もないということになる. ざっくりいうと, Grundy数が持つ性質が数学的に美しいので, どうやって足したり引いたりしても破綻しないということである.

Grundy数は美しいのでどうやって変化させても関係ないというこの事実が, この手のゲームは(複数山がある中でもっともシンプルな形態である)Nimゲームに帰着出来るというSprague-Grundyの定理に繋がる. だから, コインや豆を取り除いたり移動させるゲームを題材とした問題を見たら, 猿のようにGrundy数を計算すれば解けるのである.

以上がGrundy数に対する私のざっくりとした理解である.

ところで私は, Grundy数がどうやって生まれたものかは理解していない. 状態変化について勝ち負けを保存するために何か数学的に美しい数が必要であり, Grundy数というものを考えてみたら「たまたま」それに合致してしまった. という閃きなのだろうか?あるいはもっと理論的な積み上げによって導き出されたものなのだろうか?