博弈论基础 · 公平组合游戏

· · 算法·理论

这是一篇博弈论的入门文章，同时也整合了作者的学习笔记，并对所有例题作了详细讲解，希望能帮到你！

内容包括但不限于：

引入

相信大家都玩过这个游戏：有一些火柴，两人轮流操作。每次操作可以取走一根或者两根，取走最后一根的获胜。

从这里开始，为了方便，我们都假设参与游戏的玩家都是天才，一定会采取最优策略。

不难发现，当火柴的数量是 3 的倍数的时候，先手会输，否则先手会赢。

简单的证明就是：我们可以维持轮到对手的时候火柴数量是 3 的倍数，且轮到自己的时候不是。具体地，对手取 x 根，我们就取 3-x 根。那么因为 0 是 3 的倍数，那么没有火柴的时候一定轮到对面，对面输。

上述过程就是数学归纳法在博弈论中的体现。

如果是能取走 1\sim k 根火柴呢？只需要把“3 的倍数”改成“k+1 的倍数”即可，道理是一样的。

这个游戏就是公平组合游戏。

介绍

公平组合游戏，当然以公平为基本原则。具体地，都需要满足这些东西:

一般情况，我们遇到的游戏都是两名玩家轮流操作，分别是先手和后手。

我们将局面分为：

同理，从一个局面出发，到后面局面形成的决策过程，总体被称为必胜游戏或必败游戏。

显然，所有局面要么必胜，要么必败。

博弈图

观察我们对于公平组合游戏的定义：同一个状态不可能多次抵达。那如果我们把每一个局面看作一个节点，并向可一步到达的局面连有向边（这些局面被称为后继局面），则我们会得到一个 DAG（有向无环图）。

这个 DAG 没有入边的点就是初始局面，没有出边的点就是已经无法继续操作的必败局面。

这个图被称为博弈图。

怎么确定一个节点是必胜局面还是必败局面呢？可以从定义入手：

很多时候，直接通过上述判断方法，就可以递推出每个节点是必胜还是必败。

Nim 游戏

有 n 堆石子，第 i 堆有 a_i 个石子。两名玩家依次操作：每次操作可以选择一堆非空石子堆，并取走至少一个石子。不能操作者输。

先考虑单堆 Nim 游戏。在 n=1 的时候会怎么样：显然当 a_1>0 的时候为必胜局面（一次取完）；当 a_1=0 的时候为必败局面（开局就动不了）。

如果 n>1 呢？结论是简单的：

局面必胜的充要条件为 \bold{a_1\oplus a_2\oplus\dots\oplus a_n\ne0}。

其中 \oplus 为按位异或。

::::info[证明方法]{open}

证明的思路顺其自然，首先是充分性：

我们拿到这样一个可爱的必胜局面，就去努力让对面拿到 a_1\oplus a_2\oplus\dots\oplus a_n=0 的必败局面。最后无法操作的时候显然异或和也是 0，这样这个局面只有对面能拿到，我不就赢了？

怎么去操作呢？我们找到异或和 s 的最高非零位 d，然后去操作某个第 d 位也是 1 的 a_i。取 k 为 s\oplus a_i ，再将 k 所有 <d 的位取反，不难发现此时 k<a_i，将 a_i 减少成 k 后异或和 s 就变成 0 了。

必要性：

如果我拿到 a_1\oplus a_2\oplus\dots\oplus a_n=0 的局面，操作后肯定 a_1\oplus a_2\oplus\dots\oplus a_n\ne 0，对面按照上述方法操作我就输了。

::::

我们称自然数列 a 的异或和，成为其 Nim 和。

Nim 游戏作为典型的公平组合游戏，在后续研究中极其重要。

游戏之间的关系

对于游戏 G 和 H，我们接下来研究 G+H 是啥。

什么？游戏也能加起来？

游戏 G+H，即 G 和 H 互不干扰地进行，且：

  • 玩家每次操作只能选择在 G 或者 H 中操作一次。
  • 当 G 和 H 都无法操作的时候，游戏结束，无法操作者失败。

也就是说，G+H 是同时玩 G 和 H 两个子游戏的游戏，它也具有公平组合游戏的各种性质。

而且这个加法也满足结合律和交换律。

容易发现对于 n>1 的 Nim 游戏，相当于 n 个单堆 Nim 游戏的和。

有了加法这样一个工具，就可以去试着定义游戏的等价关系了。

游戏 G\approx H，当且仅当对于所有游戏 I，G+I 和 H+I 胜负状态相同（要么都是必胜游戏，要么都是必败游戏）。

其中 \approx 是等价符号，注意并不一定是 =，因为游戏千千万万，我们所说的等价是在决策过程所引出的结果上没有区别。

从这里我们可以发现一个非常关键的性质：两个等价的游戏的和是必败游戏。

::::info[证明]{open} 因为 G\approx H，所以 G+G\approx G+H；因为 G+G 是必败游戏，所以 G+H 是必败游戏。

这一性质也可以通过后续的 SG 函数来证明。 :::: 好，说了这么多，都是为了引出下面这个定理。 ## SG 定理与 SG 函数 这一部分许多定理的证明较为复杂，限于篇幅，在本文中没有写出证明步骤，读者若想了解可以自行搜索。 **SG 定理**： > 任何公平组合游戏都等价于某个单堆 Nim 游戏。 这个有啥用呢？我们可以给所有游戏 $G$，赋值一个函数 $SG(G)=x$，其中 $x$ 就是 $G$ 所等价的单堆 Nim 游戏的石子数量。 那么我们判断 $G$ 是必胜还是必败，**只需要看 $SG(G)$ 是否 $>0$**。 这里的 $SG()$，就是 **SG 函数**。 **游戏的和的 SG**： > $$SG(G_1+G_2+\dots+G_n)=SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_n)$$。 换句话说，就是游戏的和的 SG 函数等于所有子游戏 SG 函数的 Nim 和。 证明很显然：都转化成单堆 Nim 游戏了，那么一起玩不就是多堆 Nim 游戏！多堆 Nim 游戏怎么判断胜负呢？就是用 Nim 和来判断。 **SG 函数的递推**： > $$SG(G)=\operatorname{mex}_{G'\in G}SG(G')$$。 > > 其中 $G'\in G$，表示 $G'$ 是由局面 $G$ 走一步能得到的局面。 > > $\operatorname{mex}$ 为集合中最小未出现的自然数。 有了这个式子，就可以更方便地推出各种局面的 SG 值，来判断谁能赢了。 学会 SG 函数后，先别着急用，因为暴力求 SG 还是指数级别的，并非所有题都能使用。 而用到 SG 函数的题一般否需要找到关键性质，才能快速推出我们需要的 SG 值！ 所以在博弈论题中，大部分题不能纯靠推，需要依靠**打表**或者~~超强注意力~~等手段**找到初步规律**（或 SG 函数的规律）。或从基本的公式出发找性质。 --- 至此，对于公平组合游戏的基本概念，以及 SG 函数的介绍就基本结束了。 现在，考虑进入具体问题来探索！ ## 应用策略 & 例题 ### O 策略讲解都在 Sol 中，因此前面题目即使会做也可以看看。 - 此部分题目并不完全是洛谷题目，难度评价作参考。解法为我的做法，不一定只有一种 - 更重要的是思考过程，最开始不会做可以放心看解法，只要经过充分思考，**猜测和打表**很重要！ - 不需要对每道题都去写代码，毕竟很多题目都是结论为主。 - 都是我精选的好题 qwq。 ### I 来源：P4860，难度黄。 有 $n$ 个石子，每次可以取走 $1$ 个或者 $p$ 个（$p$ 为质数）。无法操作者失败，先后手谁会获胜？ $n\le 10^{18}$。 [题目链接](https://www.luogu.com.cn/problem/P4860)。 ::::info[sol] 练习点：打表。 手推或者运用博弈图性质（必胜点后继至少一个必败，必败点后继都是必胜）打表，可以算出 $n$ 较小的时候的胜负状态，即可发现先手必胜当且仅当 $n\bmod 4\ne 0$。 可以去证明这件事情，仍然是数学归纳法。$n<4$ 显然是对的。对于 $k\ge 4$： - $k\bmod 4=0$，必败。由于 $1$ 或者任意质数都不是 $4$ 的倍数，所以我们要么已经无法操作（$k=0$），要么会在操作后让对手拿到 $k\bmod 4\ne 0$。 - $k\bmod 4\ne0$，必胜。我们可以一步操作让对手拿到 $k\bmod 4=0$ 的局面。这是显然的，因为 $1,2,3$ 都是可以用的数字。 :::: ### II 来源：USACO，难度绿。 若当前有 $x$ 个石子，设其十进制最大数码为 $a$，最小非零数码为 $b$，玩家可以取走 $a$ 或 $b$ 个石子。最开始有 $n$ 个石子，问先后手谁会获胜？ $n\le 10^6$。 [题目链接](https://www.luogu.com.cn/problem/P2953) ::::info[sol] 练习点：博弈图递推。 这里具体讲一下递推步骤。 设 $f_i$ 表示最开始有 $i$ 个石子，先手是否会获胜，用 $0/1$ 表示。 那么 $O(\operatorname{log}n)$ 求出 $a,b$ 之后，若 $f_a=f_b=1$，那么 $f_i=0$；否则 $f_i=1$。 再搬一次基本理论！先手必胜点至少一个后继是后手必胜点（必败点），后手必胜点（必败点）所有后继都是先手必胜点！ :::: ### III 难度绿/蓝。 有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个石子。两名玩家依次操作：每次操作可以从第一堆中拿走至少一个石子，或者从第 $i$（$i>1$）堆中将至少一个石子移动到第 $i-1$ 堆。无法操作者失败，先后手谁会获胜？ $n\le 10^7,1\le a_i\le 10^{18}$。 ::::info[sol] 练习点：Nim 游戏，游戏转化。 发现可以忽略第偶数堆，并将奇数堆看作普通 Nim 游戏，因此先手获胜条件就是 $a_1\oplus a_3\oplus a_5\oplus\dots\ne 0$。 设这个只考虑奇数堆的 Nim 游戏为 $H$，原游戏是 $G，证明还是类似： 如果 $H$ 必胜，那么先手就从奇数堆正常进行操作：拿走（对于第一堆），或者移到左边那堆偶数堆（对于其它奇数堆）。这些 $G$ 移动的石子，不管拿走还是放到偶数堆，都不再在 $H$ 中考虑，所以就相当于 $H$ 的一次操作，仍然可以获胜。 如果 $H$ 必败，那么先手怎么挣扎都没用，首先如果操作奇数堆，那像刚才说的，就和 $H$ 的一次操作等价，既然不跳出 $H$ 而且 $H$ 必败，那么当然无法获胜。如果操作偶数堆，那么对手把我们拿到奇数堆的那些石子，再往左移动回另一个偶数堆（或者直接拿走），这一轮在 $H$ 中相当于两个人都没操作，先手还是必败。 综上，$G$ 可以看作 $H$，即对于奇数堆的独立单堆 Nim 游戏的和，可以直接 Nim 和得到结论。 :::: ### IV 来源：ARC208A，难度：蓝 有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个石子。两名玩家依次操作：每次操作可以从某一堆中拿走至少一个石子，需要保证所有 $a_i$ 按位或的结果时刻不变。无法操作者失败，先后手谁会获胜？ $n\le 10^6,1\le a_i\le 10^9$。 [题目链接](https://atcoder.jp/contests/arc208/tasks/arc208_a) ::::info[sol] 练习点：Nim 游戏，游戏转化。 和 Nim 游戏不一样在每个出现了 $1$ 的二进制位最终都会留下一个。 考虑钦定每堆石子最终会留下哪些二进制位。钦定之后我们就在游戏一开始把这些位设为 $0$（提前去掉一些石子），就变成了正常 Nim 游戏，先手失败的条件是 $a_1\oplus a_2\oplus \dots =0$。 发现我们钦定留下哪些二进制位，就相当于把每个出现了 $1$ 的二进制位分配给某堆这一位是 $1$ 的石子。无论分配给谁，我们最终需要的所有 $a_i$ 的异或和都是一样的，都相当于在这一位再异或一个 $1$。 综上，先手必败的条件为 $a_1\oplus a_2\oplus \dots\oplus a_n=a_1|a_2|\dots|a_n$，也就是异或和再给出现 $1$ 的每一位异或一次后为 $0$。 :::: ### V 来源：P11056，难度：蓝。 原题题目足够简洁，见 [题目链接](https://www.luogu.com.cn/problem/P11056)。 ::::info[hintA] 不存在模 $n$ 相同的后手必胜点。 :::: ::::info[hintB] 为所有后手必胜点找一个石子数上界。 :::: ::::info[sol] 练习点：博弈图递推，推理。 性质 1：不存在模 $n$ 相同的后手必胜点，否则较大者就是先手必胜了（一步可达后手必胜的是先手必胜）。 性质 2：所有后手必胜点 $p\le n(\sqrt{n}+1)$。 性质 2 证明：考虑反证，假设有大于这个数字的后手必胜点，那么考虑两步： - 第一步：从后手必胜点走一步到的所有点都必须是先手必胜点，此时对于 $p>n(\sqrt{n}+1)$，有 $>\sqrt{n}$ 种走法是减去 $n$ 的倍数的。 - 第二步：这 $>\sqrt{n}$ 个和 $p$ 同余的先手必胜点，必须要能走到至少一个后手必胜点。那么再减去 $n$ 的倍数是不可能的（由性质 1），只能减去完全平方数，而减去的方案数只有 $\sqrt{n}$ 种。又因为性质 1，所以这 $>\sqrt{n}$ 个先手必胜点所减去的完全平方数必须两两不同，此矛盾，故原假设错误。 博弈图递推前 $n\sqrt{n}$ 的胜负情况即可。 ```cpp // f：1 为先手必胜，0 为后手必胜 // vis：目前有没有同余的已经是后手必胜了 for(int i=0;i<=V;i++){ if(vis[i%n]) f[i]=1; else if(!f[i]){ vis[i%n]=1; for(int j=1;j*j<n&&i+j*j<=V;j++) f[i+j*j]=1; } } ``` 注意卡空间，要开 bitset。 :::: ### VI 来源：P13755，难度：蓝。 原题题目足够简洁，见 [题目链接](https://www.luogu.com.cn/problem/P13755)。 ::::info[hintA] 二分答案后转 $0/1$ 串，判定能否拿到 $1$。 :::: ::::info[sol] 接着 hint。 经过前面的讲解，我们发现数学归纳法确实很有用。所以更进一步，对于某个先手必胜的条件，一般都是要： - 可以通过必胜条件让对方拿到必败条件（必胜条件的反面）。 - 在必败条件中怎么操作都会让对方又拿到必胜条件。 试着找一找先手必胜条件，发现就是：**能通过一步操作让剩下的后缀 $1$ 的数量大于等于 $0$ 的数量**，边界条件略去。 也可以在构造操作方案的时候发现这个条件。 操作方案就是： - 找到所有分割点，满足分割后剩下的后缀 $1$ 的数量大于等于 $0$ 的数量。 - 选择最后面的满足上述条件的分割点进行分割。 - 这就说明，分割后的这段后缀，不存在一段后缀满足 $1$ 的数量大于等于 $0$ 的数量。我们可以说明更强的事情：这个后缀**所有的非空前缀 $1$ 的数量都大于 $0$ 的数量**，不难证。 - 既然如此，对面不管怎么操作，剩下的区间 $1$ 的数量都大于 $0$ 的数量，仍然满足我的必胜条件。 至于输出操作方案，刚才那个“选取最后一个”是一定最优的，但不一定唯一。可以直接枚举一下分割点，再用对面必败的条件判断即可。 :::: ### VII 来源：CF603C，难度：蓝。 有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个。两人轮流操作：每次可以选择一堆减少 $1$ 个石子；或者选择 $a_i$ 为偶数的堆，将其用魔法变成分开的 $k$ 堆数量均为 $\frac{a_i}{2}$ 的石子。无法操作者失败。问先后手谁会赢？ [题目链接](https://www.luogu.com.cn/problem/CF603C)。 ::::info[sol] 练习点：SG 函数。 每堆石子都是分开的子游戏，我们分别计算 SG 函数后异或起来，再检查是否为 $0$ 即可（为 $0$ 先手输）。 对于变成 $k$ 堆相同石子，如果 $k$ 是偶数那么异或和就是 $0$，否则异或和等价于一个这样的石子堆的 SG。 而一个个数为 $x$ 的石子堆的 SG 函数是所有后继的 SG 的 $\operatorname{mex}$，因此： $$SG(x)=\begin{cases}\operatorname{mex}\{SG(x-1)\},&x\bmod 2=1\\ \operatorname{mex}\{SG(x-1),SG(\frac{x}{2})\},&x\bmod 2=0\text{ and }k\bmod2=1\\ \operatorname{mex}\{SG(x-1),0\},&x\bmod 2=0\text{ and }k\bmod2=0\end{cases}$$ 接下来就是分讨 $k$ 为奇数还是偶数的情形了，容易推出在 $O(\operatorname{log}a_i)$ 时间内计算单堆石子 SG 的算法，这里就不赘述了。 :::: ### VIII 难度：紫。 给定一棵 $n$ 个点的树，最开始只有根节点是白色，其他点都是黑色，两人轮流进行操作，不可操作者输。 操作：选择一个白色的非叶子节点，将其染黑，并将其至少一个儿子染白（可以不止一个）。 先后手谁会赢？ $n\le 10^6$。 ::::info[sol] 练习点：SG 函数。 目标就是求出 $SG(root)$。 设 $S_x$ 为 $x$ 的儿子集合，则根据 SG 函数的递推和游戏和的 SG 有： $$SG(u)=\operatorname{mex}_{T\subseteq S_x}\{\oplus_{v\in T}SG(v)\}$$ 也就是儿子集合的所有非空子集的 SG 的异或和取 $\operatorname{mex}$。 直接枚举是指数级的。 我们观察这个 SG 的性质，是求出用孩子的 SG 值的数集，最小的无法异或表示出来的自然数（注意此处不能用空集表示 $0$）。 打表/数学归纳法/线性基知识，都可以发现一个关键性质：对于所有 $u$，$SG(u)$ 一定是 $0$ 或者 $2$ 的非负整数次幂。 于是我们对于 $u$，先判断 SG 是不是 $0$，这要求所有儿子中有至少一个 $0$，或者有两个儿子 SG 相同。 如果 SG 不是 $0$，只需要求出所有儿子中最小没出现的 $2$ 的幂，就是最终 SG。 现在我们还需要确定 SG 函数最大能有多大，容易发现最大也不会超过 $n$，因此只有 $\operatorname{log}n$ 种取值，结合刚才说的求解方法，总时间复杂度为 $O(n\operatorname{log}n)$。 :::: ## 更多题目 - [P13872](https://www.luogu.com.cn/problem/P13872) - [P13309](https://www.luogu.com.cn/problem/P13309) - [P13819](https://www.luogu.com.cn/problem/P13819) - [CF850C](https://codeforces.com/contest/850/problem/C) 题目可能不算太难，希望对你的博弈论入门有帮助！ --- 这篇博客部分选自我的学习笔记，由于篇幅较长，若有不完善之处，欢迎指出。 祝大家学习顺利，喜欢上有趣的博弈论！