🐢

ニム和とGrundy数に関するメモ

2024/06/02に公開

Ruby

ニムとは？

二人で遊ぶ石取りゲームのこと
一つの山を選んで1個以上の石を取る
それを交互に繰り返して取れなくなった方の負け

ニムで山が一つのときの勝者は？

先手。いきなり全部取れば後手は取る石がなくなるから。

ニムで同じ大きさの山が二つあったときの勝者は？

後手。先手の真似をすれば3手目に先手の取る石がなくなるから。

ニムで異なる大きさの山が二つあったときの勝者は？

先手。石の数を揃えてあとは後手の真似をすればいいから。

X-Y ニムとは？

ニムの変種で X or Y 個の石を取る

2-3 ニムで石が5個だったときの勝者は？

後手。

2 個取る → 3 個取る → 0 個
3 個取る → 2 個取る → 0 個

となって3手目に先手の取れる石がなくなるから。

mex とは？

mex = Minimum Excluded
集合に含まれていない最小の非負整数のこと

例:

集合	mex
0, 2	1
0, 1	2
	0

具体的な mex の実装は？

Array.class_eval do
  def mex
    transit = each_with_object([]) { |e, m| m[e] = true }
    transit.find_index { |e| !e } || transit.size
  end
end

[0, 2].mex  # => 1
[0, 1].mex  # => 2
[].mex      # => 0

Grundy 数とは？

X-Y ニムで言えば、

「今の個数 - X 個」のところにある Grundy 数
「今の個数 - Y 個」のところにある Grundy 数

を集合としたときの mex のこと。

Grundy 数列とは？

貰うDPの要領で作った Grundy 数を並べた配列のこと。添字が石の残り個数と対応する。

Grundy 数が 0 ならどうなる？

負ける。Grundy 数を「勝機」と考えると「勝機が 0 なので負ける」となるので覚えやすい。

Grundy 数が 0 ならなぜ負ける？

何か手を指してしまうと次の局面が相手にとって必ず有利になってしまうから。

ピンとこなくなった場合は、Grundy 数列を作る過程を思い出す。すると「今の個数 - X」と「今の個数 - Y」の場所にある Grundy 数は両方とも 0 でないはず。つまり、どちらの手を指しても「勝機がある」になってしまう。相手が。ということである。

これは将棋で先に動きたくないが一手指さないといけないからしかたなく何か指したら隙ができて相手が有利になってしまう状況に似ている。

Grundy 数列を簡単に作るには？

Range.class_eval do
  def grundy(*rule)
    [].tap do |a|
      each do |i|
        a[i] = rule.each_with_object([]) { |e, m|
          if i >= e && v = a[i - e]
            m << v
          end
        }.mex
      end
    end
  end
end

2-3 ニムで石が 8 個の場合

(0..8).grundy(2, 3)  # => [0, 0, 1, 1, 2, 0, 0, 1, 1]

3個以下でも負けとするなら？

(3..8).grundy(2, 3)  # => [nil, nil, nil, 0, 0, 1, 1, 2, 0]

範囲を 3 からとすれば対応した数列が作れる。

Grundy 数列は山ごとに求めないといけない？

一つの山だけでよい。

(0..10).grundy(2, 3)  # => [0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0]
(0..15).grundy(2, 3)  # => [0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0]

ルールが同じなら数列の並びは変わならいので最大の山だけでよい。

取れる個数の最大値が Grundy 数の最大値に影響する？

影響しない。

(0..1000).grundy(100, 200).uniq  # => [0, 1, 2]

100 or 200 個取れる場合でも数列は 0, 1, 2 だけでできている。ということは──

Grundy 数は 0, 1, 2 しかない？

そんなことはない。

(0..6).grundy(2, 3, 5)  # => [0, 0, 1, 1, 2, 2, 3]

2 or 3 or 5 個取れる場合は 3 が出てくる。ということは──

選択肢の多さが Grundy 数の最大値に比例する？

比例はしない。ためしに先頭を 1 にしてあとは 3 以上の素数にしてみると、

(0..1000).grundy(1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31).uniq  # => [0, 1]

選択肢は多いのに 2 すら出てこない。ということは──

選択肢の多さが Grundy 数の最大値に影響する？

影響する場合がある。選択肢の間隔が近いと影響しがち。

山が大きいとどうなる？

固まる。

(0..1000000000000000000).grundy(2, 3)

を実行してしまうと計算量が多すぎて固まる。

Grundy 数列には周期的パターンがある？

ある。

(0..4).grundy(2, 3).compact    # => [0, 0, 1, 1, 2]
(5..9).grundy(2, 3).compact    # => [0, 0, 1, 1, 2]
(10..14).grundy(2, 3).compact  # => [0, 0, 1, 1, 2]

2-3 ニムの場合 0, 0, 1, 1, 2 が繰り返されている。

本当に Grundy 数列は繰り返されている？

わからない。目視で繰り返されているように見えたというだけであって、証明する方法があるのかはわからない。

周期的パターンの長さは事前にわかる？

わからない。ただ、わかるときもある。たとえば 2-3 ニムのように Y = X + 1 の場合、

(0..20).grundy(1, 2)  # => [0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2]
(0..20).grundy(2, 3)  # => [0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 0]
(0..20).grundy(3, 4)  # => [0, 0, 0, 1, 1, 1, 2, 0, 0, 0, 1, 1, 1, 2, 0, 0, 0, 1, 1, 1, 2]

X + Y になっているようだ。しかし 1, 3 と 2, 4 と 3, 5 の場合、

(0..20).grundy(1, 3)  # => [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
(0..20).grundy(2, 4)  # => [0, 0, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 0, 0, 1]
(0..20).grundy(3, 5)  # => [0, 0, 0, 1, 1, 1, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 0, 0, 0, 1, 1]

2, 6, 8 になっていて法則がよくわからない。

周期的パターンは一瞬でわかる？

動的計画法のような感じで数列が決まるので一瞬では求められないんじゃないかと思っている。

山が大きい場合どうしたらいい？

0..4 までのパターンが繰り返されるのがわかったので、

grundy = (0..4).grundy(2, 3)  # => [0, 0, 1, 1, 2]

任意の個数を丸めて参照すれば、

number = 1000000000000000000
index = number.modulo(grundy.size)  # => 0
grundy[index]                       # => 0

Grundy 数が得られる。したがって 2 or 3 個取る場合、数列は 4 まででよい。

その場合、2 or 3 個が動的に変わったら？

困る。周期的パターンを目視で見つけたロジックをコード化しないといけないはず。

ニム和とは？

Grundy 数同士の XOR をした結果のこと。

ニム和を求めるメリットは？

山が複数あっても勝敗判定ができる。

Grundy 数の 2 って必要なくない？

必要ない。「0 で負け」であれば「0 以外で勝ち」なので 0 以外はすべて 1 でよい。だから、

(0..4).grundy(2, 3)  # => [0, 0, 1, 1, 2]

は、

(0..4).grundy(2, 3)  # => [0, 0, 1, 1, 1]
(0..4).grundy(2, 3)  # => [false, false, true, true, true]
(0..4).grundy(2, 3)  # => [:lose, :lose, :win, :win, :win]

でもいい。しかし、山が複数の場合におかしくなる。

Grundy 数が 0, 1 だと山が複数の場合に何がおかしくなる？

ニム和の結果がおかしくなる。2-3 ニム和で二つの山の大きさが 2 と 4 で考える。最大の 4 までの Grundy 数列を求めると、

0	1	2	3	4
0	0	1	1	2

だが、

0	1	2	3	4
0	0	1	1	1

にしてしまうと、

山2	山4	ニム和
1	1	0

先手は負けてしまう。本来は、

山4	山2	ニム和
2	1	3

で先手の勝ちになるのが正しい。したがって複数山の場合は 2 が必要になる。二択ではなく mex を使わないといけない。

ニムで Grundy 数を求めなかったのはなぜ？

残りの個数が Grundy 数そのものだから。たとえば 5 個あって 1 個以上取る場合、「ニム」は「1-2-3-4-5 ニム」と言い換えることができる。すると、

(0..5).grundy(1, 2, 3, 4, 5)  # => [0, 1, 2, 3, 4, 5]

となって個数と Grundy 数は一致する。なぜか？

3 個の位置で考えると選択肢は「1 or 2 or 3 個取れる」なので集合は 2, 1, 0 になり、mex が 3 になる。同様に 4 個なら 4 で、5 個なら 5 になるため、ニムではすでに Grundy 数が求められていると言える。

ニムで複数の山のニム和から勝敗がわかるのはなぜ？

個数が Grundy 数だから。

まとめると？

	ニム	X-Y ニム
Grundy 数列	すでになっている	必要
単数の山	0, 1, 2 … なので先手の勝ち	数列を求めて 0 なら負け (0, 1 でもよい)
複数の山	いきなりニム和でよい	数列を求めたあとでニム和

応用問題	内容
Game 6	グリッド上の駒のルールのニムに置き換える
Game 7	山が大きい場合に周期的パターンで最適化する