グランディ関数

グランディ関数（グランディかんすう、英: Grundy function）は、有限個の頂点を持つ非循環な有向グラフ上で、各頂点に0以上の整数値を対応させる関数である。スプレイグ・グランディ関数とも呼ぶ。
グランディ関数は、役割区別のない、２人交互型ゲームで、自分の番で可能な手のない人を負けとするゲームの解析に、威力を発揮する。
定義.
ゲーム局面の有向グラフ.
有向グラフは頂点の集合と有向辺の集合からなる。有向辺は始点の頂点から終点の頂点へ向きを持つ辺である。終点の頂点のことを始点の頂点の次の頂点と呼ぶ。
ゲームを有向グラフで扱う場合、ゲームの1つの局面が1つの頂点である。1つの頂点の次の頂点は、その局面で可能な手を1つ選択した場合の次の局面である。 
グランディ関数値.
有向グラフ"G"の上のグランディ関数"g"は、各頂点"x"に対し0以上の整数"g"("x")を以下のように対応させる関数である。頂点に対して次の頂点すべての集合を与える関数を関数"N"で表す。
実例.
5枚コインの1山くずしで説明する。2人で交互に許される枚数のコインを取り除き、自分の番でコインが取れない人の負けとする。1山くずしの局面はその時点のコインの枚数で表現できる。
1山くずし(毎回1枚以上3枚以下版).
1回に1枚以上3枚以下のコインを取る1山くずしである。
1山くずし(毎回1枚版).
1回に1枚のコインを取る1山くずしである。
1山くずし(毎回1枚以上版).
1回に1枚以上の好きな枚数のコインを取る1山くずしである
ゲームの和.
ゲームformula_4とformula_5の和のゲームformula_6とは、毎回formula_4かformula_5のどちらか1つのゲームの手を選択してゲームを行い、自分の番で可能な手のない人の負けとなるゲームである。
例えば、1山くずし(毎回1枚以上版)と1山くずし(毎回1枚以上版)の和のゲームは、2山くずし(毎回1枚以上版)となる。
スプレイグ・グランディの定理によると、和のゲームformula_6のグランディ値は、formula_4のグランディ値とformula_5のグランディ値のニム和となる。
1山くずし(毎回1枚以上版)のグランディ関数が恒等関数であることと、スプレイグ・グランディの定理を利用すると、ニム和を2山くずし(毎回1枚以上版)の次の局面のグランディ値で未使用の最小の0以上の整数値として算出できる。