へなちょここーだー

プログラミング初心者がtopcoderなどの競技プログラミングに挑戦。勉強したアルゴリズムなどを書いていきます。現在topcoder緑でcodeforces青。どちらもDiv1昇格を目指しています。

Grundy数 その1

Grundy numberについての勉強をしたので、そのまとめ(自分用のメモでもある)。ちなみにNimberとも言うみたいですね。実際にいくつかのゲームを考えながら説明をしていきます。最後の結論まで少し長いです。

そもそもGrundy数ってなんだろう

具体例は後で出すとして、とりあえずGrundy数の求め方から紹介します。

ある状態におけるGrundy数はそこから遷移できる状態におけるGrundy数以外の最小の0以上の整数。
えーと・・・。これだけでは良く分かりませんね(笑)。じゃあ実際にあるゲームを考えてみます。

30を言ったら負けゲーム

以前、伊東家の食卓というテレビ番組で紹介されたゲームです。ルールは次の通り。

先手と後手が交互に1つ以上3つ以下の整数を1から順に30まで言っていく。
先手は1から初め、30を言った人が負け。
例えば、先手:1, 2, 3 後手:4 先手:5, 6 後手:7, 8, 9 ・・・と続けて30を言った人が負けです。

とりあえずGrundy数の求め方

このゲームにおけるGrundy数をまずは計算してみます。

次に言う数 1 2 ・・・ 22 23 24 25 26 27 28 29 30
Grundy 1 0 ・・・ 0 3 2 1 0 3 2 1 0

まずは30から考えます。ここから遷移(たどり着く)数はないので最小の0以上の整数は0。
29からは30に遷移でき、このGrundy数は0である。よってこれ以外の最小の0以上の整数は1。
28からは29, 30に遷移でき、これらのGrundy数である1, 0を除く最小の0以上の整数は2。
27からは28, 29, 30に遷移でき、これらのGrundy数である2, 1, 0を除く最小の0以上の整数は3。
26からは27, 28, 29に遷移でき(3つまでしか数は言えないため30へは遷移できない)、これらのGrundy数である3, 2, 1を除く最小の0以上の整数は0。
これを繰り返し、すべてのGrundy数を求めます。

で、ここから何が分かるの?

実は自分の手番におけるGrundy数を見えると、そこからお互いが最適な行動をしたときの勝敗が分かるのです!Grundy数が0ならばそのときに手番の人は負けます。Grundy数が0より大きければそのときに手番の人が勝ちます。ではなぜなのでしょうか。次の2つの場合について考えます。

そこから遷移できる状態のGrundy数はすべて0より大きいです。

  • Grundy数が0より大きいとき

そこから必ずGrundy数を0にするように遷移出来ます。
つまりは次の画像のような状態になります。
f:id:augusuto04:20150503233056j:plainf:id:augusuto04:20150503233104j:plain
なので、Grundy数が0ならば相手が最適な行動をとれば負け、Grundy数が0でなければ自分が最適な行動をとれば勝ちなのである。よってこのゲームでは先手が必勝であることが分かる。

長くなってしまったので次の記事に続きます。
augusuto04.hatenablog.com