石取りゲーム(Nim)
石の山から交互に石を取っていくゲーム。三山崩し、などとも呼ばれる。
基本ルール
- 石が何個か積まれた山が $N$ 個ある
- 2人で交互に石を取り合う
- 石は、一度に1つの山からしか取れない。同じ山からなら1個以上何個取ってもよい
- 最後に石を取った方が勝ち
というゲームには、必勝法がある。
必勝法
- 山に残る石の数のリストを $[a_1,a_2,...,a_N]$ とする
- 2進数表現の各桁の排他的論理和 $X$ を計算する
- $X = a_1 \hat{} a_2 \hat{} ... \hat{} a_N$
- （例）$[5, 9, 11]$ ⇒ 2進数表現で $[101, 1001, 1011]$ ⇒ $0101 \hat{} 1001 \hat{} 1011 = 0111$ となり、$X = 111$
- $X=0$ の状態を「必勝形」と呼ぶ
- 初期状態で必勝形なら後手必勝、それ以外なら先手必勝
- ゲームの途中では、常に「自分が取った後の状態」が必勝形になるように取る
- 必勝系を「渡したら勝ち」「受け取ったら負け」なので混乱しやすい
最終状態（石が無くなった状態）は必勝形であり、自分が取った後に石が無くなる＝自分が最後の石を取ったので勝ちである。
自分が取った後を必勝形にし続けると、いつかは最終状態、つまり最後の石を取れることになる。
証明
- 必勝形からどのように取ろうとも、必勝形のままにはできない
- 必勝形でない状態から、必勝形にする取り方が必ず1つ以上存在する
1の証明
- ある山 $i$ から取るとき、自分以外の山の排他的論理和（$X \hat{} a_i$）は変わらない
- よって、操作後に必勝形にできる石の数を $a_i'$ として、$a_i'=X \hat{} a_i$
- しかし、操作前が $X=0$ だと $a_i'=a_i$ となるが、少なくとも1つは石を取らないといけないので、不可能
2の証明
- ある山 $i$ について、操作後の石の数 $a_i'$ を $X \hat{} a_i$ にできれば、必勝形となる
- 石は増やせないので、$a_i \lt X \hat{} a_i$ の山を選ぶことはできない
- $a_i \gt X \hat{} a_i$なら必ず必勝形にできる
- このような山が必ず存在することを示せればよい
実際にできる方法を示す。
X で最も左に1が立っている桁を d 桁目とする。
d
X 0001100101
d 桁目に1が立っている ai は必ず存在する（存在するからXでも立ってるのだ）
どれでもいいので1つ選ぶ
ai 1001001100
Xとaiのxorを計算する。これが操作後の ai' となるように、ai から石を取る
X^ai 1000101001
~~~|~~~~~~
1 2 3
このとき、元の ai から、
1の範囲は変わらない
2の箇所（d桁目）は必ず 1→0 に変化する
3の範囲はいろいろ
変化する最も大きい桁が $d$ 桁目であり、それが1→0に減少しているので、操作後の $a_i'$ は必ず元の $a_i$ より小さい。
逆型ルール
- 最後に石を取った（取らされた）方を負けとする
必勝法
- 最終的に、相手に、石が1個だけ残る山が1つの状態で渡すと勝利
- 「石が1個の山が2つ」は、相手が取ったら自分も取ればいいので、無視できる
- つまり、相手に、石が1個の山だけが奇数個ある状態で渡すと勝利
最初から石が1個の山しか無い場合、山の数 $N$ が奇数なら後手、偶数なら先手必勝となる。
石が2個以上の山が存在する場合を考える。
結論から言うと、逆型ルールでも必勝形を維持し続ける方が必勝である。
- 「石が2個以上残る山」の数がポイント
- 必勝の方は、自分の手番の時、
- 石が2個以上残る山が2つ以上なら、「最後の石を取った方が勝ち」ルールと同様、必勝形になるように取る
- 石が2個以上残る山が1つの時、
- 石が1個の山の数が奇数なら、2個以上残る山を全て取ることで勝利確定
- 石が1個の山の数が偶数なら、2個以上残る山を1個残して取ることで勝利確定
- 自分が受け取る時、石が2個以上残る山が1個の状態になるタイミングが必ずある
- つまり逆型ルールでも、初期状態で必勝形なら後手必勝、それ以外なら先手必勝は変わらない
- ただし、初期状態から石が2個以上の山が無かった場合、山が偶数個なら先手必勝、奇数個なら後手必勝
3の証明
- 「石が2個以上残る山」をTと呼ぶことにする
- 自分の手番でTが2個以上で受け取った時、必勝形を維持するように取れば、取った後もTは2個以上残る
- Tが1個の時、絶対にXは0にはならない
- Tにより、Xでは下から2桁目以降のどこかに1が立ち、それを打ち消してくれる他の山が存在しないので
- Tが2個以上の状態から一手で0個の状態にはできない
- 石の個数は一様に減っていくので、どこかでTが1個の状態が必ず発生する
- 自分が取った後の状態では発生しないので、それは相手が取った後・自分が受け取る時である
NimK ルール
- 一度に $K$ 個までの山を選べる
- それぞれから取る数も個別に決めてよい（ただし1個以上）
選べる山の数について、一般化されたNim。NimKと呼ばれるらしい。
必勝法
各山の石の個数を $A_i$ とし、$A_i$ を2進数表記する。bitごとに、全ての山について足し合わせる。
A1 1 0 1 1 0
A2 0 1 1 1 0
A3 1 0 0 1 0
--------------
2 1 2 3 0
足し合わせた各桁について、$K+1$ で割った余りを取る。
これが全ての桁について $0$ なら後手必勝、$0$ でない桁があれば先手必勝。
つまり、
- 全ての桁が0の状態から、1個以上取りつつ、0の状態を保つ術は無い
- 全ての桁が0の状態以外から、0に出来る方法が必ず存在する
NimK の逆型ルール
必勝判定は変わらず。（最初から石が1個の山しかないなどのコーナーケースを除く）
途中までは通常と同じく、全ての桁のmod K+1 を0にしつつゲームを進める。
必勝側は、石が2個以上残る山の数が $K$ 個以下で渡された瞬間、「石が1個だけ残る山の個数を、$K+1$ で割ったときに1余るように残して取る」とよい。
Grundy数による一般化
このように、お互い交互に操作して状態を変化させ、それ以上操作できない状態になったら勝ちというゲームにおいて 先手・後手のどちらが必勝かは、Grundy数（ニム数、Nimber）というものを求めることで判定できる場合がある。
Grundy数が使えるのは、不偏ゲームに限られる。
- 2人で交互にやる
- ランダム性がなく、情報はお互いにすべてわかっている
- 無限に続かない。最終状態に達したとき、勝者が1人決まる
- どちらが操作しても採れる選択肢は同じ
Grundy数とは、以下によって求められる。
- 最終状態のGrundy数を0とする
- ある状態のGrundy数は、そこから1手で遷移できる全ての状態のGrundy数に含まれない最小の非負整数である
- Mex（Minimum Exclude）という概念に等しい
このGrundy数を各部分状態について求め、xorが0なら後手必勝、それ以外なら先手必勝となる。
石取りゲームに戻って当てはめると、
- 石の山が $N$ 個ある＝全体の状態
- 石の山1つ＝部分状態
- 一度に一つの山しか操作できない、ということが、部分状態に分割する上で必要な条件
- 山に残る石の数＝その山のGrundy数
- 石が0個ならもう操作できない（最終状態）のでGrundy数は0
- 石が1個なら、0個にできるので、Grundy数は1
- 石が $a_i$ 個なら、0から $a_i-1$ 個の全ての状態に遷移できるので、Grundy数は $a_i$
ちゃんと当てはまっている。
Grundy数の適用例
コンテスト過去問のネタバレ注意。
取れる石の上限が設定
例えば、「1つの山からは一度に3個までしか取れない」ルールが加わったとする。
すると石山のgrundy数は、
- 0個の山は最終状態なので0
- 1個の山は1
- 2個の山は2
- 3個の山は3
- 4個の山は、「1個」「2個」「3個」のどれかにしか遷移できない
- 各grundy数は1,2,3なので、それに含まれない最小の非負整数は「0」
- 5個の山は、「2個」「3個」「4個」のどれか
- 各grundy数は2,3,0なので、それに含まれない最小の非負整数は「1」
となる。要は4で割った余りだね。
部分状態を分割
「山から石を取るのでは無く、2つの山に分ける。全ての山を石1個にした方が勝ち」というルールになったとする。
状態が分裂して増えていくタイプも、分裂した各状態のxorで考える。
ある状態を状態 A,B,C に分割するような操作があったとして、遷移先のGrundy数は $G_A \hat{} G_B \hat{} G_C$ として扱えばよい（ただし、状態AのGrundy数を $G_A$ と表す）。
- 1個の山は最終状態なので $G_1=0$
- 2個の山は(1個,1個)に遷移できる
- Grundy数は $G_1 \hat{} G_1 = 0 \hat{} 0 = 0$
- 「0」の状態にのみ遷移できるので、$G_2=1$
- 3個の山は(1個,2個)に遷移できる
- Grundy数は $G_1 \hat{} G_2 = 0 \hat{} 1 = 1$
- 「1」の状態にのみ遷移できるので、$G_3=0$
- 4個の山は(1個,3個)または(2個,2個)に遷移できる。
- (1個,3個)のとき、$G_1 \hat{} G_3 = 0 \hat{} 0 = 0$
- (2個,2個)のとき、$G_2 \hat{} G_2 = 1 \hat{} 1 = 0$
- 「0」の状態にのみ遷移できるので、$G_4=1$
- 5個の山は(1個,4個)(2個,3個)に遷移できる。
- (1個,4個)のとき、$G_1 \hat{} G_4 = 0 \hat{} 1 = 1$
- (2個,3個)のとき、$G_2 \hat{} G_3 = 1 \hat{} 0 = 1$
- 「1」の状態にのみ遷移できるので、$G_5=0$
まぁ、蓋を開けてみればつまらないが、偶数なら1、奇数なら0となる。
取れる石の上限と下限が設定
- 各山からは、$L$ 個以上 $R$ 個以下の石しか取ることはできない
競技プログラミングに出るようなNimの問題は、解けるようにできているので、 実際に実験をすると意外と単純な性質が見えることがある。
山に残る石の数ごとに、取れる石の上限と下限が設定
- 「山に残る石が $i$ 個のときは $L_i～R_i$ 個の石を取れる」という $L_1,R_1,L_2,R_2,...$ が決まっている
- ただし $1 \le L_i \le R_i \le i$
- 山にある石の個数は、たかだか $10^5$ 程度
やや高難度。
規則的な遷移にならないgrundy数は、遷移先全てのgrundy数を調べてそのMexを計算する必要があり、計算量がかさみやすい。
この問題では、計算量を現実的な程度に抑えるのに工夫が必要となる。
