1. Nim 博弈
结论
先手必胜当且仅当 \(\oplus SG(A_i) \not = 0\)。
2. Nim-K 博弈
每次可以选不超过 \(k\) 堆石子，Nim 可以看成 \(k=1\) 的情况。
结论
先手必败当且仅当每个二进制位上满足 \(1\) 的个数是 \(k+1\) 的倍数。proof
3. Multi-SG
在符合拓扑原则的前提下，一个单一游戏的后继可以为多个单一游戏，正常 SG 即可。
Multi-Nim：每次可以选择分裂一堆石子。
结论
\(SG(x)=\begin{cases} x-1,x \mod 4 = 0 \\ x+1,x \mod 4 = 3 \\ x, \text{otherwise}\end{cases}\)
4. Anti 游戏
无法操作的一方获胜
结论
先手必胜条件：\(SG(G) \not = 0, \exist i, SG(A_i) > 1\)
后手必胜条件：\(SG(G) = 0, \forall i, SG(A_i) \ge 1\)
5. Bash 博弈
同 Nim游戏, 但每次取的石子不能超过一个常数 \(m\)。
结论
\(SG(x) = x \mod (m + 1)\)
6. 阶梯 Nim 游戏
\(n\) 层阶梯上分别有 \(1\) 堆石子, 每次可以选择一堆中的任意个石子扔到下一层 (特殊的, 第一层的石子直接被扔出游戏), 无法操作者败。
结论
\(SG(G) = \oplus_{i=2k+1} SG(A_i)\)
7. 翻硬币游戏
结论
\(SG(G) = \text{所有正面向上的硬币单组} SG\)
棋盘游戏：选择一个矩形翻转。长条时 \(SG\) 为 \(\text{lowbit(x)}\)，二维为 \(min(\text{lowbit(x)}, \text{lowbit(y)})\)
8. 删边游戏
- 一棵有根树, 每次删除一条边及其子树部分, 不能操作者败。
结论：\(SG(u) = \oplus (SG(v) + 1)\) proof - 树上挂了若干个环（仙人掌）
结论：\(SG(\text{环}) = \text{环长} \& 1\) - 一个无向图, 每次删除一条边以及与根节点不连通的部分。
结论：将偶环替换成一个新点, 奇环替换成一个新点连出一条边, 原图中连向环的边全部连向新点, 图的 SG 值不变。
推论：对于一个边双连通分量, 其 SG 值只与其边数的奇偶性有关。
9. Every-SG
有若干个独立的游戏, 每次要移动所有可以移动的棋子, 不能操作者败。
结论
每个单独的游戏的结果已经确定了, 对最终结果有影响的就只有每个游戏结束的时间。
对于先手必胜的游戏, 我们希望它进行的时间可以尽量的长, 而对于先手必败的游戏, 我们希望它尽早结束, 这样我们才能确保最终的胜利。
所以计算出先手必胜的最长时间 和 先手必败的最短时间, 将两者进行比较即可。
10. 匹配在博弈中的应用
一张无向图, 初始时有一个棋子在 s 点, 轮流将棋子移向一个之前没有到达过的点, 无法操作者败。
结论：先手必胜, 当且仅当 s 在该图的所有最大匹配中 (即删去 s 会使该图的最大匹配减小)。
11. 动态减法
- 有一个整数 \(n\)，双方轮流减一个正整数，第一次不能减完，每次减的数不能超过上一次。
结论：先手必胜当且仅当 \(n \not = 2 ^ k\)，每次取 lowbit(\(n\)) 即可。 - 每次减的数不超过上一次 \(k\) 倍
结论：proof