不変ゲームの定義

二人零和有限確定完全情報ゲームで、どの盤面であっても、プレイヤーによって取りうる操作の選択肢は変わらないゲーム。

（チェスは白番・黒番で取りうる操作が変わるので不変ゲームではない）

Grundy数の理論

• 普通、自分が手番のとき、Grundy数が0なら負け、非0なら勝ち

  • 勝ち負けが逆な場合もある（例: Misere Nim）

• Grundy数の定義

  • 終了状態の Grundy数を0とする。
  • ある状態PでのGrundy数 = mex{ P’ の Grundy数 | P’ は P から1手で到達可能}
    • 例えば grundy数が5だったら、1手で0から4のすべてのgrundy数に遷移できる。

• Nim のように山が複数あるみたいな状態では、それぞれの山で grundy 数を独立に考えて、xor sum を取ると全体の grundy数になる (Sprague Grundy Theorem )

• 具体例

  1001 (9)
  1100 (12)
  0110 (6)
  ---- xor
  0011
  
  0110 (6) を 0101 (5) にすると、xor sum を 0にできる(相手に grundy数0を押し付けられる)
  (0011 は2桁目が1の立っている最上位bitなので、2桁目に1が立っている 0110 (6) を操作する)
  
  1001 (9)
  1100 (12)
  0101 (5)
  ---- xor
  0000
  
  ここからどのように遷移しても、xor sum は非0になってしまう（grundy数が0だと、相手にgrundy数0を押し付けられない)
  

• grundy数や mex の定義の気持ちを図で説明

  

個数制限ありの Nim における Grundy 数

• K個まで取れる Nim の Grundy数: g(x) = x mod (K+1)
• L個以上、R個以下取れる Nim の Grundy数
• Kの倍数だけ取れる Nim の Grundy数
• 2の倍数か3の倍数だけ取れる Nim の Grundy数
• mべき(1, m, m^2, …) だけ取れるNim
• 取れる個数が有限集合 $S$ で与えられた Nim
• 取れる個数が補有限集合で与えられた Nim (All-but Nim)