博弈论
声明
- 局面：博弈时唯一的信息状态。
- 完全信息博弈：博弈双方都清楚双方的目标。
- 平等博弈：一般我们讨论的是平等博弈，也就是双方无论是谁在当前局面决策集合是相同的。
在 OI 中，博弈一般有双方存在：做决策的时候都知道当前局面处于什么状态, 以及可以向什么状态转移。
图论模型
对于所有的平等博弈，我们都可以将之抽象为图论模型。
将状态看作一个点，而决策导致的变化看作一个边，那么博弈的局面会形成一张图，点数与状态数线性相关，而边数与决策集合大小线性相关。
一个一定可以在有限步内分出胜负的游戏，在抽象出来之后局面会形成一个 DAG。
SG 函数，SG 定理 - 罪恶的本质
在我们抽象出来的 DAG 中，定义 $SG(x) = \mathrm{mex} \{SG(y) \vert (x, y) \in E \}$，声称一个局面必胜当且仅当 $SG(x) \gt 0$。
对于一个多进程游戏，也就是有多个独立的小游戏，那么声称一个局面必胜，当且仅当对于所有独立游戏，$\bigoplus SG(x_i) \gt 0$，其中 $\bigoplus$ 指异或和。
SG 函数的定义是容易理解的，考虑证明 SG 定理。
一个必要的说明，若 $SG(x) \ne 0$，那么必定存在一个后继局面 $SG(y) = 0$，反之，如果 $SG(x) = 0$，那么如果存在后继局面，那么必定存在 $SG(y) \ne 0$。
那么对于 $SG(x) = \bigoplus SG(x_i)$，尝试证明满足两者。
对于 $SG(x) = 0$，那么考虑对于任意子游戏，考虑 $SG(x)$ 的后继局面 $SG(y)$ 一定满足 $SG(x) \ne SG(y)$，这利用 $\mathrm{mex}$ 的定义是显然的，于是说改变量一定 $\ne 0$，从而后继局面一定 $SG(x) \ne 0$。
对于 $SG(x) \ne 0$，先考虑如下事实，如果 $SG(x) = k$，那么表明后继一定可以到达 $SG(y) \lt k$ 的所有局面。于是当 $SG(x) \ne 0$，考虑找到对于其最高位贡献的那个 $SG(x_i)$，此时我们将其变为 $SG(x) \oplus SG(x_i)$，由于此时最高位被抵消掉了，那么一定存在的是 $SG(x) \oplus SG(x_i) \lt SG(x_i)$，也就是一定存在这么一个后继转移使得 $SG(x) = 0$。
综上，由异或定义的 $SG(x)$ 满足 $SG$ 函数的定义，所以 $SG$ 定理是合理的。
在求 $SG$ 函数时，我们更多的是打表找规律，而不是硬推 T^T
我们可以从另一个角度说明我们为什么使用异或这一个运算。
- 交换律：将两个子游戏的顺序交换不影响整个游戏。
- 结合律：将多个子游戏分为若干组游戏不影响整个游戏
- 自反性：如果有两个完全相同的游戏，那么同时删除不影响整个游戏，也就是抵消了。考虑在其一上的操作可以在另一上完美的复现。
有了如此性质，发现异或很符合，那么就可以直接怼上去了。
Nim 游戏 - 罪恶的开端
nim 游戏说的是一些石子堆，每次可以取走一些石子，最后不能操作的人败，求先手必胜还是必败。
一个简单的想法是每个石子堆互不影响，也就是独立的小游戏，那么我们只需要求出一堆石子的 $SG$ 函数，利用 $SG$ 定理即可。
设 $SG(x)$ 表示有 $x$ 个石子的堆，利用 $SG$ 函数的定义，$SG(0) = 0$, $SG(x) = \mathrm{mex}_{i = 0}^{x - 1} \{SG(i)\}$，不难发现的是 $SG(x) = x$，所以最终先手必胜当每一堆石子个数异或和不为 $0$。
各种 Nim 游戏 - 罪恶的滋生
阶梯 nim
有若干级阶梯，每次可以将某个阶梯上的若干石子向下移动一级，不能操作则输。不妨设最低级台阶为 $0$ 级台阶，那么声称有用的只有奇数层的台阶，因为如果操作了偶数层，那么后手一定可以在下一层进行同样的操作，不影响先后手以及局面。
那么此时我们声称奇数台阶上的石子可以规约为普通的 nim 游戏。因为此时先手操作的奇数，考虑偶数阶上的石子无用，因此相当于删掉了操作的石子，如果对手试图重新将删掉的石子放回来，那么先手重复其操作即可，这样最终移动到 $0$ 后轮到后手操作，只能操作奇数阶的石子，也就是说一旦操作了就相当于删除了，于是规约为了普通的 nim 游戏。
k-nim
在考虑这个游戏之前，我们先考虑另一个经典游戏：
- Bash Game：有 $n$ 个石子，每次可以从取出 $1 \sim m$ 个石子，无法操作者输。
在这个游戏下，先手必败当且仅当 $n \equiv 0 \pmod {1 + m}$。
而对于 k-nim，我们类似的考虑 $\bigoplus SG(x_i)$，忽略没有被影响到的二进制位，我们对于每一个二进制位实际上可以有 $1 \sim k$ 个影响，于是对于每一位就规约为了一个 Bash Game。
于是仿照 SG 定理的证明，可以得到后手必胜当且仅当对于每一个二进制位个数 $\equiv 0 \pmod {1 + m}$。
anti-SG
指游戏规则相同，但是不能操作者胜。
这里就需要引出一个新的定理了。
- SJ 定理
适用于满足如果 $SG(x) = 0$，那么要么没有后继状态，要么后继状态 $SG(y) = 1$ 的游戏。
先手必胜，当且仅当：
- $\forall i, SG(x_i) \le 1$ 并且 $\bigoplus SG(x_i) = 0$。
- $\exists i, SG(i) > 1$ 并且 $\bigoplus SG(x_i) \ne 0$。
证明需要分为四种情况讨论，比较繁琐，可以看贾志豪写的论文《组合游戏略述——浅谈SG游戏的若干拓展及变形》。
翻硬币游戏
每次可以按照某个约束翻一些硬币，但是需要满足最左/右边的硬币一定向上/下。
这里声称硬币之间相互独立，即整个局面的 $SG$ 等于所有硬币单独存在时的 $SG$ 的异或和。
值得一提的是，如果存在两个相同的局面，那么考虑 $SG(x) \oplus SG(x) = 0$ 的事实，相当于抵消了。
对于此类游戏，将所有硬币看作一个二进制数，由于限制的存在，意味着整个数一定不断减小，也就是无论如何操作，游戏总能在有限步内完成。
考虑按照某个约束翻一些硬币，换个方式理解，也就是按照某个限制增加一些位置的硬币，由于异或的自反律，相当于翻转了硬币。而根据 $SG$ 定理，整个游戏的 $SG(x) = \bigoplus SG(x_i)$，那么实际上硬币是相互独立的，于是整个局面的 $SG$ 等于所有硬币单独存在时的 $SG$ 的异或和。
零和博弈 - 罪恶的新篇章
二人零和博弈，就是指有2个参与人的博弈，其博弈前后的得益总和固定不变，即一方所得为另一方所失。如果将赢看作 $1$，败看作 $-1$，那么实际上类似于石头剪刀布，包括前面的游戏都是零和博弈。
对于零和博弈，认为一轮为一个转移单位，由一个状态经过双方操作进入下一个状态。
不妨设先手的操作集合为 $A$，后手的操作集合为 $B$，那么这一轮的转移 $S = A \times B$，也就是两者的笛卡尔积。认为可以利用一个矩阵 $M$ 来表示，其中 $M_{i, j}$ 表示先手进行决策 $i$，后手决策 $j$ 之后博弈的结果。不妨设先手要最大化这个结果，而后手要最小化这个结果，那么可以引入一个定理：
- 最小最大定理
简单来说，对于后手，在知道了先手选择了 $M$ 的某一行后，那么一定选择当前行的最小值。由于先手知道后手一定选择行最小的，那么一定会选择行最小最大的行。
计算过程也就是先对于每一行求 $\min$，然后对于求出来的求 $\max$，即可理想状态下得到转移后的得失。
然而实际上的定理没有如此简单。
最小值最大定理声称，若 $X \subseteq \R^n, Y \subseteq \R^n$ 为紧致凸集，$f: X \times Y \to \R$ 为连续的凸凹函数，即 $f(x, y)$ 关于 $x$ 是凸函数，关于 $y$ 是凹函数，那么：
$$\min_{x \in X} \max_{y \in Y} f(x, y) = \max_{y \in Y} \min_{x \in X} f(x, y) $$
这个函数大概如图，是个马鞍形：
对了，补充一下这里的凸函数不是像 $\cap$ 一样的函数，而是像 $\cup$ 一样的函数，也就是斜率单调不减。但是根据百度词条，不同的地方定义的不太一样？抽象。
但是值得注意的是在一般的博弈模型中这个等式并不满足，但是在一些特殊的套路中满足。