グランディ関数

ウィキペディア

グランディ関数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/23 08:08 UTC 版)

グランディ関数（ぐらんでぃかんすう、英: Grundy function）は、有限個の頂点を持つ非循環な有向グラフ上で、各頂点に0以上の整数値を対応させる関数である。スプレイグ・グランディ関数とも呼ぶ。 グランディ関数は、役割区別のない、２人交互型ゲームで、自分の番で 可能な手のない人を負けとするゲームの解析に、威力を発揮する。

定義

ゲーム局面の有向グラフ

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

ゲームを有向グラフで扱う場合、ゲームの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枚コインの１山くずしで説明する。2人で交互に許される枚数のコインを取り除き、自分の番でコインが取れない人の負けとする。 １山くずしの局面はその時点のコインの枚数で表現できる。

１山くずし(毎回1枚以上3枚以下版)

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

• 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枚以上3枚以下版)はg(5)が正なので先手必勝となる。先手の勝ち方は次の通りである。

先手がまず１枚取り、後手が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枚版)はg(5)が正なので先手必勝となる。先手の勝ち方は次の通りである。

先手がまず１枚取り、後手が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枚以上版)はg(5)が正なので先手必勝となる。先手の勝ち方は、先手が5枚とると、0枚となり後手の負けとなる。

ゲームの和

ゲーム$G_{1}$と$G_{2}$の和のゲーム$G_{1}+G_{2}$とは、 毎回$G_{1}$か$G_{2}$のどちらか1つのゲームの 手を選択してゲームを行い、自分の番で可能な手のない人の負けとなるゲームである。 例えば、１山くずし(毎回1枚以上版)と１山くずし(毎回1枚以上版)の和のゲームは、 ２山くずし(毎回1枚以上版)となる。

スプレイグ・グランディの定理によると、和のゲーム$G_{1}+G_{2}$ のグランディ値は、$G_{1}$のグランディ値と$G_{2}$のグランディ値のニム和となる。 １山くずし(毎回1枚以上版)のグランディ関数が恒等関数であることと、スプレイグ・グランディの定理を利用すると、 ニム和を２山くずし(毎回1枚以上版)の次の局面のグランディ値で未使用の最小の０以上の整数値として算出できる。