−目次

石取りゲーム(Nim)

石取りゲーム(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個以上残る山」の数がポイント
必勝の方は、自分の手番の時、
1. 石が2個以上残る山が2つ以上なら、「最後の石を取った方が勝ち」ルールと同様、必勝形になるように取る
2. 石が2個以上残る山が1つの時、
  - 石が1個の山の数が奇数なら、2個以上残る山を全て取ることで勝利確定
  - 石が1個の山の数が偶数なら、2個以上残る山を1個残して取ることで勝利確定
3. 自分が受け取る時、石が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）というものを求めることで判定できる場合がある。

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を計算する必要があり、計算量がかさみやすい。

この問題では、計算量を現実的な程度に抑えるのに工夫が必要となる。

解法

$i$ 個の状態からは $(i-R_i)～(i-L_i)$ 個の状態に遷移できる。
この区間のgrundy数のMexが、 $i$ 個の場合のgrundy数になる。

 i            0   1   2   3   4   5   6   7
Li            -   1   1   1   1   1   2   3
Ri            -   1   2   3   1   2   5   5
遷移できるi   -  0~0 0~1 0~2 3~3 3~4 1~4 2~4
grundy数      0   1   2   3   0   1   4   1

$i$ 個の状態のgrundy数を求めるのには、愚直には、 $R_i-L_i+1$ 個の遷移先全てのgrundy数を調べる必要がある。
つまり、最大の山の石数を $A_{\max}$ とすると、そこまでのgrundy数を求めるのに、 $L_i,R_i$ の与えられ方にもよるが $O(A_{\max}^2)$ かかる。石の数が大きくなってくると非常に時間がかかってしまう。

求めたいのがMinやMaxなら、セグメント木を用いて区間のそれを高速に求めることができるが、Mexはできない。
（ $\{0,1,3\}$ のMexは $2$ , $\{2,4,5\}$ のMexは $0$ 、この2つの和集合のMexは $6$ となる。しかし $2$ と $0$ という情報だけから $6$ を導き出すことはできないため、元の集合そのものの情報が必要になり、計算量が改善しない。）

ここでは、「最も直近に出てきた、grundy数が $g$ となる箇所 $i$ はどこか？」を、 $g$ をindexとしてMinセグメント木で管理する。

$i$ の小さい方から順に処理していく。
$i$ のgrundy数が $m+1$ となるとなるということは、 $i-L_i$ の更新が終了したタイミングで、以下の2つが満たされている状態と言い換えられる。

$0～m$ について、そのgrundy数が最も直近に出てきたindexを求め、その中の最小値が $i-R_i$ 以上
$m+1$ については、直近のindexが $i-R_i$ 未満（もしくはまだ出てきていない）

そのような $m$ は、Minセグメント木で二分探索することで $O(\log{A_{\max}})$ で求められる。

$i$ の小さい方から以下を処理していく
- $i$ まで到達した段階で、 $i$ のgrundy数 $g$ は求まっている
- Minセグメント木の、indexが $g$ の項を $i$ に更新する
- $i=j-L_j$ である $j$ について、二分探索でgrundy数を求める

としていくと、全体で $O(A_{\max}\log{A_{\max}})$ で求められる。