介绍博弈论中常见的必胜态、必败态、SG函数。
定义
若一个游戏满足：
- 由两名玩家交替行动；
- 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
- 不能行动的玩家判负；
则称该游戏为一个公平组合游戏（ICG）。
博弈状态
定义 必胜态 为先手必胜的状态，必败态 为先手必败的状态
不难有如下三条定理：
- 没有后继状态的状态是必败状态
- 一个状态是必胜态当且仅当存在至少一个必败态为他的后继状态
- 一个状态时必败态当且仅当他的所有后继状态均为必胜态
Nim游戏
先给出结论：
可以通过上面三条定理证明，在 Nim游戏 中：
- 全0局面 是唯一的终止状态；
- 对于异或和不为0的状态，一定存在某种移动使得新序列的异或和为0；
- 对于异或和为0的状态，所有的移动都会使异或和不为0；
由此，归纳可知，当所有数异或和为0时，必败；异或和不为0时，必胜。
有向图游戏与SG函数
有向图游戏是一个经典的博弈游戏——实际上，大部分的公平组合游戏都可以转换为有向图游戏。
在一个有向无环图中，只有一个起点，上面有一个棋子，两个玩家轮流沿着有向边推动棋子，不能走的玩家判负。
定义 mex 函数的值为不属于集合 S 中的最小非负整数。
对状态 x 和它的所有 k 个后继状态 $y_1,y_2,\dots,y_k$ ，定义 SG 函数：
$$
SG(x) = \mathrm{mex}(SG(y_1),SG(y_2),\dots,SG(y_k))
$$
有 SG定理 ：对于由 n 个有向图游戏组成的组合游戏，当且仅当每个起点的 SG值 异或和不为0 时，先手必胜。同时这是这一个组合游戏的游戏状态的 SG值。