博弈论
NIM 游戏及几个经典模型
其他典型博弈
SG函数
对抗搜索与其他技巧
NIM游戏及几个经典模型
经典NIM游戏
给定 $n$ 堆物品，第 $i$ 堆物品有 $A_i$ 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可以一堆取光，但不能不取。取走最后一件物品则获胜。两人都采取最优策略，问先手能否获胜。
结论：对于 Nim 游戏的一个局面 $(A_1,A_2,\ldots,A_n)$ 来说，先手必败当且仅当 $A_1 \oplus A_2 \oplus \ldots \oplus A_n=0$。
证明：凡是异或和非 $0$ 的都可以通过一次操作变为异或和为 $0$ 的，因此可以归纳证明。
阶梯模型
有 $n$ 层阶梯，编号 $1\dots n$，每层阶梯上有一些石子。
两个玩家轮流操作，每次操作可以将第 $i$ 层阶梯上若干(至少一个)石头放到 $i-1$ 层阶梯上，第 $0$ 层阶梯即为地板。
将最后一颗石头从阶梯移到地板上的玩家胜利。
不难发现，所有偶数阶梯都等价于垃圾桶。若一方尝试将偶数阶梯中的石子移出(至奇数阶梯)，下一个人只需要紧跟着把这些石子丢到下一个(偶数)阶梯即可，最终会到达地板。这个过程中，先后手是不会转换的。
接下来考虑奇数阶梯，一步就可以把任意多的石子丢进垃圾桶，实际上就等价于 NIM 问题。
翻硬币模型
$n$ 个硬币排成一行，每次可以翻连续的若干个，要求最右边的必须从反到正，无法操作的人输，问谁赢。
结论：整个游戏的 SG 函数相当于所有反面硬币的 SG 函数的异或和，而位于 $x$ 位置的 SG 函数有规律：$SG(x)=lowbit(x)$
斐波那契NIM游戏
有 $n$ 枚石子。两位玩家定了如下规则进行游戏：
- 第一次取石子时可以取走任意多个；
- 接下来，每次至少要取走一个石子，最多取走上一次取的数量的 $2$ 倍。当然，玩家取走的数量必须不大于目前场上剩余的石子数量。
- 取走最后一块石子的玩家获胜。
结论：先将 $n$ 写成齐肯多夫表示，即用斐波那契数表示且没有相邻两个都是 $1$，则先手每次取最低位的 $1$ 即可获胜。
其他典型博弈
威佐夫博弈
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。
结论：当且仅当两堆石子的数量构成黄金比的时候后手获胜。
二分图博弈
在二分图上，两人轮流指定下一步去哪个点，不经过重复的点，无法指定的人输，问谁赢？
结论：当一个点在所有最大匹配的方案中（少了这个点无法最大匹配），那么先手必胜。
证明：后手不可能选到非匹配点，如果后手选到一个非匹配点，设路径为 $S_1\rightarrow S_n$，那么把现在的匹配换成 $S_2\rightarrow S_n$，匹配数不变但不包含 $S_1$，与最大匹配一定包含 $S_1$ 矛盾。
扩展到无向图的情况：不指定起点，则有完美匹配后手必胜；否则结论与上面一样。
树（图）上删边博弈
在一棵树/图上钦定一个根，每次可以删去一条边，若删边后某部分与根不连通则一并删去，不能操作者失败，问谁赢？
结论：叶子的 SG 是 0，其他点的 SG 是所有儿子节点 $+1$ 后异或起来。
证明：考虑往一个子树顶上加一条边是什么意思，就是对于子树内的状态转移 $DAG$ ，加一个点 $T$, 然后对原来的每个点，加一条到 $T$ 的边，容易归纳说明每个点的 $SG$ 都会增加 $1$。该思路在其他题目中也可以使用。
图的情况：把所有偶环缩成点，所有奇环缩成一个点和一条边（只连他自己那个点），然后当成树来做。
SG函数
约定终止态的 SG 函数值为 $0$。
定义 $mex(S)$ 为集合 $S$ 中最小的未出现的自然数。
设 $G$ 能转移到的集合为 $T_G$，则定义 $$SG(G)=mex{SG(V):V\in T_G}$$
性质：$SG(G)=0$ 为必败态，否则为必胜态。
SG和
考虑两个人同时面对多个游戏，但每次只能操作其中一个。则 $SG(A+B)=SG(A)\oplus SG(B)$，NIM游戏的原理也可以这么解释。
推SG函数的例题：HNOI2007分裂游戏，CF1149E
反SG-游戏
即最后一步不能走的人胜利的游戏。
有以下 SJ 定理：对于任意一个 Anti-SG 游戏，如果规定当局面中所有单一游戏的 SG 值为 $0$ 时，游戏结束。则先手必胜当且仅当：
1.游戏的 SG 函数不为 $0$ 且游戏中某一个单一游戏的 SG 函数大于 $1$；
2.游戏的 SG 函数为 $0$ 且游戏中没有单一游戏的 SG 函数大于 $1$。
对抗搜索与其他技巧
对抗搜索&DP
在一个竞争的环境中，双方通过竞争实现相反的利益，一方最大化这个利益，另一方最小化。
定义合适的状态后，先找到必败态，然后通过记忆化搜索的方式实现，如果当前是必胜态就要在所有后继为必败态的结果中取 $\max$，否则在所有后继状态中取 $\min$。
决策包容性
如果一个状态能直接到达他后继状态的所有后继状态，在该状态是一个必胜态。
例题：ARC137C
建立模型
通过建模把原问题中复杂的操作转化为图形化的，或是易于处理的操作。
例题：AGC002E
通过建模把其他问题转化为博弈论问题。
例题：AGC043C