专栏文章

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

MMPLN
算法·理论参与者 12已保存评论 12

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
12 条
当前快照
1 份
快照标识符
@mie4n46k
此快照首次捕获于
2025/11/25 13:20
3 个月前
此快照最后确认于
2025/12/05 01:10
3 个月前
查看原文
这是一篇博弈论的入门文章，同时也整合了作者的学习笔记，并对所有例题作了详细讲解，希望能帮到你！
内容包括但不限于：
  • 游戏的概念和基本运算
  • 博弈图
  • 胜负的求解方式
  • SG 函数与 SG 定理
  • 博弈论应用与常见套路

引入

相信大家都玩过这个游戏：有一些火柴，两人轮流操作。每次操作可以取走一根或者两根，取走最后一根的获胜。
从这里开始，为了方便，我们都假设参与游戏的玩家都是天才，一定会采取最优策略。
不难发现，当火柴的数量是 33 的倍数的时候，先手会输，否则先手会赢。
简单的证明就是：我们可以维持轮到对手的时候火柴数量是 33 的倍数，且轮到自己的时候不是。具体地，对手取 xx 根，我们就取 3−x3-x 根。那么因为 00 是 33 的倍数，那么没有火柴的时候一定轮到对面，对面输。
上述过程就是数学归纳法在博弈论中的体现。
如果是能取走 1∼k1\sim k 根火柴呢？只需要把“33 的倍数”改成“k+1k+1 的倍数”即可，道理是一样的。
这个游戏就是公平组合游戏。

介绍

公平组合游戏，当然以公平为基本原则。具体地，都需要满足这些东西:
  • 对于任意状态，当前玩家可选择的行动仅取决于当前状态，与身份无关；
  • 博弈中的同一个状态不可能多次抵达，博弈以参与者无法行动为结束，且博弈一定会在有限步后以非平局结束。
一般情况，我们遇到的游戏都是两名玩家轮流操作，分别是先手和后手。
我们将局面分为：
  • 必胜局面，表示先手必胜；
  • 必败局面，表示先手必败（后手必胜）。
同理，从一个局面出发，到后面局面形成的决策过程，总体被称为必胜游戏或必败游戏。
显然，所有局面要么必胜，要么必败。

博弈图

观察我们对于公平组合游戏的定义：同一个状态不可能多次抵达。那如果我们把每一个局面看作一个节点，并向可一步到达的局面连有向边（这些局面被称为后继局面），则我们会得到一个 DAG（有向无环图）。
这个 DAG 没有入边的点就是初始局面，没有出边的点就是已经无法继续操作的必败局面。
这个图被称为博弈图。
怎么确定一个节点是必胜局面还是必败局面呢？可以从定义入手：
  • 如果至少一个后继局面是必败局面，那么这个局面必胜（可以走到让对面必败的地方）。
  • 如果所有后继局面都是必胜局面，那么这个局面必败（怎么走都会让对面必胜）。
  • 如果没有后继局面，那么显然已经输了，必败。
很多时候，直接通过上述判断方法，就可以递推出每个节点是必胜还是必败。

Nim 游戏

有 nn 堆石子，第 ii 堆有 aia_i 个石子。两名玩家依次操作：每次操作可以选择一堆非空石子堆，并取走至少一个石子。不能操作者输。
先考虑单堆 Nim 游戏。在 n=1n=1 的时候会怎么样：显然当 a1>0a_1>0 的时候为必胜局面（一次取完）；当 a1=0a_1=0 的时候为必败局面（开局就动不了）。
如果 n>1n>1 呢？结论是简单的：
局面必胜的充要条件为 a1⊕a2⊕⋯⊕an≠0\bold{a_1\oplus a_2\oplus\dots\oplus a_n\ne0}。
其中 ⊕\oplus 为按位异或。
证明方法
证明的思路顺其自然，首先是充分性：
我们拿到这样一个可爱的必胜局面，就去努力让对面拿到 a1⊕a2⊕⋯⊕an=0a_1\oplus a_2\oplus\dots\oplus a_n=0 的必败局面。最后无法操作的时候显然异或和也是 00，这样这个局面只有对面能拿到，我不就赢了？
怎么去操作呢？我们找到异或和 ss 的最高非零位 dd，然后去操作某个第 dd 位也是 11 的 aia_i。取 kk 为 s⊕ais\oplus a_i ，再将 kk 所有 <d<d 的位取反，不难发现此时 k<aik<a_i，将 aia_i 减少成 kk 后异或和 ss 就变成 00 了。
必要性：
如果我拿到 a1⊕a2⊕⋯⊕an=0a_1\oplus a_2\oplus\dots\oplus a_n=0 的局面，操作后肯定 a1⊕a2⊕⋯⊕an≠0a_1\oplus a_2\oplus\dots\oplus a_n\ne 0，对面按照上述方法操作我就输了。
我们称自然数列 aa 的异或和，成为其 Nim 和。
Nim 游戏作为典型的公平组合游戏，在后续研究中极其重要。

游戏之间的关系

对于游戏 GG 和 HH，我们接下来研究 G+HG+H 是啥。
什么？游戏也能加起来？
游戏 G+HG+H，即 GG 和 HH 互不干扰地进行，且：
  • 玩家每次操作只能选择在 GG 或者 HH 中操作一次。
  • 当 GG 和 HH 都无法操作的时候，游戏结束，无法操作者失败。
也就是说，G+HG+H 是同时玩 GG 和 HH 两个子游戏的游戏，它也具有公平组合游戏的各种性质。
而且这个加法也满足结合律和交换律。
容易发现对于 n>1n>1 的 Nim 游戏，相当于 nn 个单堆 Nim 游戏的和。
有了加法这样一个工具，就可以去试着定义游戏的等价关系了。
游戏 G≈HG\approx H，当且仅当对于所有游戏 II，G+IG+I 和 H+IH+I 胜负状态相同（要么都是必胜游戏，要么都是必败游戏）。
其中 ≈\approx 是等价符号，注意并不一定是 ==，因为游戏千千万万，我们所说的等价是在决策过程所引出的结果上没有区别。
从这里我们可以发现一个非常关键的性质：两个等价的游戏的和是必败游戏。
证明
因为 G≈HG\approx H，所以 G+G≈G+HG+G\approx G+H；因为 G+GG+G 是必败游戏，所以 G+HG+H 是必败游戏。
G+GG+G 是必败游戏可以从定义证，先手玩家不管选哪个操作，后手都可以模仿，在另外一个进行相同的操作，使得两个子游戏保持相等。最终一定是先手玩家先无法操作。
这一性质也可以通过后续的 SG 函数来证明。
好，说了这么多，都是为了引出下面这个定理。

SG 定理与 SG 函数

这一部分许多定理的证明较为复杂，限于篇幅，在本文中没有写出证明步骤，读者若想了解可以自行搜索。
SG 定理：
任何公平组合游戏都等价于某个单堆 Nim 游戏。
这个有啥用呢？我们可以给所有游戏 GG，赋值一个函数 SG(G)=xSG(G)=x，其中 xx 就是 GG 所等价的单堆 Nim 游戏的石子数量。
那么我们判断 GG 是必胜还是必败，只需要看 SG(G)SG(G) 是否 >0>0。
这里的 SG()SG()，就是 SG 函数。
游戏的和的 SG：
SG(G1+G2+⋯+Gn)=SG(G1)⊕SG(G2)⊕⋯⊕SG(Gn)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)=mex⁡G′∈GSG(G′)SG(G)=\operatorname{mex}_{G'\in G}SG(G')。
其中 G′∈GG'\in G，表示 G′G' 是由局面 GG 走一步能得到的局面。
mex⁡\operatorname{mex} 为集合中最小未出现的自然数。
有了这个式子，就可以更方便地推出各种局面的 SG 值，来判断谁能赢了。
学会 SG 函数后，先别着急用，因为暴力求 SG 还是指数级别的，并非所有题都能使用。
而用到 SG 函数的题一般否需要找到关键性质，才能快速推出我们需要的 SG 值！
所以在博弈论题中，大部分题不能纯靠推，需要依靠打表或者超强注意力等手段找到初步规律（或 SG 函数的规律）。或从基本的公式出发找性质。
至此，对于公平组合游戏的基本概念，以及 SG 函数的介绍就基本结束了。
现在，考虑进入具体问题来探索！

应用策略 & 例题

O

策略讲解都在 Sol 中，因此前面题目即使会做也可以看看。
  • 此部分题目并不完全是洛谷题目，难度评价作参考。解法为我的做法，不一定只有一种
  • 更重要的是思考过程，最开始不会做可以放心看解法，只要经过充分思考，猜测和打表很重要！
  • 不需要对每道题都去写代码，毕竟很多题目都是结论为主。
  • 都是我精选的好题 qwq。

I

来源：P4860，难度黄。
有 nn 个石子，每次可以取走 11 个或者 pp 个（pp 为质数）。无法操作者失败，先后手谁会获胜？
n≤1018n\le 10^{18}。
题目链接。
sol
练习点：打表。
手推或者运用博弈图性质（必胜点后继至少一个必败，必败点后继都是必胜）打表，可以算出 nn 较小的时候的胜负状态，即可发现先手必胜当且仅当 n mod 4≠0n\bmod 4\ne 0。
可以去证明这件事情，仍然是数学归纳法。n<4n<4 显然是对的。对于 k≥4k\ge 4：
  • k mod 4=0k\bmod 4=0，必败。由于 11 或者任意质数都不是 44 的倍数，所以我们要么已经无法操作（k=0k=0），要么会在操作后让对手拿到 k mod 4≠0k\bmod 4\ne 0。
  • k mod 4≠0k\bmod 4\ne0，必胜。我们可以一步操作让对手拿到 k mod 4=0k\bmod 4=0 的局面。这是显然的，因为 1,2,31,2,3 都是可以用的数字。

II

来源：USACO，难度绿。
若当前有 xx 个石子，设其十进制最大数码为 aa，最小非零数码为 bb，玩家可以取走 aa 或 bb 个石子。最开始有 nn 个石子，问先后手谁会获胜？
n≤106n\le 10^6。
题目链接
sol
练习点：博弈图递推。
这里具体讲一下递推步骤。
设 fif_i 表示最开始有 ii 个石子，先手是否会获胜，用 0/10/1 表示。
那么 O(log⁡n)O(\operatorname{log}n) 求出 a,ba,b 之后，若 fa=fb=1f_a=f_b=1，那么 fi=0f_i=0；否则 fi=1f_i=1。
再搬一次基本理论！先手必胜点至少一个后继是后手必胜点（必败点），后手必胜点（必败点）所有后继都是先手必胜点！

III

难度绿/蓝。
有 nn 堆石子，第 ii 堆有 aia_i 个石子。两名玩家依次操作：每次操作可以从第一堆中拿走至少一个石子，或者从第 ii（i>1i>1）堆中将至少一个石子移动到第 i−1i-1 堆。无法操作者失败，先后手谁会获胜？
n≤107,1≤ai≤1018n\le 10^7,1\le a_i\le 10^{18}。
sol
练习点：Nim 游戏，游戏转化。
发现可以忽略第偶数堆，并将奇数堆看作普通 Nim 游戏，因此先手获胜条件就是 a1⊕a3⊕a5⊕…≠0a_1\oplus a_3\oplus a_5\oplus\dots\ne 0。
设这个只考虑奇数堆的 Nim 游戏为 HH，原游戏是 $G，证明还是类似：
如果 HH 必胜，那么先手就从奇数堆正常进行操作：拿走（对于第一堆），或者移到左边那堆偶数堆（对于其它奇数堆）。这些 GG 移动的石子，不管拿走还是放到偶数堆，都不再在 HH 中考虑，所以就相当于 HH 的一次操作，仍然可以获胜。
如果 HH 必败，那么先手怎么挣扎都没用，首先如果操作奇数堆，那像刚才说的，就和 HH 的一次操作等价，既然不跳出 HH 而且 HH 必败，那么当然无法获胜。如果操作偶数堆，那么对手把我们拿到奇数堆的那些石子，再往左移动回另一个偶数堆（或者直接拿走），这一轮在 HH 中相当于两个人都没操作，先手还是必败。
综上，GG 可以看作 HH，即对于奇数堆的独立单堆 Nim 游戏的和，可以直接 Nim 和得到结论。

IV

来源：ARC208A，难度：蓝
有 nn 堆石子，第 ii 堆有 aia_i 个石子。两名玩家依次操作：每次操作可以从某一堆中拿走至少一个石子，需要保证所有 aia_i 按位或的结果时刻不变。无法操作者失败，先后手谁会获胜？
n≤106,1≤ai≤109n\le 10^6,1\le a_i\le 10^9。
题目链接
sol
练习点：Nim 游戏，游戏转化。
和 Nim 游戏不一样在每个出现了 11 的二进制位最终都会留下一个。
考虑钦定每堆石子最终会留下哪些二进制位。钦定之后我们就在游戏一开始把这些位设为 00（提前去掉一些石子），就变成了正常 Nim 游戏，先手失败的条件是 a1⊕a2⊕⋯=0a_1\oplus a_2\oplus \dots =0。
发现我们钦定留下哪些二进制位，就相当于把每个出现了 11 的二进制位分配给某堆这一位是 11 的石子。无论分配给谁，我们最终需要的所有 aia_i 的异或和都是一样的，都相当于在这一位再异或一个 11。
综上，先手必败的条件为 a1⊕a2⊕⋯⊕an=a1∣a2∣…∣ana_1\oplus a_2\oplus \dots\oplus a_n=a_1|a_2|\dots|a_n，也就是异或和再给出现 11 的每一位异或一次后为 00。

V

来源：P11056，难度：蓝。
原题题目足够简洁，见 题目链接。
hintA
不存在模 nn 相同的后手必胜点。
hintB
为所有后手必胜点找一个石子数上界。
sol
练习点：博弈图递推，推理。
性质 1：不存在模 nn 相同的后手必胜点，否则较大者就是先手必胜了（一步可达后手必胜的是先手必胜）。
性质 2：所有后手必胜点 p≤n(n+1)p\le n(\sqrt{n}+1)。
性质 2 证明：考虑反证，假设有大于这个数字的后手必胜点，那么考虑两步：
  • 第一步：从后手必胜点走一步到的所有点都必须是先手必胜点，此时对于 p>n(n+1)p>n(\sqrt{n}+1)，有 >n>\sqrt{n} 种走法是减去 nn 的倍数的。
  • 第二步：这 >n>\sqrt{n} 个和 pp 同余的先手必胜点，必须要能走到至少一个后手必胜点。那么再减去 nn 的倍数是不可能的（由性质 1），只能减去完全平方数，而减去的方案数只有 n\sqrt{n} 种。又因为性质 1，所以这 >n>\sqrt{n} 个先手必胜点所减去的完全平方数必须两两不同，此矛盾，故原假设错误。
博弈图递推前 nnn\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，难度：蓝。
原题题目足够简洁，见 题目链接。
hintA
二分答案后转 0/10/1 串，判定能否拿到 11。
sol
接着 hint。
经过前面的讲解，我们发现数学归纳法确实很有用。所以更进一步，对于某个先手必胜的条件，一般都是要：
  • 可以通过必胜条件让对方拿到必败条件（必胜条件的反面）。
  • 在必败条件中怎么操作都会让对方又拿到必胜条件。
试着找一找先手必胜条件，发现就是：能通过一步操作让剩下的后缀 11 的数量大于等于 00 的数量，边界条件略去。
也可以在构造操作方案的时候发现这个条件。
操作方案就是：
  • 找到所有分割点，满足分割后剩下的后缀 11 的数量大于等于 00 的数量。
  • 选择最后面的满足上述条件的分割点进行分割。
  • 这就说明，分割后的这段后缀，不存在一段后缀满足 11 的数量大于等于 00 的数量。我们可以说明更强的事情：这个后缀所有的非空前缀 11 的数量都大于 00 的数量，不难证。
  • 既然如此，对面不管怎么操作，剩下的区间 11 的数量都大于 00 的数量，仍然满足我的必胜条件。
至于输出操作方案，刚才那个“选取最后一个”是一定最优的，但不一定唯一。可以直接枚举一下分割点，再用对面必败的条件判断即可。

VII

来源：CF603C，难度：蓝。
有 nn 堆石子，第 ii 堆有 aia_i 个。两人轮流操作：每次可以选择一堆减少 11 个石子；或者选择 aia_i 为偶数的堆，将其用魔法变成分开的 kk 堆数量均为 ai2\frac{a_i}{2} 的石子。无法操作者失败。问先后手谁会赢？
题目链接。
sol
练习点：SG 函数。
每堆石子都是分开的子游戏，我们分别计算 SG 函数后异或起来，再检查是否为 00 即可（为 00 先手输）。
对于变成 kk 堆相同石子，如果 kk 是偶数那么异或和就是 00，否则异或和等价于一个这样的石子堆的 SG。
而一个个数为 xx 的石子堆的 SG 函数是所有后继的 SG 的 mex⁡\operatorname{mex}，因此：
\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

难度：紫。
给定一棵 nn 个点的树，最开始只有根节点是白色，其他点都是黑色，两人轮流进行操作，不可操作者输。
操作：选择一个白色的非叶子节点，将其染黑，并将其至少一个儿子染白（可以不止一个）。
先后手谁会赢？
n≤106n\le 10^6。
sol
练习点：SG 函数。
目标就是求出 SG(root)SG(root)。
设 SxS_x 为 xx 的儿子集合，则根据 SG 函数的递推和游戏和的 SG 有：
SG(u)=mex⁡T⊆Sx{⊕v∈TSG(v)}SG(u)=\operatorname{mex}_{T\subseteq S_x}\{\oplus_{v\in T}SG(v)\}
也就是儿子集合的所有非空子集的 SG 的异或和取 mex⁡\operatorname{mex}。
直接枚举是指数级的。
我们观察这个 SG 的性质，是求出用孩子的 SG 值的数集，最小的无法异或表示出来的自然数（注意此处不能用空集表示 00）。
打表/数学归纳法/线性基知识，都可以发现一个关键性质：对于所有 uu，SG(u)SG(u) 一定是 00 或者 22 的非负整数次幂。
于是我们对于 uu，先判断 SG 是不是 00，这要求所有儿子中有至少一个 00，或者有两个儿子 SG 相同。
如果 SG 不是 00，只需要求出所有儿子中最小没出现的 22 的幂，就是最终 SG。
现在我们还需要确定 SG 函数最大能有多大，容易发现最大也不会超过 nn，因此只有 log⁡n\operatorname{log}n 种取值，结合刚才说的求解方法，总时间复杂度为 O(nlog⁡n)O(n\operatorname{log}n)。

更多题目

题目可能不算太难，希望对你的博弈论入门有帮助！
这篇博客部分选自我的学习笔记，由于篇幅较长，若有不完善之处，欢迎指出。
祝大家学习顺利，喜欢上有趣的博弈论！

评论

共 12 条评论，欢迎与作者交流。

正在加载评论...