グランディ関数

グランディ関数（グランディかんすう、英: Grundy function）は、有限個の頂点を持つ非循環な有向グラフ上で、各頂点に0以上の整数値を対応させる関数である^[1]。スプレイグ・グランディ関数とも呼ぶ。

グランディ関数は、役割区別のない、２人交互型ゲームで、自分の番で可能な手のない人を負けとするゲームの解析に、威力を発揮する。

定義編集

有向グラフは頂点の集合と有向辺の集合からなる。有向辺は始点の頂点から終点の頂点へ向きを持つ辺である。終点の頂点のことを始点の頂点の次の頂点と呼ぶ。

ゲームを有向グラフで扱う場合、ゲームの1つの局面が1つの頂点である。1つの頂点の次の頂点は、その局面で可能な手を1つ選択した場合の次の局面である。

有向グラフGの上のグランディ関数gは、各頂点xに対し0以上の整数g(x)を以下のように対応させる関数である。頂点に対して次の頂点すべての集合を与える関数を関数Nで表す。

頂点xの次の頂点が0個、つまりN(x)={ }ならば、g(x)=0である。　
頂点xの次の頂点が1個以上で、 $N(x)$ = { $y_{1},y_{2},...,y_{k}$ } ならば、g(x)は $g(y_{1}),g(y_{2}),...,g(y_{k})$ の値と一致しない最小の0以上の整数である。

グランディ関数値が正の場合は、この局面をもらった人の勝ち、相手の負けである。理由は適切な手を選べば次の局面のグランディ関数値を必ず0にできるからである。
グランディ関数値が0の場合は、この局面をもらった人の負け、相手の勝ちである。理由は、次の局面が存在する場合は、どの手を選んでも次の局面のグランディ関数値が正となる。次の局面が存在しない場合は、本人の負けだからである。

5枚コインの1山くずしで説明する。2人で交互に許される枚数のコインを取り除き、自分の番でコインが取れない人の負けとする。1山くずしの局面はその時点のコインの枚数で表現できる。

1回に1枚以上3枚以下のコインを取る1山くずしである。

x枚（x≧3）の局面の次の局面は、x - 1枚の局面か、x - 2枚の局面か、x - 3枚の局面である。これをN(x)={x - 1、x - 2、x - 3}と書くと、以下のようになる。
N(5)={4,3,2},N(4)={3,2,1},N(3)={2,1,0},N(2)={1,0},N(1)={0},N(0)={ }
各局面のグランディ関数値は次のようになる。すなわち、整数4で割った余りの値と一致する。
g(0)=0, g(1)=1, g(2)=2, g(3)=3, g(4)=0, g(5)=1
5枚コインの1山くずし(毎回1枚以上3枚以下版)はg(5)が正なので先手必勝となる。先手の勝ち方は次の通りである。
- 先手がまず1枚取り、後手がt 枚なら、先手が 4 - t 枚取ると、0枚となり後手の負けとなる。

1回に1枚のコインを取る1山くずしである。

x枚（x≧1）の局面の次の局面は、x - 1枚の局面となる。
N(5)={4},N(4)={3},N(3)={2},N(2)={1},N(1)={0},N(0)={ }
各局面のグランディ関数値は次のようになる。すなわち、整数2で割った余りの値と一致する。
g(0)=0, g(1)=1, g(2)=0, g(3)=1, g(4)=0, g(5)=1
5枚コインの1山くずし(毎回1枚版)はg(5)が正なので先手必勝となる。先手の勝ち方は次の通りである。
- 先手がまず1枚取り、後手が1枚、先手が1枚、後手が1枚、先手が1枚取ると、0枚となり後手の負けとなる。

1回に1枚以上の好きな枚数のコインを取る1山くずしである

x枚（x≧1）の局面の次の局面は、x - 1枚の局面か、x - 2枚の局面か、...、0枚の局面となる。
N(5)={4,3,2,1,0},N(4)={3,2,1,0},N(3)={2,1,0},N(2)={1,0},N(1)={0},N(0)={ }
各局面のグランディ関数値は次のように恒等関数となる。
g(0)=0, g(1)=1, g(2)=2, g(3)=3, g(4)=4, g(5)=5
5枚コインの1山くずし(毎回1枚以上版)はg(5)が正なので先手必勝となる。先手の勝ち方は、先手が5枚とると、0枚となり後手の負けとなる。

ゲーム $G_{1}$ と $G_{2}$ の和のゲーム $G_{1}+G_{2}$ とは、毎回 $G_{1}$ か $G_{2}$ のどちらか1つのゲームの手を選択してゲームを行い、自分の番で可能な手のない人の負けとなるゲームである。

例えば、1山くずし(毎回1枚以上版)と1山くずし(毎回1枚以上版)の和のゲームは、2山くずし(毎回1枚以上版)となる。

スプレイグ・グランディの定理によると、和のゲーム $G_{1}+G_{2}$ のグランディ値は、 $G_{1}$ のグランディ値と $G_{2}$ のグランディ値のニム和となる。

1山くずし(毎回1枚以上版)のグランディ関数が恒等関数であることと、スプレイグ・グランディの定理を利用すると、ニム和を2山くずし(毎回1枚以上版)の次の局面のグランディ値で未使用の最小の0以上の整数値として算出できる。