grundy number

Algorithm

grundy number について知ったのでメモ．

これは

ある完全情報ゲームについて，両プレイヤーが勝つために最善の状態遷移を選択したとき，与えられた初期状態から先手が勝つか後手が勝つかを答えよ．

というような問題を解くときに使えるかもしれない考え方．

基本的に Algorithm Tutorials しか参考にしていないので，これくらいの英語なら特に苦労せずに読める人はこっちを読んだほうがいいと思います…

Nim

まずそのようなゲームの代表例として Nim というゲームについて考える．
ニム - Wikipedia
最後に必勝法として触れられているように，Nim は各山のコインの枚数をそれぞれ a[1], ..., a[n] とすると，X = a[1] ^ a[2] ^ ... ^ a[n] として，X != 0 のときに限り先手必勝であることが知られている．

このようなゲームにおいて，状態は大きく2つに分けることができる．

  • losing: どうがんばっても相手がうまくプレイすると負ける状態
  • winning: うまくプレイすると相手がどうがんばろうとも勝てる状態

言い換えると，

  • losing: どうがんばっても winning にしか遷移できない
  • winning: うまく手を選ぶと losing に遷移できる

となる．よって，初期状態が losing か winning かを判定できれば，先手が勝つか後手が勝つかわかるということになる．

ではなぜ X == 0 だと losing で，逆に X != 0 だと winning であるか．

X == 0 だと losing

X == 0 の状態で自分の番が回ってきたときを考える．
自分はどれかの山から1枚以上のコインを取り除かなければならないので，取り除いた後の X は必ず 0 以外になる．

X != 0 だと winning

X != 0 の状態で自分の番が回ってきたときを考える．
X の立っているビットのうち最上位のビット(これを k ビット目とする)に注目し，k ビット目が立っている山の一つ(これを i とする)を選び，プレイヤーはここからコインをとる．a[i] からは好きな数だけ引くことができるので，うまく引く数を選ぶことで k ビット目を 0 にしつつ，任意の j (< k) ビット目を任意に変えることができる．よって，a[i] からうまく引くことで X を 0 にできる．


よって，どこか不思議なかんじがするが，xor によって先手必勝か後手必勝かを初期状態から判定することができる．

grundy number

grundy number というものを用いることで，この考えを Nim 以外にも応用できる．
Nim の性質で xor による判定に関わる重要な点は

  • 全部の山が0になったら負け
  • 1つの山からしかコインを取れない
  • 1つの山から1以上の好きな数だけ引ける

というようなものだった．

これらを保持するために，grundy number を

「ある状態の grundy number が n」 := 「その状態から n 未満の任意の i (>= 0) について，grundy number が i であるような状態に遷移できる」

となるようにつける．最終状態の grundy number は 0 になる．

例題として，TopCoder のと一緒だとつまらないのでほぼ同じような POJ の問題を解いてみる．

2425 -- A Chess Game

頂点数 N の DAG が与えられ，M 個の駒がそれぞれどこかの頂点に置かれている．プレイヤーは1ターンに1つの駒を有向辺に沿って隣りの頂点に動かす．どの駒も動かせなくなったプレイヤーの負け．N <= 1000, M <= 10

というような問題．
これはある駒に注目すると(Nim の「山」に相当する)，上の定義に従って頂点 x の grundy number を

int memo[1000];
Graph g;
int grundyNumber(int x)
{
  int& n = memo[x];
  if (n != -1) {
    return n;
  }
  bool s[1000];
  fill_n(s, 1000, false);
  for (int y : g.nodes_from(x)) {
    s[grundyNumber(y)] = true;
  }
  for (n = 0; s[n]; ++n);
  return n;
}

というようなかんじのメモ化再帰で求めることができる．すると，最初の駒の位置が x[1], ..., x[M] のとき，grundyNumber(x[1]) ^ ... ^ grundyNumber(x[M]) == 0 のときに "LOSE"，そうでないときは "WIN" と答えればよい．


類題: 2311 -- Cutting Game
ちょっと工夫は必要だが，これも grundy number を利用して解ける．