grundy数を習得したかった

戯言
前置き

ゲームの問題(プレイヤーが2人いて、お互いに最適な戦略を取ったとき勝つのはどちらか、みたいな問題）のときにたびたび耳にするGrundy数、これまでさっぱり何のことやら分からなかったのですが、解ける問題のレパートリーを増やすために、少しは理解しておこうと思って調べてみました。備忘録を兼ねてここに書いておこう、そうしよう。
蟻本にもgrundy numberについて書かれていますけど、今回は主にAlgorithm Tutorialsの項を利用しています。というか、このページのほぼ和訳＋自分の解釈つきみたいな流れになります。

ゲームとは

ここでいうゲームとは、

  • 2人で行う
  • 完全に情報が分かる（トランプで相手の手札が見えない、とかそういう分からない情報がない）
  • 出力は勝つか負けるかのどちらかのみ

で、こういうのは大体、交互に状態を遷移させるタイプが多い。状態には、遷移先が無い終端状態が存在する。

WL-Algorithm

一般的な名称かどうかは分からないですけど、ゲーム理論において最も単純な以下のアルゴリズムをWL-Algorithmと呼びます。

boolean isWinning(State pos){
  State[] nextStates = { posから到達できる全ての次の状態 };
  for(State s : nextStates){
    if(!isWinning(s)) return true;
  }
  return false;
}

ゲームの各状態 pos は winningとlosingのどちらかの状態をとります。winningは相手が最善を尽くしても自分が必ず勝利する状態のことです。losingは逆で、自分がどんなに頑張っても負けてしまう状態のことです。
以下のようなことが言えます。

  • posが終端状態のとき、losing
  • posからlosingであるような状態へ遷移できるとき、このposはwinning
  • posからwinningであるような状態へしか遷移できないとき、このposはlosing

これを実装したアルゴリズムが上記のWL-Algorithmです。
1番目は、終端状態で動かせないのでそれは紛れもなく負けの状態（今さらですけど、動かせなくなったら負けというゲームを想定しています）。
2番目は、遷移先にlosingが無いかを調べます。発見したらそこへ動くような手を打てば自分は勝てるので、現在の状態posはwinningとなります。
3番目は、2の逆で、あらゆる動かし方を試しても相手がwinningの状態にある場合で、これはどう頑張っても負けます。なので、この状態posはlosingです。

ゲームの状態数が少ないならこのWL-Algorithmで解くことができるでしょう。

Nim

ゲームにおいてベリー有名なのがこのNimというものでしょう。Nimとは以下のようなルールのゲームです。

  • K個のコインの山があり、各山にはn1, n2, ... , nk個のコインがある
  • プレイヤーは2人、交互にターンが回る
  • プレイヤーは自分のターンで山を1つ選び、そこから1枚以上のコインを取る
  • 最後の1枚を取ったプレイヤーの勝ち

そして、このNimの勝敗判定は xor を使うだけで分かってしまうというから驚きです。

n1 xor n2 xor ... xor nk == 0 である、且つ、このときに限り、状態はlosing

本当かよ？と思うけど本当のようです。

まず、コインの山が全て0枚のときを考えてみます。明らかに xor の結果は0です。コインが全く無い状態でターンが回ってきたのですから、この直前に相手が最後の1枚を取っていることになります。よって、この状態は既に負けている状態です。

コインがまだ残っている場合で、xorの結果が0のときを考えます。結論からいうと、ここからはwinningとなる状態にしか遷移できません。なぜなら、プレイヤーはコインを1枚以上取るからです。xorの各ビットにおいて、1の個数が変化して、1が偶数個では無くなるビットが出てきます。なんとなく例をあげてみましょう。コインの山が2個、それぞれコインが7枚あったとします。それぞれのコインの枚数を2進表記すると次のようになります。

111
111
---
000

では、コインの取り方を全通りやってみましょうか。
1枚とる場合、(6, 7)

110
111
---
001

2枚とる場合、(5, 7)

101
111
---
010

3枚とる場合、(4, 7)

100
111
---
011

4枚とる場合、(3, 7)

011
111
---
100

5枚とる場合、(2, 7)

010
111
---
101

6枚とる場合、(1, 7)

001
111
---
110

7枚とる場合、(0, 7)

000
111
---
111

おぉ、確かにどんな取り方してもxorの結果はwinning(xorの結果 != 0)になってるわよ奥様。

xorが0ではない状態を考えます。このとき、losingへ遷移する手が必ず存在します。xorの各ビットを見て、全てのビットの1の個数を偶数個にするようなコインの減らし方が見つかります。
適当な例を作ってやってみましょうか。参照ページの例をそっくり貰います。
コインの山が3つあり、(6, 9, 3)の状態を考えます。

0110
1001
0011
----
1100

色々融通のききそうな9の山からコインを取ることにしましょう（思い付き）。すると、真ん中の列のビットをいじって、xorを0にすることになるので、

0110
????
0011
----
0000

みたいな形になります。?は他2つの山の状態を見れば分かりますね。1が偶数個だったら0で、奇数個なら1です。

0110
0101
0011
----
0000

おぉ、???? → 0101と求まりましたよ。つまり、9枚のコインから4枚取ると、相手にlosing状態を押しつけることができるわけですね。

以上から、losingからは必ずwinningへ、winningからはlosingへ行けることが分かりました。また、全てのコインを取りつくすとlosing状態であるということも分かりました。1ターンにつき、コインの総数は必ず減るので、いつかは全てのコインを取りつくします。よって、相手にlosing状態を押し当て続けるといつかはコインが無くなって自分が勝利するのです。

grundy numbers

いよいよgrundy数の登場です。言いたいことは、ほとんどのゲームはgrundy数を作ってやると、Nimに帰着できて、勝敗判定がxorで分かりますよってことです。本当ですかい・・・？
例となるゲームを説明します。8x8の大きさのチェスボードとK個のナイトを使ったゲームです。
このゲームではナイトは普通とは少し違う動き方をします。以下のように4方向へのみ動きます。

x x x x x x x x
x x x x x x x x
x x o x o x x x
x o x x x x x x
x x x K x x x x
x o x x x x x x
x x x x x x x x
x x x x x x x x

ナイトは同時に同じマスに存在することが許されます。プレイヤーは交互にナイトを1つ動かして行って、動かすナイトが無くなったら負けです。

まず、このゲームはK個のボードがあり、各ボードにただ1つのナイトがいる、と置き換えても構わないです。
そして、ナイトの位置posについて以下のようにgrundy numberを割り当てると、Nimのようにゲームを扱えます（らしいですよ！）

int grundyNumber(position pos){
  nextPos[] next = { posから遷移できる全ての座標 };
  set<integer> s; // 集合を用意します
  for(position x : next)
    s.add( grundyNumber(x) ); //遷移先のgrundy numberを集合に追加します
  //集合sに含まれない非負の整数の中で最小値を、このposのgrundy numberとします
  int res = 0;
  while( s.contains(res) ) res++;
  return res;
}

K個のナイトについて、それぞれgrundy numberを求め、それらのxorを取ります。Nimと同様に、その結果が0であるならばその状態はlosing, それ以外ならwinningと判定できます。本当かよ・・・

何はともあれ、チェスボードの各座標についてgrundy numberを求めてみます（Tutorialsの方に図がありますがちゃんと手でも求めましたよ！）。左上の方から埋めていきます。

0 0 1 1 0 0 1 1
0 0 2 1 0 0 1 1
1 2 2 2 3 2 2 2
1 1 2 1 4 3 2 3
0 0 3 4 0 0 1 1
0 0 2 3 0 0 2 1
1 1 2 2 1 2 2 2
1 1 2 3 1 1 2 0

結構不規則ですねぇ。
ナイトを動かせなくなるような座標は全てgrundy numberが0になっていますね。
で、このgrundy numberがなんでNimのコイン枚数に相当するのでしょうか。Nimとこのゲームの対応をそれぞれ見てみます。

  • Nimにおいて、コインの枚数がAからBへ変化

今の座標のgrundy numberがAであるとき、grundy numberがBであるような遷移先が見つかります。なぜなら、grundy numberの求め方から、
grundy numberがA = 遷移先に0〜A-1のgrundy numberがある
ということが言えるからです。コイン枚数Bは、Aより必ず小さいので、grundy numberがBの座標が必ず見つかります。

  • grundy numberが0より大きい座標にいるとき

grundy numberを減らすような動かし方が存在し、いつかは0になります。コインの山がいずれ空になることを指します。

  • grundy numberが0の座標にいるとき

この状態からは必ず、grundy numberが1以上の座標へ遷移します。もし、grundy numberが0の遷移先があった場合、この座標のgrundy numberは0になり得ません。また、遷移先の座標から、grundy numberが0であるような座標へ1ターンで遷移することができます。

Tutorialsの説明は大体以上で終わっているんで自分の思うところを少し
座標で(a, b)と書いてあるのは、ボードの(row, column)を指していると思ってください。一番左上が(0, 0)です。

ナイトが全く動かせなくなる座標(0, 0), (0, 1), (1, 0), (1, 1)の4か所は全てgrundy numberが0です。よって、全てのナイトが終端状態になったときのgrundy numberのxorは0であり、確かにlosingになっています。
grundy numberがAの座標からはgrundy numberが0〜A-1である座標へ1ターンで到達可能です。つまり、コインがA枚ある山から1枚以上のコインを取るという状態遷移にピッタリ対応できています。Nimの場合と同様に、losingの状態からはwinningへ行くしかなく、winningからはうまく動かし方を選んで相手にlosingを押しつけることができそうです。Nimはコインが必ず減っていくのに対し、このゲームは、grundy numberが大きくなるような動かし方が存在します。Nimでいうところ、コインの枚数を増やす遷移があるのです。けれど、これは心配無用。なぜなら、そのナイトの次の遷移先の中に必ず、もとのgrundy numberと等しい座標があるからです。例えば、(5, 3)のgrundy numberは3で、そこから(3, 4)へ行くとgrundy numberが4になります。ですが、(3, 4)から(2, 2)へ動かすことでgrundy numberを同じく3に戻すことができます。コインが増えたらその分を取れば、すぐに元の状態に戻すことができるということです。
コインが増えても次のターンですぐ修正できることができそうだと分かりました。これで、なんとなくこのゲームがNimに帰着できたような感じがしてきました。

Nim チェスボードゲーム
コインの枚数 grundy number
コインの枚数nkを0〜nk-1にすることができる grundy number Aから0〜A-1のgrundy numberを持つ座標へ動かすことができる
コインは減っていくのでいつかはコインが取れなくなる ナイトはrow + columnの値を減らすような方向へしか動けないのでいつかは動かせなくなる
全てのコインの山が無くなるとxorの結果は0になる ナイトを動かせない座標のgrundy numberは0なので、全てのナイトが動かせなくなるとxorの結果は0になる
losingからはwinningへしか行けない Nimと同じ原理でwinningへしか行けなさそう(*)
winningからlosingになるような手が存在する Nimと同じ原理でそのようなナイトの動かし方が存在する
コインが増えた場合、増えた分を取ることで元に戻る grundy numberがAからBへ増えるような動き方をした場合、Bの遷移先の中にgrundy numberがAになっているような座標が必ずあるのですぐに元の状態へ戻せる

おぉ、Nimに対応づけることができたと言えそうです。
ただ、気がかりなのは(*)の部分でしょうか。grundy numberが真に減る場合はコインを取ることに相当して、真に増える場合はすぐに対処できると分かりましたが、AからAとなるような動かし方が存在しちゃった場合どうなるでしょうか？もし存在する場合、losingの遷移先にlosingが登場することになり、実はwinningだったみたいなわけわからんことになりそうです。Aが0の場合はすぐNOだと言えますね。0から0に行けるのなら、出発点の0のgrundy numberは少なくとも1ですから。Aが3の場合とかどうでしょう。自分の遷移先のgrundy numberに3があります。自身のgrundy numberも3です。まず、自身の遷移先には0〜2の座標があることは確実です。自身のgrundy numberが3ですから。あれあれ？そこに新たに、grundy numberが3である遷移先が見つかりました。つまり自身のgrundy numberは実は4だったのです！おぉ、grundy numberが全く同じになるような遷移の仕方は存在しなさそうですね。安心安心。

終わりに

一応grundy numberがNimに対応してそうだということが分かりました。あとは問題に対応できるかどうかですね。こればっかりは経験を積めとしか言えなさそうなので頑張ります。
これでちょっとはゲーム系の問題を読むのが楽しくなるかな？