想当年我第一次在OJ上看到取石子问题第一反应是“这也能算难题”——状态一个数组存过去要么DFS要么DP写出来再说。结果数据范围一出来直接懵了(n) 给到 (10^{18})根本不是让你用搜索硬怼的。再后来陆陆续续刷了巴什博弈、Nim博弈、威佐夫博弈、斐波那契博弈才发现这套东西真正的名字叫“组合博弈论”而取石子游戏就是理解这门学问最顺手的入口。最近算法群和热榜上“博弈论”这个词又频繁出现很多人在问到底怎么入门、怎么下手判断胜负我觉得与其零散刷题不如把经典的取石子模型一次性串起来把必胜态、必败态、异或和、SG函数这些概念放到同一个框架里讲清楚。这篇文章面向两类人一是刚接触博弈论、手里有几道取石子题但只会套模板的入门选手二是已经会做普通Nim、但遇到威佐夫、反Nim、斐波那契博弈会卡壳的进阶选手。我会从一个最朴素的问题“谁站在原地谁输”开始一路推到SG定理顺便把我在实际刷题和比赛中踩过的坑也一并交代清楚。1. 破题必败态与必胜态先搞懂“游戏状态”能怎么迁移1.1 两个词就能概括全部博弈N态和P态很多讲博弈的文章直接丢结论比如“异或和为零就是必败”却不解释为什么。这是最劝退的讲法。先把基本概念定下来。对一个公平组合游戏任意一个局面可以分成两类必胜态N态当前行动的人有策略保证自己最终获胜。必败态P态当前行动的人无论如何操作对方都有策略使自己最终获胜。这里有两个最底层的转移规则如果某个状态存在一条边能走到P态那么这个状态是N态。如果某个状态所有边都只能走到N态那么这个状态是P态。换句话说站在必败态的选手只能眼睁睁把胜势送给对手而站在必胜态的选手只需要找到一个能把对手推进P态的操作。这个定义是递归的终点也很简单在“取完最后石子的人获胜”规则下没有石子可取的状态就是P态因为轮到谁谁就输了。1.2 巴什博弈(m1) 这个周期是怎么冒出来的巴什博弈是最简单的取石子模型有一堆石子总数 (n)每次至少取 (1) 颗最多取 (m) 颗取到最后石子的人获胜。我刚开始也和人一样记结论(n \bmod (m1) 0) 时先手必败否则先手必胜。但我花了好久才真正理解为什么偏偏是 (m1)。道理其实很直观。假设当前轮到对方行动他取 (x) 颗(1 \le x \le m)我总能取 (m1-x) 颗补回去。这样一轮下来两个人合计取走的石子数是固定的 (m1)。所以只要我能把局面控制成“剩余石子数是 (m1) 的倍数”并且让对手先面对这个局面那么无论他怎么取我都能把余数重新补回 (m1) 的倍数。重复下去最后一组 (m1) 颗一定是对手先取他取不完也取不没我补上最后一手结束游戏。所以判断就一句话(n \bmod (m1) 0)先手必败。否则先手第一步取 (n \bmod (m1)) 颗之后把双方每轮总取数保持在 (m1)先手必胜。代码更是短到让人怀疑bool bashGame(long long n, long long m) { return n % (m 1) ! 0; }把这个模型稍微变一变比如“每次只能取 ({1,3,4}) 颗”就不能再用模数套了。这个时候老老实实用一个数组推状态即可(f[0]0)对每个 (i) 扫描所有允许的步长 (s)如果 (i-s \ge 0) 且 (f[i-s]0)那么 (f[i]1)。这种“由P态反推N态”的打表方式是后面一切复杂问题的根基。2. 普通Nim的“异或邪术”为什么几堆石子变成了XOR2.1 核心定理异或和决定一切普通Nim博弈规则如下有若干堆石子双方轮流从任意一堆中取走至少一颗石子可以整堆取完取到最后一颗石子的人获胜。这个游戏的结论大家应该都听过把所有堆的石子数做异或记作 (X a_1 \oplus a_2 \oplus \cdots \oplus a_n)如果 (X 0)先手必败否则先手必胜。我第一次看到这个结论时很抗拒——异或是位运算石子数是整数这两个是怎么扯上关系的后来看了一个证明才通透。证明分两步从 (X \ne 0) 出发一定能找到某一堆 (a_i)把它变成 (a_i a_i \oplus X)并且满足 (a_i a_i)。因为 (X) 的最高位为 (1)必然至少有一堆在这一位也是 (1)改变这一位后 (a_i) 的高位减小所以 (a_i) 确实比 (a_i) 小。这样一次操作后新的异或和为 [ a_1 \oplus \cdots \oplus a_i \oplus \cdots \oplus a_n X \oplus X 0 ] 也就是说任何非零局面都能一步走到零局面。从 (X 0) 出发你取走某一堆若干颗后这堆从 (a_i) 变成 (a_i)且 (a_i \ne a_i)。此时新的异或和变成 (a_i \oplus a_i)这个值不可能为 (0)因为两个不同的数异或不可能是零。也就是说零局面只能走到非零局面。这两条合在一起正好对应前面说的P/N态转移规则(X0) 是P态(X\ne0) 是N态。2.2 一个实际走位看懂先手怎么赢举个例子三堆石子分别是 ((1,3,4))。先算 (1 \oplus 3 \oplus 4 6)非零所以先手必胜。那么具体怎么走(X6) 的二进制是 (110)最高位是第 (2) 位从0开始数需要找一堆在这一位上也包含 (1) 的。(1) 的二进制是 (001)没有(3) 的二进制 (011)第 (2) 位是 (0)(4) 的二进制 (100)符合条件。于是把这一堆变成 [ 4 4 \oplus 6 2 ] 也就是从4颗那堆里取走2颗剩2颗。此时局面变为 ((1,3,2))计算 (1 \oplus 3 \oplus 2 0)正好把对手推入P态。之后无论对手怎么取你都能用同样的方式把局面拉回零异或状态。这就是Nim博弈中“保持异或和为零”的操作策略。2.3 nim博弈的两个易错点第一异或运算的优先级很低我自己写代码时踩过坑if (x ^ y 0) // 错 优先级高于 ^正确的是if ((x ^ y) 0)第二Nim博弈的“取到最后一颗石子获胜”这个前提很关键。如果题目把规则改成“取到最后一颗石子的人判负”也就是反Nim结论会完全不一样这个我放到第四节专门说。3. 变体实战威佐夫、斐波那契、反Nim三种高频题型3.1 威佐夫博弈两堆石子里的黄金比例威佐夫博弈长这样有两堆石子两个人轮流操作可以在一堆中取任意多颗也可以在两堆中同时取走相同数量的石子取最后一颗者胜。这个模型不能直接用XOR因为规则允许“同时动两堆”整个局面并不是相互独立的若干互不相干的子游戏。但可以打表把必败局面找出来。记两堆数量为 ((a,b))假设 (a \le b)。从头枚举((0,0)) 是必败态。((1,2)) 是必败态。下一个必败态是 ((3,5))。再下一个是 ((4,7))。这些必败态也叫“奇异局势”。规律是每次取没有在之前出现过的最小整数作为新局势的 (a_k)然后 (b_k a_k k)其中 (k) 从0开始编号。于是得到序列ka_kb_k00011223534746105813看到 (b_k - a_k k)而 (a_k \lfloor k \cdot \varphi \rfloor)其中 (\varphi \frac{1\sqrt5}{2})这就是黄金比例。这个结论来自Beatty定理竞赛里一般不需要证明直接用即可。所以判断方法就一句话设两堆为 (a \le b)令 (k b - a)如果 [ a \left\lfloor k \cdot \frac{1\sqrt5}{2} \right\rfloor ] 那么当前是必败态先手输否则先手胜。代码实现要注意浮点精度问题bool wythoff(long long a, long long b) { if (a b) swap(a, b); long long k b - a; long double phi (1 sqrtl(5.0L)) / 2.0L; long long tmp (long long)(k * phi 1e-9L); return a tmp; // true 表示必败 }这里我习惯加一个极小的欧拉值 (10^{-9})是为了防止浮点误差导致整型向下取整时差1。后面第五节再展开讲这个坑。3.2 斐波那契博弈对手你最多只能翻倍斐波那契博弈的规则比较别扭有一堆石子第一个人可以取任意数量但不能全部取完此后每个人取的颗数不能超过对手上一次取的颗数的两倍。取到最后一颗的人获胜。结论同样漂亮当且仅当石子总数 (n) 是斐波那契数时先手必败。第一次接触这个结论时我完全无法理解“劣势方到底输在哪儿”。后来看了一个从Zeckendorf定理入手的解释才算真正搞明白。Zeckendorf定理说任何一个正整数都可以唯一表示成若干个不相邻的斐波那契数之和。比如 (n14) 时 [ 14 13 1 ] 因为13和1在斐波那契序列里不相邻。如果 (n) 本身是斐波那契数比如 (n13)先手无论第一步取多少颗最多只能取12颗。后手有个巧妙的应对策略把剩下的石子按照Zeckendorf定理拆成若干“块”用取石子把大块化小、把小块补满总能在回合内“控制”局面节奏。这个过程比较抽象竞赛中记住结论打表验证就够用。如果 (n) 不是斐波那契数先手必胜而且第一步取法是取出最接近 (n) 且小于 (n) 的斐波那契数取走 (n) 减去这个数的差值。之后把局面当作“对手面对一个斐波那契数的堆”来处理。写个判断函数bool fibGame(long long n) { long long a 1, b 1; while (b n) { long long c a b; a b; b c; } return b n; // true 表示先手必败 }这个模型最典型的应用是在阶梯博弈类的入门题里很多题目只是换了个包装核心还是“判断n是否是斐波那契数”。3.3 反Nim游戏最后取到石子的人输结论完全反转反Nim博弈和普通Nim唯一的区别是判负条件互换取到最后一颗石子的人判负。这个条件导致XOR结论失效。我第一次做这类题直接拿普通Nim的异或判了一发结果WA到怀疑人生。反Nim的判断分两种情况如果所有堆的石子数都为 (1)这时胜负只取决于堆数的奇偶性。堆数是奇数先手必须取走一堆 (1)剩偶数个 (1) 给对方对方拿完最后一堆时自己也拿完了但根据规则是“取最后一颗者负”所以先手输。奇数个1 → 必败。如果存在某堆石子数大于 (1)那么结论和普通Nim正好相反——异或和为零时先手必胜异或和不为零时先手必败。这个反直觉的结论第一次见时很容易记混。我后来给自己编了个口诀普通Nim看异或反Nim先看全一全一奇偶定胜负非全一则异或反着判。判断代码bool antiNim(vectorlong long piles) { bool allOne true; long long xr 0; for (long long x : piles) { xr ^ x; if (x 1) allOne false; } if (allOne) { return piles.size() % 2 0; // 偶数个1先手胜 } else { return xr ! 0; // 这里和普通Nim恰好相反 } }注意这段代码返回的是“先手是否必胜”。4. 更大杀器Sprague-Grundy函数把“规则随你定”变成异或4.1 SG函数和mex运算Nim博弈里各堆是相互独立的所以可以直接异或。但巴什博弈的步长集合是 ({1,m})威佐夫博弈允许同时动两堆斐波那契博弈限制上一轮操作这些规则各自不同难道每一种都要重新找规律不需要。Sprague-Grundy定理统一了它们。先定义SG函数。对一个状态 (s)它所有一步可达的后继状态记为 (T(s))。定义 [ SG(s) \operatorname{mex}{SG(t) \mid t \in T(s)} ] 其中 (\operatorname{mex}) 表示“集合中未出现的最小非负整数”。终点状态没有后继其SG就是0。然后神奇的事情发生了如果状态 (s) 代表一个“独立可叠加”的子博弈那么整个组合博弈的胜负只取决于所有子博弈SG值的异或和。异或和为零就是必败态否则是必胜态。为什么SG定理能把任何游戏转化成Nim你可以把SG值理解为“这个状态相当于一个拥有SG(s)颗石子的虚拟Nim堆”。一堆SG为 (x) 的子游戏能走到SG为 (0,1,\ldots,x-1) 的所有时代替Nim堆中“取任意颗石子”的效果至于更大的SG值组合游戏由多个子堆组成时反正最后都是看异或。这个视角一旦建立做题就变成机械计算。4.2 手动推一个SG表以最基础的取石子为例有一堆石子每次只能取 ({1,3,4}) 颗取最后一颗者胜。求SG函数。(SG(0)0)(SG(1)\operatorname{mex}{SG(0)}\operatorname{mex}{0}1)(SG(2)\operatorname{mex}{SG(1)}\operatorname{mex}{1}0)(SG(3)\operatorname{mex}{SG(2), SG(0)}\operatorname{mex}{0,0}1)(SG(4)\operatorname{mex}{SG(3), SG(1), SG(0)}\operatorname{mex}{1,1,0}2)(SG(5)\operatorname{mex}{SG(4), SG(2), SG(1)}\operatorname{mex}{2,0,1}3)(SG(6)\operatorname{mex}{SG(5), SG(3), SG(2)}\operatorname{mex}{3,1,0}2)可以发现SG值会从某个位置开始循环这就是所谓的“周期规律”。竞赛中一般不用在题目里找周期直接把SG打表打到上限即可。4.3 代码模板时间戳优化如果每次求mex都开一个bool vis[]然后memset清空状态一多就会超时。常见的优化是引入时间戳const int MAXN 100005; int sg[MAXN], vis[MAXN], stamp; void calcSG(int n, vectorint steps) { sg[0] 0; for (int i 1; i n; i) { stamp; for (int s : steps) { if (i - s 0) { vis[sg[i - s]] stamp; } } sg[i] 0; while (vis[sg[i]] stamp) sg[i]; } }这样每次只修改vis中碰到的位置不用全局清零复杂度大致是 (O(n \cdot |steps|))。对于多个堆直接异或所有SG值int ans 0; for (int i 0; i m; i) ans ^ sg[a[i]]; if (ans 0) printf(先手必败\n); else printf(先手必胜\n);这里再次出现异或是不是瞬间觉得普通Nim其实只是SG定理的一个特例确实如此Nim游戏每个堆的SG值就是石子数本身。5. 实战中踩过的坑以及怎么快速判断该用哪个模型5.1 模型识别看到题目不要直接无脑SG取石子的变体一眼看不完但根据状态特征可以快速缩小范围。我一般先回答三个问题这是几堆石子每次取石子的限制是什么判负条件是“取到最后者胜”还是“取到最后者负”回答完基本能对号入座整理成一张表模型石子堆数取子限制判负条件判断方式巴什博弈1堆每次取1到m颗最后者胜(n \bmod (m1))普通Nim多堆可从任意一堆取任意颗最后者胜异或和威佐夫博弈2堆一堆取任意颗或两堆取相同颗最后者胜黄金比例公式斐波那契博弈1堆第一次不能取完之后不超过上次的两倍最后者胜(n) 是否为斐波那契数反Nim多堆同普通Nim最后一颗者负全1特判异或取反这张表基本上覆盖了绝大多数算法竞赛里出现的取石子裸题。如果题目不满足上面任何一种再考虑SG函数。5.2 浮点精度威佐夫判断不要裸用double威佐夫博弈里有一个 (\lfloor k \cdot \varphi \rfloor) 的计算。(k) 可能很大如果直接用double算精度不够时向下取整会出偏差。我实测过(k) 到 (10^9) 左右double已经不够安全。我踩过这个坑之后改用long double并加一个极小的修正量long double phi (1 sqrtl(5.0L)) / 2.0L; long long tmp (long long)(k * phi 1e-9L);如果题目给出的数据范围到了 (10^{18}) 级别单纯靠浮点计算的人会吃大亏。更稳妥的做法是改用高精度整数模拟或者提前预处理所有奇异局势用二分判断。不过在一般校赛和面试中long double 1e-9已经够用。5.3 数据范围决定算法不决定模型取石子问题经常把 (n) 给到 (10^{18})这是在逼你放弃O(n)的DP回到数学规律的判断上。很多人一看到“石子堆”就直接开sg数组结果内存爆掉还浑然不觉。我的建议是先看一眼数据范围再决定方案。(n \le 10^6)可以放心打表做SG。(n \le 10^{18})必是公式题或周期题优先考虑巴什、Nim、威佐夫、斐波那契。多个堆但每堆状态数很小先分别算SG再异或。5.4 反Nim的“全一堆”特判是最容易丢分的地方反Nim里如果所有堆都是1异或和不为零但先手反而必败。这个边界条件极其阴险。我见过很多代码主逻辑写得头头是道却漏了这个特判导致奇偶性反了。写题时还容易把普通Nim和反Nim的代码混用。建议把两种判断封装成两个函数命名明确区分免得复核时看花眼。5.5 递归记忆化搜索时小心爆栈SG除了递推也可以用记忆化DFS写。但递归深度在某些“取很少颗石子”的题目中可能很深。比如步长集合里有 (1)每层只减15000层就爆栈。所以能用递推就尽量用递推尤其是OJ环境栈空间不大时。6. 一些竞赛之外的体会为什么取石子游戏值得认真玩最后说点题外话。取石子游戏看起来只是“数学题里的一个文件夹”但它锻炼的能力非常底层识别状态、建立转移、找不变量、从局部最优推导全局结论。这套思维和动态规划相似但比DP多了一层“博弈双方都在理性行动”的假设写代码时一般不需要显式模拟对手因为P/N态和SG定理已经把对手的最优策略压缩进了状态判断里。我给初学者的建议是不要只背结论一定要自己推一遍巴什博弈的 (m1) 周期以及威佐夫博弈的奇异局势表。把前面的表打到第20行盯着它看一会儿你会发现“下一个必败态最小未出现整数 等差数列”的模式会自己浮现出来——这种从原始数据里看出规律的快感比死记公式强多了。如果以后遇到一个全新的取石子变体我一般直接打表观察SG序列找周期再尝试证明。很多所谓的高难题最终都逃不过“SG异或”这个框架。把本文的模型吃透你已经能搞定绝大部分相关考点了。