グランディ関数のソースを表示

'''グランディ関数'''（グランディかんすう、[[英語|英]]: Grundy function）は、有限個の頂点を持つ非循環な有向グラフ上で、各頂点に0以上の整数値を対応させる関数である<ref>Grundy, P. M. (1939); ''Mathematics and games'', Eureka 2,　6–8.</ref>。スプレイグ・グランディ関数とも呼ぶ。

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

==定義==
===ゲーム局面の有向グラフ===
有向グラフは頂点の集合と有向辺の集合からなる。有向辺は始点の頂点から終点の頂点へ向きを持つ辺である。終点の頂点のことを始点の頂点の次の頂点と呼ぶ。

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

===グランディ関数値===
有向グラフ''G''の上のグランディ関数''g''は、各頂点''x''に対し0以上の整数''g''(''x'')を以下のように対応させる関数である。頂点に対して次の頂点すべての集合を与える関数を関数''N''で表す。
* 頂点''x''の次の頂点が0個、つまり''N''(''x'')={ }ならば、''g''(''x'')=0である。　
* 頂点''x''の次の頂点が1個以上で、<math>N(x)</math> = {<math>y_1, y_2, ..., y_k</math>} ならば、''g''(''x'')は<math>g(y_1), g(y_2), ..., g(y_k)</math>の値と一致しない最小の0以上の整数である。

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

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

===1山くずし(毎回1枚以上3枚以下版)===
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回に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回に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枚となり後手の負けとなる。

==ゲームの和==
ゲーム<math>G_1</math>と<math>G_2</math>の和のゲーム<math>G_1+G_2</math>とは、毎回<math>G_1</math>か<math>G_2</math>のどちらか1つのゲームの手を選択してゲームを行い、自分の番で可能な手のない人の負けとなるゲームである。

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

[[スプレイグ・グランディの定理]]によると、和のゲーム<math>G_1+G_2</math>のグランディ値は、<math>G_1</math>のグランディ値と<math>G_2</math>のグランディ値の[[ニム和]]となる。

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

==脚注==
{{Reflist}}

{{DEFAULTSORT:くらんていかんすう}}
[[Category:数学に関する記事]]
[[Category:数学の問題]]
[[Category:ゲーム理論]]
[[en:Grundy function]]