博弈论学习笔记

· · 算法·理论

写在前面

感觉自己 OI 生涯快结束了，最好还是留下点东西证明我学过 OI。

绝对不是因为我 ACM 只会签博弈……

引入

博弈论最经典的例题应该就是 Nim 游戏：

给 n 堆石子，每次选一堆拿走至少 1 个，至多拿完这一堆，问先手是否必胜。

但是我认为其实这个问题并不是最贴合博弈本质的（至少涉及到了一定的运用），更本质的应该是表述为有向图的博弈。

一个有向图博弈的例子是 Nim 游戏的弱化版本：只有一个堆的情况。

我们可以这样来抽象问题：把目前剩余的石子个数作为一个点（称为一个状态），在一步操作后可以到达另一个点（即把目前的石子数 x 减少为 y），那么就连一条从 x 到 y 的边。

博弈过程可视为从起始状态开始轮流沿边移动。

此时获胜条件即对方操作时无法移动。

当然也有无法移动为胜的情况（anti-Nim），在后续内容中会讨论。

在对博弈有一定了解后会发现绝大多数博弈都可以抽象为此种模型（事实上，绝大多数 ICG 游戏 都可以）。

赛场上考察方向有以下几种：

扯远了，我们回到有向图博弈上。

有向图博弈

现在给出一些定义：

称一个状态一步可达的所有状态为后继状态。

称一个状态为必败状态，要么它没有出边，要么其后继状态全部为必胜状态（即先手不论怎么操作，操作完后手都必胜则先手必败）。

令一个状态为必胜状态，那么这等价于这个状态的后继状态中存在一个状态为必败状态（即先手通过某个操作使得操作完后手必败则先手必胜）。

自然地，如果这张图是一张 DAG，所有状态都被划分为2种：必胜状态和必败状态。

所以，在这种情况下，如果要回答先手是否必胜，只需要判断初始状态是否是必胜状态即可。

以下如无特殊说明，有向图博弈的图均为 DAG ，把状态视为一个点而转移视为一条边。

基础思维

大概介绍完了有向图博弈，我们回到博弈本身。

接下来介绍几个博弈常见的思维模式：

Wythoff 博弈

在大谈特谈一段理论之后，我们来考虑一个实际点的问题。

什么？你说为什么不考虑 Nim 游戏？

因为 SG 函数还没有定义，我们先来一个简单的。

Wythoff 博弈是这样的一个问题：

一共有 2 堆石子，一堆数量为 a，而另一堆为 b。

不妨令 a \le b，每次操作要么选一堆拿多于一个石子，同样最多拿完；要么把两堆石子拿走同样多个石子，同样最多拿完其中一堆。

观察一下可以发现必胜状态是很多的，所以关注一下必败状态有哪些。

我们的状态用 (a,b) 来表示，首先肯定有 (0,0) 是一个必败态。

经过一段打表分析发现还有 (1,2) 和 (3,5) 等。

在 这里 给出通过观察得到了的性质并证明了它。

但是我并没有这么强劲的观察能力，所以我们通过以上的几种基础思维来推出必胜状态的充要条件。

先考虑某个已知的必败态 (a,b) （此处视为无序对，即 (a,b)=(b,a)），我反向沿边跑一步，得到的所有状态都是必胜态，即 (a+x,b,a+x,b) 和 (a+x,b+x) （其中 x 大于零）都是必胜态。（此处我们把问题转换成有向图博弈）。

我们来刻画一个必败态 (a,b)，如果当前这一步同时操作两堆，那么 b-a 恒定不变，意味着所有 (a-x,b-x) 都是必胜态，因此推出关键性质：对于某个给定的 b-a，符合这一条件的必败态至多只有 1 个。

那么我只操作一堆呢？那就意味着对于一个无序对而言，我钦定其中一项相同，这时的所有无序对中也至多只有一个必败态（这里对转移边进行分类讨论）。

从另一个角度说，所有不同的必败态不会有相同的一项，所有必败态的差值也不会存在任何两对相同。

因为我们讨论了所有可能的操作，所以这就是必要条件！

我们从小到大考虑钦定必败态的一项为没有出现过的 x，对于一个 x 再钦定一个没有出现的差值 y。

那么我们要证明 (x,x+y) 是一个必败态。

接下来的证明和这里相同。

但与之不同的是我们把所谓直觉观察拆成自然的想法，使得思路可以复刻到其他题目。

可能也没有多自然……

SG 函数与 SG 定理

SG 函数和 SG 定理已经成为博弈论中不可分割的一部分（尤其是在 OI 相关中），但是我们往往忽略 SG 函数相关题目与直接构造方案的博弈题目之间的相似部分。

接下来我希望能够以自然的推导来揭示出一小部分的相似性，如果有人能够对下面几个问题提出更好的见解请发在评论区。

自然地给出 SG 函数的定义

大部分的博客中，SG 函数是先给出后介绍的，这里我们试图用一种自然的方式推导出 SG 函数的定义。

对于一类状态数奇多且转移也奇多的有向图博弈，我们要把一类状态合并成一个集合，使得同一集合内此函数值相同，也就是说，用函数值对有向图的所有状态进行分类（此为第一条性质）。

这个函数就是 SG 函数。

但是还有几个要点：

最自然的想法是用 0 和 1 来表示必败和必胜，但是如果只有 0 和 1 ，那不就是有向图博弈吗？没有得到任何的优化。

核心在于每个状态的信息不止是必胜与必败，还有转移信息（当然必败点不需要），要考虑按照转移信息分类。

思考转移边的信息怎么维护。

先讨论特殊情况：

如果一个点已经是必败的了，那转移边的信息就没有了，因为要么根本没有出边，要么到达的都是必胜点也就是可以断开此边。

同时，这也提示了我们所有必败态可以视为一个集合。

进一步地，如果同一集合内有两点直接连边，那么这个集合内进行拓扑排序，排序后最靠后的点一定没有出边会到达同集合的其他点，这就与前面的「后继状态所在集合相同」矛盾，所以同一集合内没有两点间有边。（此为第三条性质）。

考虑按拓扑排序反向建立集合。

具体来说，就是先钦定没有出边的必败态为一个集合，编号任意，不妨令其为 0。

接下来依次考虑每个点，对于一个点，它的所有后继状态的集合已经固定，所以它所在集合的编号不能与任何一个后继状态编号相同。

同时，如果其后继状态 SG 值对应集合与某编号 x 的后继状态集合相同，那么这个点的编号就是 x。

特殊地，如果到不了任何一个必败态，则这个点就是必败态，我们直接编号设为 0。

除此之外，编号任意，不妨令其为最小的未被钦定的编号。

接下来有不太容易看出来的一点，即上述3条性质是一个集合划分合法的充要条件。

要证明这一点其实也很简单，只要证明同一集合都是必胜态/必败态就可以了。

归纳法，不妨令这个结论对某个集合内所有状态的所有后继状态都成立，那么一个状态 x 的所有后继集合的状态与另一个同集合状态 y 也全部相同，因此此集合内所有状态同为必胜 / 必败态。

（实际上，编号非 0 的都是必胜态，证明会在下小节中提到）。

有了这个充要条件，我们把一个状态的 SG 值设为所有后继状态的 \operatorname{mex} 即可，这样不仅最小化了集合数，还使得所有集合编号连续。

由此我们得到了 SG 函数的某种实际含义，让我们回顾一下这个含义： **SG 函数即是某种有向图博弈的压缩方式，通过给每个状态一个集合来合并各个状态**。 --- 在自然地给出 SG 函数的定义后，我们发现 SG 函数**并没有实质上地压缩有向图大小**。 因为实际上 SG 函数是一种编号而不是一个真正的状态，对于不同的有向图而言并没有一个“通用”的 SG 函数。 换句话说，SG 函数的取值取决于这个状态的后继状态，而这是与整张图（或者说钦定起点后的一个完整子图）的形态相关的，没有给出这个图一个完整的形态，SG 函数将是不可求的。 ~~那我学个鸡毛……~~ 其实不是的，如果最后 SG 函数可以直接用状态本身的信息计算就可以优化建图了。 同时，我们推出的 SG 函数还有别的性质，或者说别的用途。 ### SG 函数的基本性质 由定义，自然地得到 SG 函数为 $0$ 的状态是必败的。 否则，它一定是必胜的，因为 SG 函数是后继状态的 $\operatorname{mex}$，而它不是 $0$，所以它一定可以到达 $0$。 SG 函数相当于维护了一个状态的多条**有效**出边，因为如果一个状态 $x$ 可以到达另一个状态 $y$，而 $\operatorname{SG}(x)<\operatorname{SG}(y)$，说明 $y$ 可以回到 $x$，即抵消操作，所以可以认为 $x$ 连且仅连向 SG 值小于 $\operatorname{SG}(x)$ 的点。 以上的性质就可以减小图的大小了（然而求的时候还是完整图）。 同时，如果可以快速计算 SG 值，那么整张图其实会收缩成类似一条链，其中每个点向其后所有点连边。 在进行多组博弈的时候（即从只有一堆的 Nim 扩展到正常 Nim），只维护必胜/必败态的函数不可并，而 SG 函数具有可并性！ 因为每次会操作其中一堆，如果有两堆都是先手必胜，只维护单堆必胜还是必败将会告诉你先手必败，然而事实并非如此。 比如一堆为 $3$，而另一堆为 $2$，先手拿走第一堆的一个，后手就必败了，因为先手可以镜像操作。 而为什么 SG 函数可并呢？因为 SG 函数**在一个必胜态维护了怎么输**，即走到另外一个必胜态。 也就是 SG 函数维护了一个必胜态的所有有效出边，相当于得到了整张图的信息，自然具有可并性。 --- 但是具体是怎么个可并法？ 如果我直接把图直接合并（即用多个状态合成一个新状态），这个复杂度是完全无法接受的。 大概是 $\mathrm O(\prod_{i ∈ S} \operatorname{SG}(i))$。 SG 函数本身是子图的信息压缩，我们看看 SG 函数能不能快速合并，于是我们得到： ### SG 定理 我们先给出这个定理并证明之，然后再叙述如何自然地想到这个定理。 对于多个博弈游戏（令集合为 $S$） 的合并（即一步操作可以选择操作某个子游戏进行，当然前提是这个游戏还能操作。 整个游戏的 SG 函数为 $S$ 内所有子游戏的 SG 函数异或和，即 $\operatorname{SG}(S)=\bigoplus_{i\in s}\operatorname{SG}(i)$。 **证明：** 同样运用归纳法，令现在的状态（即当前子游戏的集合）为 $S$，一个可达状态为 $S'$。令 $\left(\bigoplus_{i\in S}\operatorname{SG}(i)\right)=V$。 由归纳法，可令所有的 $S'$ 都符合 SG 定理。故有: $$\operatorname{SG}(S')=V \oplus \operatorname{SG}(x) \oplus \operatorname{SG}(x')$$ 其中令 $x'$ 为某个子游戏 $x\in S$ 修改后的状态。 那么，有 $\operatorname{SG}(x')<\operatorname{SG}(x)$，即 $\operatorname{SG}(x)\oplus\operatorname{SG}(x')\neq 0$，所以 $V$ 是无论如何无法被构造出的，这样就说明 $V$ 可能为 $\operatorname{SG}(S)$，但还不是一定为 $\operatorname{SG}(S)$。 现在需要证明对于所有 $V'<V$，都存在一组 $(x,x')$ 使得 $\operatorname{SG}(x) \oplus \operatorname{SG}(x')=V\oplus V'=W$。 我们发现，令 $W$ 的最高位是第 $k$ 位，则 $V$ 的第 $k$ 位为 $1$ 而 $V'$ 的第 $k$ 位为 $0$。 由 $V$ 第 $k$ 位为 $1$ 得到一定存在一个子游戏 $x$ 满足 $\operatorname{SG}(x)$ 第 $k$ 位为 $1$。这时只需要令 $\operatorname{SG}(x')$ 的第 $k$ 位为 $0$。 $\operatorname{SG}(x')$ 此时显然已经必定小于 $\operatorname{SG}(x)$ 了，所以后面的每一位都可以随便选，所以 $\operatorname{SG}(x) \oplus \operatorname{SG}(x')$ 后面的每一位也都可以随便选，接下来令 $\operatorname{SG}(x)$ 与 $\operatorname{SG}(x')$ 比 $k$ 大的位取值完全相同，就构造出了一组解。这样就完成了证明。 --- 接下来我们尝试自然地发现这个定理。 我直接用多个子游戏状态合成一个完整状态，那么这个完整状态可以用有序多元组表示，而起始状态为 $(\operatorname{SG}(S_1),\operatorname{SG}(S_2),\cdots,\operatorname{SG}(S_{|S|}))$ 。 而必败态有（不是只有）$(0,0,\cdots,0)$。 这可以视为一个 $n$ 维空间内的点。 转移去到的点则为 $n-1$ 维不变，剩下 $1$ 维可以变成原值到 $0$ 间任意整数。 这是一个 $n$ 维超立方体一部分的棱。 但是对于一个 $n$ 维超立方体，我们没有一个好的技术来分析，所以我们从 $n=2$ 的小情况开始讨论。 $n=2$： 这时只有 $2$ 个堆。 - 当两堆数量相等时，不论先手怎么做，后手都可以镜像操作，所以后手胜。 - 反过来说，如果不等，先手就可以通过一次操作使得它们相等，然后换先，所以先手胜。 这样一来，SG 值为 $0$ 的状态就知道了，于是我们可以在二维表里不断求 $\text{mex}$ 来得到 SG 值。 打出表来我们观察就会初步得到 SG 定理，推广到三维初步验证后就可以进行证明。 ~~什么？你问我怎么二维观察出异或性质？~~ 同时，$n=2$ 也就是所谓的 Acrostic Twins，即每次选同行或同列的 2 个硬币进行翻转，要求右下角的硬币正面朝上，获胜条件即将 $(1,1)$ 位置进行翻转（这时可以只翻 1 个）。 --- 现在我们讨论一个实际的问题：Nim 游戏。 一个 Nim 游戏的单堆 SG 函数（令 $x$ 为石子数）就是 $\operatorname{SG}(x)=\operatorname{mex}_{0\leq i<x}\operatorname{SG}(i)$，显然有 $\operatorname{SG}(x)=x$，简单归纳即可证明。 这里有多堆石子，每堆石子又是独立的，所以直接套 SG 定理就可以了。 SG 定理有一个要点就是，**要确保各子游戏之间是独立关系**，或者，你要证明在经过一定的转换以后，各子问题是独立的。 接下来我们来做一道更难一点的题。 ### 翻棋子博弈 现在有一个 $1 \times n$ 的棋盘，上面有 $m$ 个位置是黑棋子，其它都是白棋子。 每次操作是选择一个黑棋子，设其所在位置为 $x$，那么我们把它变白，再把所有在集合 $S_x$ 内的棋子颜色翻转（$S_x$ 会给出）。 保证在两人绝顶聪明的情况下，给出的 $S$ 可以让游戏结束。 有一个很自然的想法，就是令一个子游戏是只有第 $x$ 个位置是黑的，其他都是白的。 但是有个问题：现在 $x,y$ 都是黑的，但如果我翻转 $x$，$y$ 也会被翻转（即 $y\in S_x$），这样各子游戏之间就不互相独立了…… 但这个问题是不可解决的吗？ > Comment by Argon_Cube：思想其实很简单！与其将 $y$ 变成白的，不如看作直接在 $y$ 处再放一个黑棋子。这样就可以通过镜像操作抵消 $y$ 的影响，换句话说它们的 $\rm SG$ 异或成 $0$ 没有影响了，而且现在子游戏就独立了！原证明见下。 若翻转了 $x$，那么在 $x$ 的子游戏里，$y$ 还可以被翻转（然而在总问题中并不是），怎么办？ 那我就让 $y$ 在总问题中也可以被翻转（暴论。 具体来说，我们把「只能翻黑」的限制去掉，令获胜条件改为操作完后所有棋子都是白的。 有一个性质：**一个位置被翻两次和没翻一样**。 假设翻了 $x$ 再翻 $y$ 本来可以让后手赢（不是在翻完 $y$ 后直接赢），但现在的情况是，先手可以再一次翻转 $y$ 来抵消后手的操作。 如果后手存在赢法（在原博弈中的赢法），他就没必要和先手来回翻 $y$，而是去实现这个赢法，这个赢法在现在的问题中要么还是会导致后手赢，要么会逼迫先手不断抵消后手的操作。 否则后手就会不停翻 $y$ 来阻止先手赢。 然而其实这里已经隐含了**这个不停翻的状态下，此时的先手输定了**这一点，所以这个状态的 SG 值本来就是 $0$ 而不需要考虑来回翻的情况。 所以我们可以把这些状态直接设为必败态，那么**一个原问题的赢法一定唯一对应一个新问题的赢法**。 而新问题的**各子问题是独立的**！ 我们只要解决新问题即可。 新问题直接上有向图博弈求子游戏 SG 值，然后 SG 定理合并即可。 ## 其他的 Nim 相关博弈模型 Nim 游戏因为其经典的构型（$\operatorname{SG}(x)=x$）而为人广泛所知。 而由此也衍生出了大量的 Nim 相关模型，比如阶梯 Nim，anti-Nim，k-Nim 等。 需要注意的是，上述衍生模型**并不能扩展到 SG 函数本身上**。 也就是说，以上模型对 SG 定理和 SG 函数不适用，因为它们的 SG 值并不是它本身。 ### 阶梯 Nim 也许是最好理解的一种？ 挑选 $1$ 到 $n$ 中任意一个存在石子的位置 $i$ ，将至少 $1$ 个石子移动至 $i-1$ 位置。 可以移到 $0$，结局应当是所有石子都在 $0$。 谁不能操作谁输。 与翻棋子博弈相似，我们把问题转化为子问题互相独立的形式。 同样运用抵消操作的思想，发现： - 一个偶数非 $0$ 的位置上的石子是可以被推到某个奇数的位置上的，但是对方可以把它直接运到另一个偶数位置上，即为**一个石子运到偶数位置以后就对答案无影响**。 - 一个奇数位置上的石子是**一定需要**被推到 $0$ 位置上的，而 $0$ 位置上的却无法被拿走，所以**一个石子进入偶数位置，则它可以在不影响答案的情况下进入 $0$**。 两条结合就相当于每次可以从奇数位置拿走石子，而偶数位置直接忽视的普通 Nim 游戏。 ### anti-Nim 与普通 Nim 博弈基本相同，只是条件改为拿完者输。 与阶梯 Nim 不同，这里各堆"石子"在明面上是之间互不干扰的。 你可能很快就会套上 $\operatorname{SG}(1)=0,\operatorname{SG}(0)=1,\operatorname{SG}(x)=x(x \ge 2)$，试图直接过题。 然后就 WA 了。 为什么呢？ 因为这里的 SG 函数**并不是不互相干扰的**，比如两个局面相同，我向其中一个额外加一个 $1$ 进来，在 SG 函数上它们是等价的，而实际上不等价。 问题就在于 $0$ 和 $1$ 的 SG 函数设计不对，这里的设计是认为**多一个 $0$ 与原局面不同，而多一个 $1$ 与原局面相同**。 在原 Nim 博弈中，这一点是正确的，但在 anti-Nim 则是错误的。 有人问多一个 $0$ 是怎么来的，这是因为在你的删除过程中可以有 $0$ 状态被抵达。 那么，应该怎么写？ 可以这样子： 令 $\operatorname{SG}(x,y,v)$ 表示「有 $x$ 个 $0$，$y$ 个 $1$，剩下有且仅有一堆 $v$ 个石头的堆」这个局面对应的 SG 值。 在这里我们的 SG 函数需要认为多一个 $0$ 是相同局面，而多一个 $1$ 是不同局面。 合并时就可以认为整个游戏是由一个 $(x,y,0)$ 的局面和多个 $(0,0,v_i)$ 的局面构成。 然后分析 SG 值， - 显然一个 $(n,0,0)(n \ge 0)$ 是必败态，$\operatorname{SG}(n,0,0)=0$。 - $(n,1,0)$ 可以且只可以到 $(n,0,0)$ ，所以 $\operatorname{SG}(n,1,0)=1$。 - $(n,m,0)(m \ge 2)$ 可以且只可以到 $(n,m-1,0)$ ，所以 $\operatorname{SG}(n,m,0)=m\bmod 2$。 - 综合一下就有 $\operatorname{SG}(n,m,0)=m \bmod 2(n \ge 0,m \ge 0)$，也就是有 $\operatorname{SG}(n,m,0)=\operatorname{SG}(n,m\bmod 2,0)$。 - $(n,m,1)$ 和 $(n,m+1,0)$ 是等价的。 - $(n,0,v)(v\geq 2)$ 可以到 $(n+1,0,0),(n,1,0)$，$(n,0,v')(v'\ge 2)$，画出图来就有 $\operatorname{SG}(n,0,v)=v$。 - $(n,1,v)(v\geq 2)$ 可以到 $(n+1,1,0)$，$(n,2,0),(n,1,v')(v'\ge 2)$，其中 $\operatorname{SG}(n,2,0)=0,\operatorname{SG}(n+1,1,0)=1$，同样画出图来仍有 $\operatorname{SG}(n,0,v)=v$。 因为合并的时候一个子游戏中 $n+m$ 和 $v$ 最多只有一个非 $0$，所以我们可以令 $\operatorname{SG}_1(v)=v,\operatorname{SG}_2(v)=v\bmod 2$，最后用非零堆的 $\operatorname{SG}_1$ 的异或和异或上剩余堆数目的 $\operatorname{SG}_2$。 进一步地，我们可以总结出 [反常游戏](https://oi-wiki.org/math/game-theory/misere-game/) 的规律，也就是上面的式子。 --- 同时 anti-nim 还有一个常见变体（虽然结论没啥关系就是了）。 就是给定一棵树，每次操作是删掉某个点为根的整颗子树，删掉根的人（也就是拿完的）输。（Updated by Argon_Cube：原题是 AT_agc017_d） 先分析特殊情况：整棵树是一条链就有（设 $s$ 为树的大小）： $$\operatorname{SG}(0)=1,\operatorname{SG}(1)=0,\operatorname{SG}(s)=s (s\ge2)$$ 这里不会像 anti-Nim 一样出现错误，原因是我们的问题转化方式不一样。 再思考这样的情况：根节点（设为 $1$）只有一个儿子（设为 $2$）。 以下令 $\operatorname{SG}(u)$ 表示 $u$ 为根的子树的 SG 值。 假设我们已经知道了 $\operatorname{SG}(2)$，现在想求 $\operatorname{SG}(1)$。 你就发现，当前局面的所有可达局面（除了空局面）都可以表示为 $2$ 的所有可达局面加一个新根节点 $1$。 所以 $\operatorname{SG}(1)=\operatorname{SG}(2)+1$。 然后考虑在这样子的基础上，在根节点挂几条其他的树。 接下来问题转化一下：把根节点复制多份，然后把这些儿子分配给每个根节点，设复制后每个根节点下挂且仅挂了一条链，原树变成一个森林。 你发现这时森林的 SG 值和原树的 SG 值相同（森林的胜负条件是拿了任何一个根节点就输）。 因为既然不能拿根，那么拿其他部分在树上是互不影响的，在森林也一样，而且树上的所有方案与森林上的所有方案都构成双射。 （正是因为这一点，我们才会想把树拆成森林）。 拆成森林这件事，自然地会引导我们去证明：各树 SG 和与森林 SG 值相等。 这里很酷，因为这个森林的拆分不会出现一个空的子游戏，所以上面说的“**多一个 $0$ 与原局面不同**”就不会出现，而多一个根节点本来就没差别，所以上面说的“**多一个 $1$ 与原局面相同**”也是成立的。 因此这个结论是对的！这样我们就得到 $\operatorname{SG}(u)=\bigoplus_{u\to v}(\operatorname{SG}(v)+1)$。 ### K-Nim 与普通 Nim 的差别在于每次最多可以选取 $k$ 堆石子分别进行取石子操作，当然，要选至少 $1$ 堆。 这个情况就不是很好分出子游戏的概念了。 我们考虑结合一些简单情况和之前得到的博弈结果来分析。 首先，如果每堆石子都只有 $1$ 个，那么就是经典的控制 $\bmod~(k+1)=0$ 的结论，即符合此条件则先手输，否则先手赢。 接下来我们结合普通 Nim 来分析，同时也尝试提出一个审视 SG 定理的新视角。 我们给出一个视角： SG 定理相当于 $2$ 步： 1. 拆位。 2. 对每一位使用「控制 $\bmod~(k+1)=0$」这个结论。 是不是听起来很对？（事实上也是对的） 浅证一下： 直接思考是困难的，我们能不能退一步，思考一个有启发性的问题：对于普通 Nim 来说，把一堆石子拆成各个大小为 $2^x$ 的石子堆这个局面与原局面等价？ 这件事是好证的，因为两个局面的 SG 值相等即可说明其等价。 那么拆完以后发现有个很 cool 的点，就是如果两堆大小相同，对于这两堆，先后手就会由获胜方镜像模仿失败方，因此可以直接忽略这两堆。 我们进一步，就可以抵消掉大小为 $2^x$ 的所有堆中多余的堆。 接下来考虑最大的一堆，如果我们把它拿到大小刚好等于其余所有堆的和，那么就可以镜像操作。 如果我们做不到这点，即为最大的堆与其余堆之和相等，然而这是不可能的，除非现在根本什么都没剩下。 这也算是 SG 定理的变相证明。 由此也可以证明新视角的正确性：我们把一堆取到可以与某几堆镜像操作，就相当于把这堆和被镜像操作的堆都删除了，即**可以任意取走某一位的一，谁先取到 $0$ 谁赢**。 我们来扩展这个视角到 K-Nim。 发现问题在于镜像操作这一点不再成立了，因为本来是镜像的两步可以同时被一个人实现。 但是「保持 $\bmod~(k+1)=0$」这件事仍然成立，这件事本身就是另外的一种“镜像操作”。 那么我们仍然拆位，但统计每一位 $1$ 的数量，如果对于所有位，$1$ 的数量 $\bmod~(k+1)=0$ 恒成立，说明先手必败（后手对所有位镜像操作），否则对于某一位不满足这一性质的，先手可以利用它换先并抹除其他这样的位。 你可能以为结论对了这个咱们就讲完了，但其实不是。 因为我们没有说明拆成「$2^x$ 和原局面等价」仍然成立。 我们之前证它是用 SG 定理的定义，但现在不行，因为**我们没有给出 SG 函数，就不能认为 SG 值相等**。 于是我们考虑实际意义： 我们需要证明在原局面中选 $k$ 个操作和在新局面里选 $k$ 个操作等价，这个事与上面的「变相证明」是同理的，就不赘述了。 ~~留作习题，读者自证不难~~ --- ### There's still more 有很多题目需要具体分析，所以 SG 函数的运用是千变万化的，我们常用的做法其实就是打表找规律。 但是！打表之间亦有差距。 首先有一个基本的想法：打出所有状态的 SG 值。 这是最基本的行为，你不一定可以很快地找出规律。 然后进阶一点的想法就是，把转移边打出来。 但是所有的转移边会显得很散乱，具体是什么样的输出方式也需要思考，不过这个就是比较个性化的东西了。 有一个很好的想法是：对一个状态 $S$，其 SG 值为 $V$，打出其**来源中 SG 值最大的状态**（即为 SG 值为 $V-1$ 的来源状态）。 打表就聊到这里。 在相当一类博弈问题中，博弈会在一棵树或图上进行。这时状态就不好表示成可以打表的形式了。 这个时候比较适宜的做法是把链上的 SG 值或者菊花的 SG 值算出来，然后考虑对其合并。 或者，考虑一个点可达的所有状态是否构成包含关系，以此在图上直接由图边进行转移。 还有一类比较少见的博弈是在一个矩阵上进行的，往往是走到同行 / 列中符合某些条件的点。 这样的题目一般可以分析出几个策略之间的优劣，以此可以优化转移边至 $\mathrm O(1)$ 或 $\mathrm O(n)$ 级别，但是这样子其实不太需要使用 SG 函数，往往是使用数据结果优化转移。 ---- 接下来 SG 函数暂时不会出现了，因为还有一些公平博弈不需要 SG 函数——其中一种就是二分图博弈。 ## 二分图博弈 我们之前提到的几乎所有模型都偏向抽象，但是现在可以回归到一些比较具体的东西。 来重复一下之前的性质，对于一个博弈而言，我们画出它的状态图，你会发现： - 所有必胜点的可达点全都必败。 - 所有必败点都可以到达一个必胜点。 - 对一张给定的图，我们可以去掉从必败到必败的所有边，这样图的胜负情况是不变的。 既然如此，我们可以把状态视为点，保留下的转移视为边。 这样，我们就造出了一张二分图。 但是仔细读过前面部分的老哥会说，你这没有用啊，我定义必胜必败点需要先跑一遍深搜啊，这对优化复杂度没用啊。 是的，**在求解必胜点没有更优秀的方法时**，这个技术是无效的。 但是！正如通过 SG 函数可以解决某些特殊的状态图一样，在许多问题中，就算在二分图的情况下，边数依然很多，可其却具有足够的性质来使用 DP / 局部最优等方式来确定这一点。 但是但是，我要是有这办法就直接求了对吧？ 这里根本用不上二分图这个性质对吧？ 所以，我们在解决这一问题时，一般**假定必胜点的情况**，然后通过二分图的性质来进行判定。 那么，我们需要题目具有两个性质： - 必胜点集合一定满足某个很简单的限制，比如点值全小于某个数，这个限制要么使**可能的必胜点集合很少可以暴力枚举**，要么具有**可二分性**。 - 判定必胜点集合的方法复杂度足够优秀。 举例来说：[CF1710E Two Arrays](https://www.luogu.com.cn/problem/CF1710E)。 诸如此类，给定每个点的点权和移动方式（一般来说，走过的不能再走），先手要最大 / 最小化结束时所在点权，后手反之，每个人可以移动或者**直接结束游戏**，我们要求的是最后所在点的权值。 注意后面这个条件，这是二分图博弈黑白染色的前提。 这时可以二分答案，把小于 / 大于 $mid$ 的点染黑（设为必胜点），剩下的染白，就实现了枚举必胜点集合的效果。 我们这里有黑到白，白到黑，**黑到黑** 3 种边，理论上这个并不是二分图，所以我们要去掉黑到黑的边。 注意在这里其实最原始的状态应该是已经走过哪些点的点集，但是可以发现我们把**黑到黑的边去掉（这时才是二分图）**，这个新博弈与原始博弈等价，这里的证明需要利用可以直接结束游戏的性质。 当然二分的时候就可以把 $l$ 设置为起点点权，因为先手可以直接结束。 所以接下来我们默认起点为白。 check 相当于给定起点，判断从起点开始走最后是不是只能到黑。 我们有这样一个结论：**去掉起点最大匹配若减少，则先手必胜，否则反之**。 我们来证明一下这个结论： 首先，去掉起点最大匹配减少，等价于所有最大匹配方案中都含有起点，这个是定义。 我们先证结论右推左：先手必胜那么走的路径是 $\texttt{WBWBWBWBWB}\ldots\texttt{WB}$ 其中白是 $\texttt{W}

黑是 \texttt{B}，这里默认后手要尽量拖时间（这样一定不劣），所以路径一定最长。

这条路径显然对应一个匹配方案，即相邻的一组 \texttt{WB} 互相匹配。

那么，先手只要按照任意一个最大匹配来走，后手就会配合着走完这个匹配（然后输掉）。

这时，先手每次去一个匹配点，后手每次走一个匹配边以跑完一组匹配。

接下来反过来，我们让后手跳出这个匹配以求胜，那么现在，这条路就成了 \texttt{WBWB}\ldots\texttt{WBW}。

注意这里的这个匹配是指任意一个最大匹配。

所以，现在后手在一个非匹配点，目前的路径不是任何一个最大匹配的子集。

我们现在去掉起点，按 BW 来分匹配，那么匹配大小与跳出之前相比不变。

因为你加入的是一个非匹配点，所以你可以挑一个最大匹配，这个匹配含有整条路径除起点和当前非匹配点的所有点。

把目前路径和这个匹配取并集，那么新得到的匹配要么比所谓最大匹配还大，矛盾；要么不含起点，矛盾。

右推左证完，接下来左推右：

你现在有一个不含起点的最大匹配，那你从起点走一步，你一定得到一个匹配点，否则你就能增大这个匹配。

那你相当于从 \texttt{B} 开始不断走匹配边，最后一定停在 \texttt{W}，就输了。

如果不存在这样的匹配，那最大匹配就一定包含起点，那就从 \texttt{W} 开始不断走匹配边，就停在 \texttt{B}，先手必胜。

如果感觉这里证明模糊可以看文章末尾的对应参考资料。

但是说这么多证明，搞 OI 都没有用，因为你只要用就行了。

问题就在于怎么用。

我们有这样一个性质：最大匹配与最大独立集构成双射（一一对应）。

这个是图论知识啊，我在此就不证明了，可以自行搜索。

接下来，我们就要求解最大独立集，这个一般会比最大匹配好求一点。

因为在图论研究中，最大匹配往往研究一般性的问题，大部分做法都不是特化的（或者说，二分图已经是很特殊的特化情况），难以利用性质直接保证复杂度。

而最大独立集就不一样了，我们有一系列的分析工具来处理特殊情况。

以例题而论，把图的黑点重排到左下，白点重排到右上。

最大独立集应当是左上 + 右下 2 个矩形，这个可以 DP 解决，详情可以读此题题解。

非公平博弈

就现在而言，很多题都是非公平博弈，可以说是出题倾向了。

其实 HDU 的 ACM 每年都有很多这类题目，读者也可以在近年省选找到 2023 联合省选 过河卒 这样的题。

一般而言有 2 个考察方向：Ad-Hoc 式的手模分析或暴力模拟有向图博弈，后者代码难度较高，前者思维难度较高。

但是 Ad-Hoc 吧，它也没有什么通用的技术，讲代码实现技巧，又不是很贴合主题。

我姑且空泛提一些技巧，权当抛砖引玉：

在此之后呢？

接下来博弈论有 2 个主要的发展方向：

走向无限：序数理论。

寻找均衡点：纳什均衡和多玩家博弈。

其实纳什均衡一方面的研究甚至早于 SG。

相比前面所提及的内容，这两方面的 OI 题目相对较少，而且一般需要结合数学 / 数据结构知识，博弈论相对并不是最难的一部分。

但是在这类题目中，博弈论是不可或缺的一部分，如果你不会，那很大可能会考察你的 Ad-Hoc 能力，或者成为人类智慧题。

序数理论的例题是 【省选联考 2024】 最长待机。

纳什均衡的是 【THUPC 2023 初赛】 欺诈游戏 或 CF98E Help Shrek and Donkey。

这里有点超出正常 OI 的范围了，不过省选考了你会也基本没辙，我浅提一下，可能大学会填坑。

序数部分

我们主要讨论一下序数的比较大小，接下来的术语并非标准，但我认为它比较易懂。

序数跟所谓无穷进制数即多项式比较相似，可以认为我们用一个多项式来表示一个状态，x^2 的系数再大也无法跟 x^3 相比。

在序数中，我们需要定义一个或多个操作，比如我定义：“输入一个数，然后循环这么多次，每次再输入一个数，每次输入后会停输入 '这个数' 秒”，而玩家可以看到操作这一秒之前的所有操作（包括对手的和自己的）。

玩家的得分是总运行时间，获胜条件就是得分更大。

注意，有的情况不一定能判断谁必胜，而序数做法可以判定出无法确定。

在描述完问题以后，我们来定义嵌套操作：

具体的，序数中类似 x^n 的就是某个操作的 n 重嵌套。

可能有点抽象，我们举个例子：

我们的操作是：输入一个数，然后循环这么多次，每次执行“输入一个数，然后循环这么多次”，这里是一个二重嵌套即 x^2。

而在例子中，我们定义 1 表示 x^0 也就是停一秒。

然后再定义一下加法：x^2+x^3 就表示先执行输入一个数，然后循环这么多次，每次执行“输入一个数，然后循环这么多次”；再执行“输入一个数，然后循环这么多次”的三重嵌套。

我们还可以混合两种运算：x(x+1)，表示输入一个数，循环这么多次，每次输入一个数，停几秒，再停一秒。

再次强调，这里给出的定义都是不严谨的，只是便于理解。

由于定义，我们的乘法并不支持对加法分配律，甚至，加法和乘法都不支持交换律。

比如，就定义来说，x(x+1) 和 (x+1)x 是不同的。

某种程度上来说，它与多项式技术的差别在于侧重不同，后者注重系数的变换，而前者可以忽略系数直接比较（或者说除了表示方式相似就没啥相似了）。

我们现在引入一些比较规则，还是用例子说话：

x+1=x<1+x

先输入一个数 v_1，停 v_1+1 秒并不能肯定谁必胜，这和输入 v_2=v_1+1，停 v_2 秒是等价的，因为你同时输入这两项不知道哪个更大。

但 1+x 就不同，你先停一秒就可以知道对方输入啥，你输入更大的就占优。

用这个思路还可以得出 x(x+1)=x^2。

纳什均衡

这个技术解决这样一类问题：每个人有一些选择，所有人的选择合在一起得到一个状态，会给每个人对应的回报，博弈论比较奇怪，这个回报叫做代价。

这里代价越大也就是回报越大，和正常汉语不一样。

每个人都想最大化自己的代价，而大家都绝顶聪明，所以最后大家不一定会选到最优的结果。

最经典的例子就是囚徒困境。

囚徒困境

若只有一边招，这个人释放，对面判 $5$ 年。 俩都招，都判 $3$ 年。 都不招，都判 $1$ 年。 从客观的角度，都不招是全局的最优解，但是作为囚徒本身来讲，如果对面招，你招更优，对面不招，你还是招更优。 所以在**玩家只利己**的条件下，双方都会招，避开了都不招这个比当前结局严格更优的解。 那么“都招”，这个就是纳什均衡点。 也就是说，**纳什均衡点是不会有任何一方主动改变自己策略的点**。 在做数学题时，我们可以先随便选一个点，然后看有没有任何一方会主动改变自己选择，一直做到没人动为止。 当然还有和囚徒困境一样的办法求纳什均衡：对每个人去掉相对某个其他而言绝对不优的选择，不断处理每个人直到做不了为止。 #### 混合策略纳什均衡 这里我们允许一个玩家按照一定概率来进行选择。 比如石头剪刀布，赢的得一分输的扣一分平局不变。 那不可能一个人一直出剪刀对吧。 最优的做法就是等概率选择石头剪刀布。 这里就可以设 A/B 选石头 / 剪刀 / 布概率为 $p_{i,0/1}$，然后可以列出得分的方程，在对手策略不变时我们改变这一方的策略使得期望得分最大，这个改变方法可以称为**反应函数 reaction function**（一方对另一方改变策略的反应）。 我们不断重复这个过程就可以得到均衡时双方策略，因为选择有概率，所以称为混合策略纳什均衡。 #### 更多应用 和 OI 里很多抽象的不行的博弈不同，纳什均衡可以应用在现实的经济学中（不过会复杂很多）。 但是在这里我们的选择不是简单的离散选择，而是连续的函数。 比如说生产产品的数量是选择，市场上价格与总产品数量有关（产品越多价格越低），所有的厂商来选择生产数量使自己利润最高（这里的成本与生产数量也相关）。 随成本函数和价格函数不同，我们的反应函数也有很多种。 但在这个模型中，可以认为所有厂商等价也就是每个玩家最后策略是一样的。 反应函数会把一个人的代价调到最高，所以把它求一阶导，导函数为 $0$ 即最大（极大）值一般可以做完了。 ## 碎碎念与致谢 ~~因为不熟悉 $\sout{\LaTeX}$ 规范投全站推荐一直被打回。后来还是 Argon_Cube 帮我改好了。~~ 其实写完了发现自己对博弈论理解也不是很深入，如果有误还请指出。 万一有伪证或者定义不清我看到会立刻修改。 参考资料有： [VG 的博弈系列学习笔记（1）：浅谈 Wythoff 游戏](https://www.luogu.com.cn/article/47xbnmjv) [VG 的博弈系列学习笔记（3）：谈谈 SG 函数与 SG 定理及其若干拓展](https://www.luogu.com.cn/article/1am7gm8b) [博弈论小记](https://www.luogu.com/article/6apzxhu6) [CF1710E 题解](https://www.luogu.com.cn/article/gke449qa) [P10222 最长待机 不很是题解而是序数理论入门](https://www.luogu.com.cn/article/ty0wud02) [二分图博弈学习笔记](https://www.cnblogs.com/Pbriqwq/p/15502037.html) [耶鲁大学博弈论公开课](https://open.163.com/newview/movie/free?pid=EHJOV84RI&mid=QHJOV89Q7) [博弈论习题解答（浙江大学）](https://max.book118.com/html/2018/1228/5102224013001343.shtm) [OI-wiki](https://oi-wiki.org/math/game-theory/intro/)