Grundy数 その1
Grundy numberについての勉強をしたので、そのまとめ(自分用のメモでもある)。ちなみにNimberとも言うみたいですね。実際にいくつかのゲームを考えながら説明をしていきます。最後の結論まで少し長いです。
そもそもGrundy数ってなんだろう
具体例は後で出すとして、とりあえずGrundy数の求め方から紹介します。
えーと・・・。これだけでは良く分かりませんね(笑)。じゃあ実際にあるゲームを考えてみます。30を言ったら負けゲーム
以前、伊東家の食卓というテレビ番組で紹介されたゲームです。ルールは次の通り。
先手は1から初め、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より大きいとき
そこから必ずGrundy数を0にするように遷移出来ます。
つまりは次の画像のような状態になります。
なので、Grundy数が0ならば相手が最適な行動をとれば負け、Grundy数が0でなければ自分が最適な行動をとれば勝ちなのである。よってこのゲームでは先手が必勝であることが分かる。
長くなってしまったので次の記事に続きます。
augusuto04.hatenablog.com