公平组合游戏
- 游戏由两个人参与，二者轮流做出决策，且两个人都做出最优决策
- 游戏中不可能重复抵达某个状态，不可能出现平局
- 任何一个游戏者做出的决策都只与当前状态有关
必胜态与必败态
定义 必胜状态 为 先手必胜的状态
定义 必败状态 为 先手必败的状态
我们可以得到三个结论：
结论 1：没有后继状态的状态是必败状态
结论 2：一个状态是必胜状态当且仅当后继中至少有一个必败状态
结论 3：一个状态是必败状态当且仅当后继状态全部为必胜状态
这三个结论都非常显然。当一个游戏进行不下去，这是一个必败状态；当后继状态中有一个必败状态，我们就可以通过决策使得后手进入必败状态，所以这是一个必胜状态；当后继状态全部为必胜状态时，我们无法通过决策使后手进入必败状态，所以这是一个必败状态。
Chomp! 博弈
有一个 $n \times m$ 的棋盘，每次可以取走一个方格并且拿走它右边和它上面的所有方格，最后取走 $(1, 1)$ 的人输。
结论：除了 $1 \times 1$的棋盘，每次都是先手必胜
证明：假设后手必胜，那么就存在一种无论先手如何取走方格，都有一种决策（取走某个方格）使得后手必胜。事实上，先手可以先做出这样的决策（取走这个方格），再让后手走，这样就变成了无论后手如何取走方格，先手都必胜。因此不存在后手必胜的策略
Chomp! 博弈的变形
约数游戏
有 $1 – n$ 个数字，两个人轮流选择一个数字，并把它和它的约数擦去。擦去最后一个数的人赢，问谁会获胜。
结论：除了 $1$ 个数字的情况，每次都是先手必胜
染色游戏
现在有一棵含 $n$ 个节点的有根树，根节点是 $1$ ，每个点初始时都是白色。每次可以把任意一个白色节点到根节点经过的所有的点（包括该节点）变成黑色。谁最后把整棵树染黑了，谁就输了。
结论：除了节点数为 $1$ 的情况，每次都是先手必胜
NIM 游戏
$n$ 堆游戏，每堆有 $a_i$ 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取。取走最后一个物品的人获胜。
定义 $NIM$ 和为 $a_1 \oplus a_2 \oplus \cdots \oplus a_n$，当 $NIM$ 和为 $0$ 时，先手必胜
我们只需要根据定义证明三条定理：
A. 没有后继状态的状态是必败状态
B. 对于状态 $a_1 \oplus a_2 \oplus \cdots \oplus a_n \not = 0 $，存在某种决策使得 $a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0$
C. 对于 $a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0$ 不存在某种决策使得 $a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0$
根据游戏定义，没有后继状态的状态是必败状态。
若 $a_1 \oplus a_2 \oplus \cdots \oplus a_n = k \not = 0$ 那么就存在奇数个 $a_i$ 在 $k$ 的最高位 二进制位为 $1$，那么对于这样的 $a_i$ 必然存在 $a_i > a_i \oplus k$
对于 $a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0$ 要使 $a_i = a_i’$ 且 $a_{1}’ \oplus a_{2}’ \oplus \cdots \oplus a_{n}’ = 0$，那么 $a_i = a_i’$，显然不是个合法的决策。
证毕