博弈论
定义
此处的博弈论只研究 ICG（公平组合游戏）和反常游戏中的 ICG，很多棋类游戏都是非公平组合游戏，因为双方只能移动自己的棋子。
一个游戏是 ICG 当且仅当：
游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息。
有明确的终止态，游戏不会无休止地进行下去。
每一个局面都是先手必胜（N）或者先手必败的局面（P）。
任意时刻双方可以执行的操作集合只与游戏的状态无关，与双方的身份无关。
性质
由第二条定义可得我们可以抽象成一个有向无环图，每个玩家操作一枚棋子往一条出边移动，谁移动不了了就输了。
那么对于没有出边的位置肯定是 P 局面，那么我们考虑倒推所有位置的 N/P 状态，从而得知整个游戏是先手必胜还是先手必败。
如果一个点的出边中有 P 局面，那么这个点是 N 局面。
如果一个点的出边中全是 N 局面，那么这个点是 P 局面。
这两条性质是双向的，并且可以很显然地由 ICG 的定义得到。
小例子，有一堆石子大小为 $n$，你和小 A 每次可以从中取出来 $[1,k]$ 区间中的石子，谁无法取了就失败。
可以发现一个大小为 $n$ 的后继节点是 $[n-k,n-1]$，然后直接打表 SG 值即可，或者构造一种必胜的方案，方案小学生都会就不写了。
相关函数与模型
Nim 游戏
给定 $n$ 堆石子，每堆石子有 $a_i$ 个石子，你和小 A 每次可以从任意一堆石子中选出来至少一个石子扔掉，无法操作的人输，你先手，问最后你和小 A 谁有必胜策略。
定理
如果 $ans=\operatorname{xor}_{i=1}^n a_i>0$ 的话先手一定有必胜策略，否则后手必胜。
证明
首先，没有后继的状态，即 $a_1=a_2=\dots=a_n=0$ 的时候一定先手必败。
然后如果 $k=\operatorname{xor}{i=1}^n a_i>0$ 的话一定存在一种操作使得 $\operatorname{xor}{i=1}^n a_i=0$，我们显然可以找到一个 $a_i \operatorname{xor} k < a_i$，然后改成 $a_i \operatorname{xor} k$ 就可以了。
最后需要证明如果 $k=\operatorname{xor}{i=1}^n a_i=0$ 的话不可能存在任何一种操作使得 $k=\operatorname{xor}{i=1}^n a_i=0$，显然成立。
所以结论成立。
SG 函数
定义集合的 SG 运算为 $\operatorname{mex}{S}$ 表示 $S$ 中最小的没有出现过的自然数，那么 $SG(x) = \operatorname{mex}{y_1,y_2,\dots,y_k}$，其中 $y$ 是 $x$ 的后继节点。
如果 $SG(x)>0$，那么代表先手的棋子如果在 $x$ 这个节点先手必胜，否则后手必胜。这个的证明也很显然，参考前面的 ICG 游戏的性质即可。
那么如果我们是多个游戏拼在一起的怎么办呢？
例如我们在有向图游戏上有多个棋子，然后每次可以移动一颗，最后不能移动者失败。
我们发现 $x$ 可以移动到 $SG(y) < SG(x)$ 或者 $SG(y)>SG(x)$ 的节点，如果我们移动到了 $y$ 满足 $SG(y)>SG(x)$，那么后手如果觉察到不优秀，肯定会从 $y$ 移动到 $z$ 满足 $SG(x)=SG(z)$，这样的操作是不优秀的。
那么我们只剩下移动到 SG 值比它小的节点，那么这就是一个 Nim 博弈，我们相当于每次可以拿走若干个大于等于 $1$ 小于等于全部的石头，于是直接把所有起点的 SG 值异或起来，然后按照 Nim 博弈的判断标准来判断就行了。
注意：每个局面都可以转化为含有 $SG(x)$ 个石子的 Nim 游戏，如果有多个局面，就相当于 Nim 游戏有多个石堆。
解题方法
如果我们构造了一个模型发现一个石子移动了会影响另外的石堆，那么我们可以对每个石子单独考虑得出结果。
SG 函数不一定是直接取若干个后继节点的 $\operatorname{mex}$，而是有可能每个后继节点又衍生出两个游戏，那么我们要把这两个游戏的 SG 值异或起来再取 $\operatorname{mex}$。
有些 SG 函数十分刁钻，需要打表，并且可能会出现循环节，并且只有几个特殊情况。
例题
有 $n$ 堆石子，每堆石子有 $a_i$ 个石头，每次可以选择 $i<j \le k$ 且 $a_i>0$，从第 $i$ 堆石头中选择一个石头扔掉，然后给第 $j$ 和 $k$ 堆石头中添加一个石头，最后无法操作的人失败，问先手是否拥有必胜策略。
首先，因为一次操作会影响石堆互相的值，所以考虑对每个石头分开考虑，如果当前石头距离最后一堆石头 $k$ 堆，那么我们可以扔掉它，然后加入两个距离最后一堆石头 $<k$ 的石头，就相当于可以让一个值为 $k$ 的数分裂为两个 $1 \le k_1,k_2<k$ 的数，然后分开考虑，最后异或起来就可以了。
因为 $n$ 只有 $20$，所以 $k$ 也只有 $20$，记忆化搜索打表即可。
题目如果要求输出第一次操作的方案，我们直接暴力 $O(n^3)$ 枚举第一次操作的 $i,j,k$，拿走之后判断是否先手必败即可。
代码如下：
1 |
|
附：有些题也不需要转化为 Nim 游戏，直接通过题目的性质转化为有向图游戏，然后通过 SG 函数计算即可。（需要去除一些无用状态或者记忆化一下）
取石子游戏
一维翻硬币问题有一个结论:
局面的 SG 值等于局面中所有反面朝上的硬币单独存在时的 SG 值的异或和。
这个结论同样适用于二维的翻硬币问题。
删边游戏
有一幅图，每次操作可以删去图上的一条边，操作结束之后把所有没有与 $root$ 相连的边和点删去，最后无法操作者失败。
树
首先对于叶子结点，因为只剩一个节点，所以 SG 值为 $0$。
然后对于某些其它节点 $i$，它的 SG 值经过证明可得 $SG_i = \operatorname{xor}_{v \in son_i}{SG_v+1}$.
最后整张图的 SG 值就是 $SG_{root}$。
图
首先需要找出所有的环（边双连通分量），如果一个环内的边数是偶数，那么直接将这个环缩成一个点即可。
否则需要将环缩成一个点还要再新建一个点挂一条边。
然后如果根属于一个环，那新的根就是环缩点的那个点。
容易发现这样操作完成之后是一棵树，于是直接用树删边定理即可，代码如下：
1 |
|
反常游戏
给定 $n$ 堆石子，每堆石子有 $a_i$ 个石子，你和小 A 每次可以从任意一堆石子中选出来至少一个石子扔掉，取走最后一个石子的人输，你先手，问最后你和小 A 谁有必胜策略。
设 $k=\operatorname{xor}_{i=1}^n a_i$。
如果 $a_i$ 有的为 $0$，删去不影响答案。
如果 $a_i$ 全部为 $1$，如果 $n$ 为奇数先手必败，$n$ 为偶数先手必胜。
否则如果 $k>0$ 先手必胜，否则先手必败。
证明
第一条结论显然。
第二条结论每次只能拿走一堆石子，所以显然。
第三条结论：
如果只有一个 $a_i>1$，那么先手必胜，因为先手可以让全部 $a_i$ 为 $1$，并且控制堆数的奇偶性。
有至少两个 $a_i>1$，那么如果 $k>0$ 由 Nim 游戏可得先手可以把 $k$ 转化成 $0$。
若 $k=0$，先手可以转化为至少两个 $a_i>1$ 并且 $k>0$ 的情况，那么这么交叉进行最后 $a_i$ 的堆数会逐渐减少，回归最开始的情况。
并且这种情况可以让对方必胜，也可以转化为至少两个 $a_i>1$ 并且 $k>0$ 的局面，并且至少两个 $a_i>1$ 并且 $k>0$ 的局面只能转化为 $k=0$ 的局面，所以这种情况先手必胜。
得证。
Nim-k 游戏
给定 $n$ 堆石子，每堆有 $a_i$ 个石头，每次可以选择 $1 \sim k$ 堆，从每堆中拿走一部分石子，拿走的石子总数必须大于等于 $1$，谁无法操作就失败，问什么情况下先手必胜。
结论：如果存在一位 $j$ 使得 $a_i$ 二进制下第 $j$ 位为 $1$ 的个数 $\ \bmod \ (k+1) \ne 0$，那么先手必胜，否则先手必败。
容易发现，Nim 游戏就是在 $k=1$ 的时候的特例。
证明
首先如果不存在任何一位 $j$ 满足上述条件，一次操作之后不可能也不存在一位 $j$ 满足上述条件。
如果存在，那就把所有的 $j$ 拿出来，然后因为 $a \bmod (k+1) \le k$，所以一定可以加入到 $k$ 个集合中，于是我们通过 Nim 游戏的证明就可以证出可以通过一次操作使得不存在任何一位 $j$ 满足上述条件。
当所有元素都为 $0$ 时，不存在任何一位 $j$ 满足上述条件，先手必败。
于是一来一回归纳得证。
其它
如果是到达一个状态先手必胜，那么我们必须转化为到达某个状态先手必败，然后再用 Nim/SG 的相关知识解决。
例题：
有 $n$ 个棋子，第 $i$ 个棋子在 $(x_i,y_i)$，每次可以移动一颗棋子到 $(x_i-k,y_i),(x_i,y_i-k),(x_i-k,y_i-k)$ 之一（$1 \le k$），$x \ge 0,y \ge 0$，AB互相博弈，A先手，如果某人移动了某颗棋子到 $(0,0)$，此人胜利，问先手是否必胜。
因为是移动到 $(0,0)$ 就胜利，而且有多颗棋子，我们可以考虑什么情况下面某人必败，来转化。
首先，一个人不会傻到移动棋子到 $(0,k),(k,0),(k,k)$，除非没有地方移动了。
我们就会发现如果有一个棋子位于上面三个位置，先手必胜，特判掉即可。
如果不，那么当且仅当棋子在 $(1,2)$ 或者 $(2,1)$ 的时候一定会移动到上面三个位置之一，这就是终止态，先手必败。
然后按照 SG 函数合并即可，代码如下：
1 |
|