石取りゲーム(Nim)

  • 石が何個か積まれた山が $N$ 個ある
  • 2人で交互に石を取り合う
  • 石は、一度に同じ山からしか取れない。同じ山からなら1個以上何個取ってもよい
  • 最後に石を取った方が勝ち

というゲームには、必勝法がある。

必勝法

  • 山に残る石の数のリストを$[a_1,a_2,\ldots,a_N]$とする
  • 2進数表現の各桁の排他的論理和を計算する
    • $X = a_1 \hat{} a_2 \hat{} \ldots \hat{} a_N$
    • (例)$[5, 9, 11]$ ⇒ 2進数表現で $[101, 1001, 1011]$ ⇒ $0101 \hat{} 1001 \hat{} 1011 = 0111$ となり、$X = 111$
  • $X=0$ の状態を「必勝形」と呼ぶ
  • 初期状態で必勝形なら後手必勝、それ以外なら先手必勝
  • ゲームの途中では、常に「自分が取った後の状態」が必勝形になるように取る

証明

  1. 必勝形からどのように取ろうとも、必勝形のままにはできない
  2. 必勝形でない状態から、必勝形にする取り方が必ず1つ以上存在する
  3. 自分が最後の石を取る=自分が取った後、必勝形である
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個以上残る山」の数がポイント
  • 自分の手番の時、
    1. 石が2個以上残る山が2つ以上なら、「最後の石を取った方が勝ち」ルールと同様、必勝形になるように取る
    2. 石が2個以上残る山が1つの時、
      • 石が1個の山の数が奇数なら、2個以上残る山を全て取ることで勝利確定
      • 石が1個の山の数が偶数なら、2個以上残る山を1個残して取ることで勝利確定
    3. 石が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個の状態が必ず発生する
    • 自分が取った後の状態では発生しないので、それは相手が取った後・自分が取る時である

grundy数による一般化

このように、お互い交互に操作して状態を変化させ、それ以上操作できない状態になったら勝ちという問題の先手必勝・後手必勝は、grundy数というものを求めることで判定できる場合がある。

  • 二人で交互にやる
  • ランダム性がなく、情報はお互いにすべてわかっている
  • 無限に続かない
  • 状態は、いくつかの部分状態に分割できる

このgrundy数とは、以下によって求められる。

  • 最終状態のgrundy数を0とする
  • ある状態のgrundy数は、そこから1手で遷移できる全ての状態のgrundy数に含まれない最小の非負整数である

このgrundy数を各部分状態について求め、xorが0なら後手必勝、それ以外なら先手必勝となる。

石取りゲームに戻って当てはめると、

  • 石の山が $N$ 個ある=全体の状態
  • 石の山1つ=部分状態
    • 1度に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となる。

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