グランディ関数
有向グラフGの上のグランディ関数gは、各頂点xに対し0以上の整数g(x)を以下のように対応させる関数である。頂点に対して次の頂点すべての集合を与える関数を関数Nで表す。
頂点xの次の頂点が0個、つまりN(x)={ }ならば、g(x)=0である。
頂点xの次の頂点が1個以上で、 N ( x ) {\displaystyle N(x)} = { y 1 , y 2 , . . . , y k {\displaystyle y_{1},y_{2},...,y_{k}} } ならば、g(x)は g ( y 1 ) , g ( y 2 ) , . . . , g ( y k ) {\displaystyle g(y_{1}),g(y_{2}),...,g(y_{k})} の値と一致しない最小の0以上の整数である。
ゲーム G 1 {\displaystyle G_{1}} と G 2 {\displaystyle G_{2}} の和のゲーム G 1 + G 2 {\displaystyle G_{1}+G_{2}} とは、毎回 G 1 {\displaystyle G_{1}} か G 2 {\displaystyle G_{2}} のどちらか1つのゲームの手を選択してゲームを行い、自分の番で可能な手のない人の負けとなるゲームである。
例えば、1山くずし(毎回1枚以上版)と1山くずし(毎回1枚以上版)の和のゲームは、2山くずし(毎回1枚以上版)となる。
スプレイグ・グランディの定理によると、和のゲーム G 1 + G 2 {\displaystyle G_{1}+G_{2}} のグランディ値は、 G 1 {\displaystyle G_{1}} のグランディ値と G 2 {\displaystyle G_{2}} のグランディ値のニム和となる。
1山くずし(毎回1枚以上版)のグランディ関数が恒等関数であることと、スプレイグ・グランディの定理を利用すると、ニム和を2山くずし(毎回1枚以上版)の次の局面のグランディ値で未使用の最小の0以上の整数値として算出できる。