有若干堆石子,两个玩家轮流取石子,每次可以从任一堆中取走任意多枚石子。假设棋子个数为。对于
,用
表示
和
按位异或的结果。
- 取走最后一枚者赢:先手胜当且仅当。
- 取走最后一枚者输:先手胜当且仅当所有全为
且
为偶数,或者存在
大于
且
。
- 每次只能取不超过枚,取走最后一枚者赢:记
为
模
的值
。先手胜当且仅当
。
如果再增加一种操作:从一堆棋子中取走一些并把这堆剩下的分解成更多的堆,在前3种规则下,结论和前3种相同。
- 每次只能取不超过枚,取走最后一枚者输:记
为
模
的值
。先手胜当且仅当所有
全为
或
且
等于
的个数为偶数,或者存在
大于
且
。
- 只有一堆石子,有枚,第一步操作的玩家第一次不能全取,以后每次操作的玩家不能取超过另一名玩家上次取的石子数,取走最后一枚者赢:先手胜当且仅当
不为
的幂。
- 只有一堆石子,有枚,第一步操作的玩家第一次不能全取,以后每次操作的玩家不能取超过另一名玩家上次取的石子数的两倍,取走最后一枚者赢:先手胜当且仅当
不是斐波那契数。
正常游戏:无法操作者输。
反常游戏:无法操作者赢。
每个无偏游戏都可以对应到一个带根的有向无环图,其中
表示起始状态,
表示没有后继状态的状态集合,
表示整个状态图。从游戏
到游戏(
的一个同态是指
满足:
和
。
任意两个游戏,它们的和
表示这样一个游戏:初始状态玩家面临
游戏的初始局面和
游戏的初始局面,每名玩家在每回合可以选择
游戏或者
游戏进行一步操作。
正常游戏终结状态后手胜;反常游戏终结状态先手胜。逆推可以最终推出初始状态谁会获胜。
定义Sprague-Grundy函数为:对于终结状态,;对于非终结状态
存在从
到
的有向边
。则状态
先手胜当且仅当
。
任意两个游戏,
。称两个游戏等价如果它们的Sprague-Grundy函数值相等。
只有一堆石子,且它恰包含枚石子的尼姆游戏的Sprague-Grundy函数值为
。所以每个无偏游戏都和某个只有一堆的尼姆游戏等价。