石取りゲーム(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. 必勝形からどのように取ろうとも、必勝形のままにはできない
  2. 必勝形でない状態から、必勝形にする取り方が必ず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)というものを求めることで判定できる場合がある。

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

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

解法

programming_algorithm/game/nim.txt · 最終更新: 2023/11/26 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0