Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

Grundy数を定義するとNimに帰着出来るのはなぜか

Grundy数とは

再帰的に定義される数です。ある状態から一回遷移した状態のGrundy数を集めて、そこに含まれていない非負の最小の数をGrundy数と定義します。

なぜNimに帰着出来るのか考える

ゲームの状態にGrundy数を定義すると、Nimに帰着出来ます。

以下の図を使って説明します。今、根(初期状態)のGrundy数は、3です。なぜならば、自分の遷移先で非負の最小数が3だからです。(0,1,2の次が4に飛んでいます)

f:id:akiradeveloper529:20190818175827j:plain

Grundy数を定義してNimに帰着させるというのは、この木を「石が3つの山」として扱うということです。本当は100個石があっても構わず、3として見ます。そして、Nimに帰着させます。

Grundy数の性質から、3の次は2,1,0のどれかに飛べます。これはまさにNimにおいて石をとる行為そのものです。

従って、先手から見て、どの山もGrundy数にしたNimに帰着させて勝ってるならば、その勝ちを選ぶことが出来ます。

では、先手から見て、それでは負けてしまうことがわかった場合、0,1,2以外への分岐をして勝ちにすることは出来るでしょうか?

これは出来ません。例えば、4を選んだとします。するとGrundy数の性質から、後手は次に3に遷移させることが出来ます。こうして、先手には3が必ず帰ってきます。4ではなくもっと大きい数を選んだとしても、やっぱり3を返されます。こうして負けるNimに帰着されてしまうため、負けを覆すことは出来ません。

従って、Grundy数を使ってNimをしていて勝ち負けを計算出来ることになります。

Nimの石数はGrundy数である

Nimにおいて石数がxの場合、次に遷移出来るのはx-1,x-2,...,0です。Grundy数をこの値を採用して定義出来ます。従って、これらの次の整数がxであるため、Grundy数はxです。