石取りゲーム(Nim)
基本ルール
- 石が何個か積まれた山が $N$ 個ある
- 2人で交互に石を取り合う
- 石は、一度に1つの山からしか取れない。同じ山からなら1個以上何個取ってもよい
- 最後に石を取った方が勝ち
というゲームには、必勝法がある。
必勝法
- 山に残る石の数のリストを$[a_1,a_2,...,a_N]$とする
- 2進数表現の各桁の排他的論理和を計算する
- $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$）は変わらない
- $i$ から取った後の石の数が $X \hat{} a_i$ の時のみ $X=0$ となり、必勝形となる
- しかし、今の状態がそれであり、そこから少なくとも1つは石を取らないといけないので、必勝形は維持できない
2の証明
- ある山 $i$ について、取った後の石の数を $X \hat{} a_i$ にできれば、必勝形となる
- 石は増やせないので、$a_i < X \hat{} a_i$ の山を選ぶことはできない
- $a_i \gt X \hat{} a_i$なら、$a_i - (X \hat{} a_i)$ 個取ればその形にできる
- $X$ で最も左に1が立っている桁を $d$ 桁目とする
- $d$ 桁目に1が立っている $a_i$ が必ず存在する
- 存在しないと $X$ の $d$ 桁目が1になるはずが無い
- そのような$a_i$は、必ず$a_i \gt X \hat{} a_i$となる
- $d$ 桁目より上の部分は、$a_i$ と $X \hat{} a_i$ で等しい
- $d$ 桁目は、$a_i$ は1、$X \hat{} a_i$ は0
逆型ルール
- 最後に石を取った（取らされた）方を負けとする
必勝法
- 最終的に、相手に、石が1個だけ残る山が1つの状態で渡すと勝利
- 「石が1個の山が2つ」は、相手が取ったら自分も取ればいいので、無視できる
- つまり、相手に、石が1個の山だけが奇数個ある状態で渡す
- 「石が2個以上残る山」の数がポイント
- 自分の手番の時、
- 石が2個以上残る山が2つ以上なら、「最後の石を取った方が勝ち」ルールと同様、必勝形になるように取る
- 石が2個以上残る山が1つの時、
- 石が1個の山の数が奇数なら、2個以上残る山を全て取ることで勝利確定
- 石が1個の山の数が偶数なら、2個以上残る山を1個残して取ることで勝利確定
- 石が2個以上残る山が0個になる前に、必ず自分の手番で1個になるタイミングがある（初期状態から0,1個の場合を除く）
- つまり逆型ルールでも、初期状態で必勝形なら後手必勝、それ以外なら先手必勝は変わらない
- ただし、初期状態から石が2個以上の山が無かった場合、山が偶数個なら先手必勝、奇数個なら後手必勝
3の証明
- 「石が2個以上残る山」をTと呼ぶことにする
- 自分の手番でTが2個以上の時、
- 一度に1個の山からしか取れないので、自分が取った後でもTは最低1個残ることになる
- Tが1個の時、絶対にXは0にはならない
- Tにより2桁目以降のどこかに1が立ち、それを打ち消してくれる他の山が存在しない
- よって、必勝形を維持するように取る以上、Tが2個以上で回って来たら、自分が取った後でもTは2個以上必ず残る
- 相手の手番でも、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$
ちゃんと当てはまっている。
応用例1
例えば、「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
「山から石を取るのでは無く、2つの山に分ける。全ての山を石1個にした方が勝ち」というルールになったとする。
状態が分裂して増えていくタイプも、分裂した各状態のxorで考える。
- 1個の山は最終状態なので0
- 2個の山は(1個,1個)に遷移できる
- grundy数は(0,0)、xorを取ると0。よって2個のgrundy数は1
- 3個の山は(1個,2個)に遷移できる
- grundy数は(0,1)、xorを取ると1。3個からは「1」の状態にしか遷移できないので、grnudy数は0
- 4個の山は(1個,3個)または(2個,2個)に遷移できる。
- (1個,3個)の各grundy数は(0,0)、xorは0
- (2個,2個)の各grundy数は(1,1)、xorは0
- 「0」の状態にのみ遷移できるので、grundy数は1
- 5個の山は(1個,4個)(2個,3個)に遷移できる。
- (1個,4個)は(0,1)でxorは1
- (2個,3個)は(1,0)でxorは1
- 「1」の状態にのみ遷移できるので、grundy数は0
まぁ、蓋を開けてみればつまらないが、偶数なら1、奇数なら0となる。
応用例3
- 「山に残る石が $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を計算する必要があり、計算量がかさみやすい。
この問題では、計算量を現実的な程度に抑えるのに工夫が必要となる。
