Grundy数

Grundy数 †

このページは競技プログラミングに興味のある方向けにGrundy数を簡単に説明するページです

Grundy数って何？ †

簡単に言えば以下の手順で決定される数です
1.これ以上ゲームが進行(遷移)しない場面のGrundy数を0とする
2.ある場面 Aでゲームが進行(遷移)するなら次の遷移先)A'をすべて列挙する
3.列挙した遷移先 A'におけるGrundy数がすべて定義されているなら(未定義のA'が存在しない状態)それらのGrundy数の集合の中に存在しないもっとも小さな非負の整数をその場面におけるGrundy数とする
4.未定義の遷移先 A'があるなら、さらに次の遷移先 A''を列挙しその遷移先 A'のGrundy数を求める

Grundy数とやらは何の役に立つの？ †

なんと！組み合わせゲームにおける公平ゲームは「状態を適切に定義」し、「各状態のGrundy数のxor」の値によってNimに帰結できるのです(ﾏｼﾞｶﾖ)。

組み合わせゲームとか、公平ゲームってなんだよ †

簡単に言えば以下の5点が満たされているゲームです
1.二人でやる
2.交互に手番がある
3.ランダム性がない
4.無限に続かない
5.情報はお互いにすべてわかっている

Nimってなんだよ †

Nimのページを読んでください。
というか、Nimのページを読んでからこのページを読んでください

3つ前(Grundy数とやらは何の役に立つの？)を読んでもよくわからないんだけど †

先述した組み合わせゲーム・公平ゲームは手数が有限です
ここで、「あるゲームをいくつかの要素の集合として見たときに、各要素についてGrundy数を割り当てることが出来る」と仮定しましょう
するとゲームの状況は「Grundy数の集合として表現することが出来る」ということになります
さらにもう一つ「自分の手番で変更できるGrundy数は一つだけ(同時に二つ以上のGrundy数を変化させることは出来ない)」と仮定しましょう
そして、初期状態を根(頂点)とし、各ノードが次の遷移先すべてを子として持つ木構造を考えたときに、末端の要素(場面)について「どちらのプレイヤーが勝つかがわかる」＆「全てのGrundy数は必ず0になる」ことがわかります
さて、これでNimに帰結できましたね

「Nimに帰結できましたね」とかいきなり言われてもよくわかんないで †

具体例を挙げて説明します。
初期状態が2つのGrundy数 (A, B)であらわされるゲームを考えます。簡単のため A=1, B=2 の時を考えます
さて、このとき次の遷移先のGrundy数の組(A', B')において(A', B') = (1, 1)になる遷移先が必ず存在します(ここ、すごく重要なのでよく考えてくださいね)
(ヒント：Grundy数が2ということは、遷移先のGrundy数に0と1が必ず存在している)
Nimの時にも述べましたが、ある数値の組のxorが0である場合、そこから1つだけ数値を変えるとそのxorは必ず0以外になるのです
つまり、上記のゲームにおいてあなたが先手である場合に「対戦相手にGrundy数のxorが0である状態を押し付ける」ことが出来ます
Nimの必勝法の基本的な考え方は「xorが0になる状態を押し付けると次の自分の手番でxorが0以外の状態になる」でしたね。それと同じ現象がGrundy数にも起こります
今度こそ、Nimに帰結できましたね

まだわからないです。もっと一般化してください †

Nimの必勝法は「山の石の数のxorが0になるようなとり方をする」という戦略でしたね
そして、そういう石の取り方が必ず存在することを証明しました
さて、あるゲームの場面がGrundy数の集合S = (a, b, c,・・・)で表現されるとき、その遷移先として
(0, b, c,・・・), (1, b, c,・・・), (2, b, c,・・・), (3, b, c,・・・),・・・(a-1, b, c,・・・),
(a, 0, c,・・・), (a, 1, c,・・・), (a, 2, c,・・・), (a, 3, c,・・・),・・・(a, b-1, c,・・・),
(a, b, 0,・・・), (a, b, 1,・・・), (a, b, 2,・・・), (a, b, 3,・・・),・・・(a, b, c-1,・・・),・・・
の全てが存在していることが保障されているはずです(Grundy数の定義をよく思い出してくださいね。)
これは各山の石の数が(a, b, c,・・・)であるNimにおける石の取り方をすべて網羅していることに等しいです
Nimにおける石の取り方をすべて網羅しているということは、「あなたの手番でGrundy数のxorが0でないならGrundy数のxorが0になるような遷移先が存在する」ということになります
今度こそ、本当にNimに帰結できましたね

Nimに帰結できてもどちらが勝者かどうかはルール次第じゃない？ †

その通りです。Grundy数を用いてNimに帰結することが出来ますが、それは勝者を求めることを保証していません
しかし、「全てのGrundy数が0の時にゲームが終了した場合にそのプレイヤーは敗北する」というゲーム条件である場合はGrundy数を用いて勝者を求めることが出来ます
と、言うより「ゲームの敗北時に必ずGrundy数が全て0である」という形になるようにGrundy数を適切に設定することが大事です