2人交互に手番がくるゲームのうち、ランダム性がなく無限に続かないものはGrundy数によってNimに帰着できることがある。
Nimとは、いくつかの石の山のうち好きな山を選んで1つ以上の石を取り除くことを交互に繰り返すゲームであり、取れる石がなくなったプレイヤーが負け。
Nimの特徴として、すべての山の石の数のXorを取ったものが0でない状態で自分の手番が回ってきたプレイヤーが勝つ（Xorが0の状態で自分の手番が回ってきたプレイヤーはどうやっても勝てない）というものがある。これは「負けの状態（すべての山が0こ）はXorが0」「Xorが0の状態からどのように石をとっても必ずXorが1以上になる」「Xorが1以上の任意の状態からうまく石をとることで必ずXorを0にできる」「必ずいつかはゲームが終了する」という性質から導ける。一旦Xorが0でない状態を引いたら、相手にXorが0の状態を押し付け続けることで絶対に勝利することができる。お互いが常に最適に行動するとき、どちらが勝つかは初期状態が与えられた瞬間に決まる。
2人交互に手番がくるゲームのうち、ランダム性がなく無限に続かないものはGrundy数によってNimに帰着できることがある。Grundy数とは、ゲームの各状態について以下のように定義される数である。
ゲームの各状態がいくつかの要素（たとえばNimであればいくつかの石の山）から構成されると考えたとき、その要素の数だけGrundy数を定義する。各要素について、その状態が終状態（負けの状態）であれば、Grundy数は0となる。ある要素について、その状態から遷移できるすべての状態を列挙して、それらのGrundy数のなかに存在しない最小の非負整数をその要素のGrundy数とする。例として、ある状態から遷移できる状態のGrundy数が$\{0,1,2,4\}$なら、その要素のGrundy数は$3$である。
Grundy数はNimの石の数に対応した概念であり「終状態はGrundy数が0」「Grundy数のXorが0の状態からどのように遷移しても必ずXorが1以上になる」「Grundy数のXorが1以上の状態からうまく遷移させることで必ずXorを0にできる」という性質をもっている。状態によってはGrundy数がより大きい状態に遷移できることもあるが、最終的に必ずゲームが終了するのであれば関係ない。
発展的な問題であればGrundy数の求め方を工夫することが本質である場合が多い。その場合は、まず遷移を書き出して実験から法則を掴むことが重要。