pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Grundy数の計算方法と使い方

この記事では Grundy 数の計算方法と使い方を説明します。 Grundy 数の原理に関してはあまり触れません。

Grundy 数とは

ゲームで先手と後手のどちらが必勝なのかを判定する魔法のような数。

Grundy 数の定義

Grundy 数とはゲームの状態と一対一に対応した数であり、次のように再帰的に定義される。

  • 負けの状態なら 0
  • 遷移先の Grundy 数に含まれない最小の非負整数

現在の状態の Grundy 数が 0 なら後手必勝、そうでなければ先手必勝。

Grundy 数の計算方法

例として N 言っちゃダメゲームを取り上げる。ゲームのルールは次の通り。

  • 山に n 個の石がある
  • プレイヤーは交互に山から 1~k 個の石を取り除く
  • 取り除けなくなったプレイヤーが負け

n=6, k=3 の場合の Grundy 数の計算過程を図で示す。 左から k 番目の頂点は、山に石が k 個ある状態に対応し、頂点のラベルはその状態の Grundy 数を表している。

(1) 石が 0 個なら負けなので 0

f:id:pekempey:20160116163621p:plain:w450

(2) 遷移先の Grundy 数に含まれない最小の非負整数は 1。

f:id:pekempey:20160116163625p:plain:w450

(3) 遷移先の Grundy 数に含まれない最小の非負整数は 2。

f:id:pekempey:20160116163628p:plain:w450

(4) 遷移先の Grundy 数に含まれない最小の非負整数は 3。

f:id:pekempey:20160116163631p:plain:w450

(5) 遷移先の Grundy 数に含まれない最小の非負整数は 0。

f:id:pekempey:20160116163634p:plain:w450

(6) 遷移先の Grundy 数に含まれない最小の非負整数は 1。

f:id:pekempey:20160116163642p:plain:w450

(7) 遷移先の Grundy 数に含まれない最小の非負整数は 2。

f:id:pekempey:20160116163645p:plain:w450

たとえば石が3個のときは Grundy 数は 3 だから先手必勝で、石が 4 個のときは Grundy 数が 0 だから後手必勝だと分かる。

複数の山がある場合の Grundy

先ほどのゲームは山が 1 つだったが、これを 3 つに増やしてみる。 それぞれの山にある石の数を a, b, c とし、g(a, b, c) を計算したい。

実は山への操作が独立に行われる場合、

$$g(a, b, c) = g(a) \oplus g(b) \oplus g(c)$$

になる。n 個山があっても同様。

山が分裂する場合の Grundy

先ほどのゲームで次のような操作も許すことにする。

  • 山を 1 つ選び、その山を x1, x2, ... , xn 個の石を持つ n 個の山に置き換える。

このときの Grundy 数は次のようになる。

$$ \begin{align} g(n) &= \mathrm{mex}(g(n-1),g(n-2),g(n-3), g(x_1,x_2,\ldots,x_n)) \\ &= \mathrm{mex}(g(n-1),g(n-2),g(n-3), g(x_1) \oplus g(x_2) \oplus \cdots \oplus g(x_n)) \end{align} $$

よって山が分裂しても山が 1 個のときの Grundy 数から計算できる。

実装方法

動的計画法で求めることが多い。再帰で書くなら次のような処理になる。

def f(s):
  x = set()
  for t in (状態 s から遷移可能な状態全体):
    x.add(f(t))
  return mex(x)

遷移先の Grundy 数を管理するのに set を使ったが、Grundy 数の上限が 60 ぐらいならビットで管理した方が高速になっていい。

Grundy 数の上限は「遷移可能な状態の個数より大きくならない」ので簡単に見積もれる。 たとえば冒頭の例では、遷移可能な状態は 3 つしかないので Grundy 数はたかだか 3 であることが分かる。

動的計画法が使えない場合は、そのゲーム特有の Grundy 数の性質を見つける必要がある。 たとえば N 言っちゃダメゲームの場合、単に mod を取れば Grundy 数が求まるという性質があるのでこれを使う。

ゲーム系の問題全般に言えることだが、とりあえず実験してみると規則性が分かることが多い。

例題

Nim の問題も混ぜてある。見つかり次第追加していく。

山がひとつのゲーム

山が複数あるゲーム

山の分裂があるゲーム

Grundy 数の規則性を使うゲーム

Grundy 数の原理を考えだすとアレ。 使い方さえ分かれば十分だと思う。