这篇文章偏结论性，几乎没有什么证明。
一些定义
公平组合游戏
信息完全公开、双方交替行动、同一局面双方的决策集合相同、且一定会在有限步内结束的游戏。
N 态与 P 态
N 态：先手必胜的状态；P 态：先手必败的状态。
一个状态为 P 态当且仅当其所有出边都为 N 态；一个状态为 N 态当且仅当其出边中有一个为 P 态。从而 P 态不可能转移到 P 态。
游戏的和
设有两个游戏 $A,B$，每次双方选一个游戏移动一步，这样子得到的新游戏称作 $A,B$ 的和，记做 $A+B$。
SG 函数
一个局面的 SG 函数值定义为
$$
SG(x)=\begin{cases}0,&E_x=\varnothing\\\operatorname{mex}_{v\in E_x}(SG(v)),&\mathrm{otherwise}\end{cases}
$$
其中 $E_x$ 指 $x$ 转移得到的状态集合，$\operatorname{mex}(S)$ 指最小的未在 $S$ 中的自然数。
定理 1：$SG(x)=0$ 当且仅当 $x$ 是 P 态。
定理 2：$SG(A+B)=SG(A)\oplus SG(B)$，这里的 $\oplus$ 表示按位异或。
一些常见的游戏
Anti-SG 游戏
一类不可操作者胜利的游戏。
对于该规则下的取石子游戏，先手必胜当且仅当所有堆中石子数都小于等于 $1$ 且异或和为 $0$，或者存在一个堆中石子数大于 $1$ 且异或和不为 $0$。
当我们尝试将其扩展到一般的 Anti-SG 游戏时，会出现问题，因为处在一个 $SG(x)=0$ 的状态时可能有出边，此时无法直接胜利。
所以 Anti-SG 游戏中先手必胜当且仅当
- 所有局面中 SG 函数值都小于等于 $1$ 且异或和为 $0$，或者存在一个局面 SG 函数值大于 $1$ 且异或和不为 $0$。
- 当 $SG(x)=0$ 时，游戏可以立刻结束，或者存在一条出边使得到达的边的 SG 函数值为 $1$。
Multi-SG 游戏
一类一个单一游戏的后继可能为多个游戏的游戏。
仍然可以使用 SG 函数，将后继多个游戏的 SG 函数值异或和作为后继状态的 SG 函数值即可。
Every-SG 游戏
一类对于任意没有结束的游戏，操作者都必须进行一步操作的问题。
每个游戏先手必胜还是先手必败是已经确定的，唯一有影响的就是时间。求出胜利的最早时间和失败的最晚时间，进行比较即可。
一些经典的博弈问题
Nim 博弈
有 $n$ 堆石子，双方轮流取石子，每次选定一堆并从中取出任意多的石子（不能不取），不能操作者输。
$SG(x)=x$。
Bash 博弈
有 $n$ 堆石子，双方轮流取石子，每次选定一堆并从中取出至少 $1$ 个、至多 $m$ 个石子，不能操作者输。
$SG(x)=x\bmod m+1$。
Wythoff 博弈
有两堆石子，双方轮流取石子，每次可以从两堆中取走相同数量的石子或者选择一堆取走若干石子（不能不取），不能操作者输。
令 $\alpha=\frac{1+\sqrt{5}}{2},\beta=\frac{3+\sqrt{5}}{2}$，$(x,y)$ 是先手必败状态当且仅当 $(x,y)=(\lfloor\alpha n\rfloor,\lfloor\beta n\rfloor)$。可以由 Beatty 定理证明。
阶梯博弈
$n$ 层阶梯，每层有一堆石子，每次选择一堆，取出若干个丢到低一层中（特别的，第 $1$ 层的直接扔掉），不能操作着输。
只把奇数层的拿出来，相当于一个 Nim 博弈。
翻硬币游戏
$n$ 枚硬币，有的正面向上，有的反面向上，每次按照某个规则翻转一些硬币，但最右边的必须是从反面翻转成正面，不能操作者输。
结论：局面的 SG 函数值等于局面中每枚正面向上的硬币单独存在时的 SG 函数值的异或和。
树上删边游戏
一个有根树，每次是选择一条边，删除此边以及删掉边后和根不连通的部分，不能操作者输。
$SG(x)=\oplus_{v\in son_x}(SG(v)+1)$，叶节点的 SG 函数值为 $0$。
1-动态减法博弈
有一个正整数 $n$，双方轮流将其减去一个正整数，第一次不能减完，接下来每次减的值不能超过上次，先将其减到 $0$ 者胜利。
先手必败当且仅当 $n=2^k$。
2-动态减法博弈
有一个正整数 $n$，双方轮流将其减去一个正整数，第一次不能减完，接下来每次减的值不能超过上次的两倍，先将其减到 $0$ 者胜利。
先手必败当且仅当 $n$ 为斐波那契数。
k-动态减法博弈
上面两种博弈的一般情况。
有一个正整数 $n$，双方轮流将其减去一个正整数，第一次不能减完，接下来每次减的值不能超过上次的 $k$ 倍，先将其减到 $0$ 者胜利。
设上一轮取了 $x$ 个，此轮至多取 $f(x)$ 个，其中 $f(x)$ 单调不降。再设 $H_i$ 表示第 $i$ 个先手必败态，且 $H_1=1$。
定理：$f(H_i)\geq H_i$，$S_{i+1}=\min\left\{H_x|f(H_x)\geq H_i\right\}$，$H_{i+1}=H_{i+1}+S_i$。
如果递推到第 $i$ 个时发现 $f(H_i)<H_i$，那么之后不存在任何先手必败局面。