什么是组合游戏？
- 有两个玩家。
- 有一个状态集合，经常会是无限大的。
- 每个玩家有从某状态转移到其他状态的规则，若两个玩家规则相同，称之为公平的，否则称之为非公平的。
- 两个玩家轮流行动。
- 当一个状态没有后续状态，玩家无法操作，游戏结束，通常规则下，最后一个行动的人获胜，特殊规则下，最后一个行动的人失败。这种状态称之为结束状态。
- 一般的，游戏总能在有限次数的行动下结束。当游戏无法结束时，称之为平局，下文如不特殊声明，不考虑有这种情况。（这意味着，游戏状态的转移不存在环）
需要注意的是，组合游戏是信息完全的，即任何信息都是公开的，任何行动都是确定的。
在公平的组合游戏中，对于状态集合的每个状态，将其分为两种，一种是先手必胜状态，即首先行动的人必将获得胜利，另一种是后手必胜状态，或者先手必败状态，即首先行动的人必将失败。通过归纳递推，我们可以将所有状态分类：
- 首先，结束状态必然是后手必胜状态，因为先手无法操作。
- 能转移到任何一个后手必胜状态的状态都是先手必胜状态。
- 只能转移到先手必胜状态的状态是后手必胜状态。