Grundy数
定義
ゲームの状態遷移が閉路を含まないグラフ(DAG)で表されるとき、状態AのGrundy数の定義は
状態Aから1手で行ける各頂点のGrundy数をc1, c2, ..., cPとするとき、状態AのGrundy数はmex({c1, c2, ..., cP})
mexとは、集合の要素に含まれない最小の非負整数
例:mex({0, 1, 2}) = 3
例:mex({1, 2}) = 0
例:mex({}) = 0
Grundy数からわかること
Grundy数が0の場合、後手必勝。1以上の場合、先手必勝。
山がN個あるとき、各山の状態のGrundy数をd1, d2, ..., dNとすると、 (d1 xor d2 xor ... xor dN) = 0 ⇔ 後手必勝
参考URL