1. 这类问题的本质先搞清楚游戏规则再谈博弈第一次接触取石子游戏是在一场校赛的签到题上。题目描述很简单一堆石子两个人轮流拿每次可以拿1到3颗拿到最后一颗的人赢。当时我还在用DFS硬搜状态结果数据范围直接给到 10^9当场傻眼。后来才知道这种题目背后是一整套系统的博弈论解法而且它的变体几乎覆盖了算法竞赛里所有入门级的组合博弈问题。所谓的取石子游戏核心就几个要素一堆或多堆石子、每回合可操作的拿取范围、胜负判定条件通常是谁拿完谁赢也有反过来的“拿走最后一颗的人输”。一旦把这些规则抽象出来你会发现它本质上是一个状态转移问题——当前局面是“必胜”还是“必败”只取决于它是否能转移到对方的“必败”局面。这个思路和动态规划很像但不同的是博弈双方都在做最优决策所以你推的是“双方都足够聪明”的前提下先手能不能赢。这类问题适合谁来学一个是正在准备算法竞赛的选手模板题几乎必出另一个是想打牢算法基础、准备大厂面试的开发者因为博弈论能很好地考察一个人对状态抽象和规律归纳的敏感度。哪怕你不搞竞赛理解这一套必胜态和必败态的推理方式对日后设计决策类算法也有帮助。这篇总结里我会把三个最经典的取石子模型——巴什博弈、尼姆博弈、威佐夫博弈——从头到尾拆一遍再从它们身上抽出通用的SG函数理论最后附上可以直接抄的C模板和踩坑经验。看完之后你再遇到“取石子”三个字心里应该有底了。2. 先把概念说透必胜态、必败态和状态转移2.1 一个简单的“胜负手”推导过程先拿最简单的情况练手一堆石子共 n 颗双方轮流取每次取 1 到 3 颗。我们不用急着背结论先从最小状态往前推。如果当前剩下的石子数用 n 表示游戏规则是无法取石子的人输也就是取到最后一颗的赢。那么n 0轮到谁谁就输了所以这是必败态n 1、2、3当前玩家直接全取走对手面对 n 0必败所以这些都是必胜态n 4当前玩家只能取 1、2、3 颗把局面交给对手时对手面对的分别是 n 3、2、1全是对手的必胜态因此 n 4 是必败态n 5、6、7当前玩家可以取 1、2、3 颗把局面交成 n 4让对手面对必败态所以这几个都是必胜态n 8又如法炮制取 1、2、3 都只会让对手面对必胜态所以必败。看到规律了没有n 对 4 取模等于 0 的时候必败否则必胜。这里的“4”就是“每次最多取 3 颗 1”得到的。这个推导过程本质上就是博弈树的状态枚举只不过我们用递推代替了每一层的搜索。2.2 必胜态与必败态的递归定义把上面这个过程抽象成通用定义一个状态是必败态当且仅当它所有可达的状态都是必胜态一个状态是必胜态当且仅当它至少存在一个可达状态是必败态。这个定义看似简单但它把“双方最优”这个博弈的前提落到了实处。你不需要真的去模拟对方的每一步棋只需要确信只要我能把局面交给一个必败态那么无论对手怎么走我都有办法继续把他拖回必败态直到终局。这也解释了为什么博弈问题的代码通常很短关键却在找规律。很多新手看到网上几行代码就解出题误以为博弈论就是背结论其实所有结论背后都是这个状态转移推导出来的。所谓“先手必胜”和“先手必败”都只是在整个状态图上沿着最优策略走出来的结果。3. 三大经典取石子模型从巴什博弈到尼姆博弈3.1 巴什博弈Bash Game最基础的一次取上限模型巴什博弈的规则就是上面我们推过的那个一堆石子 n 颗双方轮流取每次至少取 1 颗、最多取 m 颗取到最后一颗的人赢。结论很简洁若 n % (m 1) 0则先手必败否则先手必胜。为什么是 m 1因为无论对手取 x 颗1 ≤ x ≤ m你都可以补上 (m 1 - x) 颗让连续两回合的总取走数恰好是 m 1。这样一来只要一开始把局面的余数部分控制好你就能始终把握节奏。这个“凑 m1”的思路是很多变形题的内核。实际做题时巴什博弈不会只给你这么裸的规则。常见变换包括取石子的人可以先取任意数量的“手续费”这种题本质上还是巴什只需要提前判断一下优劣石子堆是环形的、取完某一颗后整堆消失这时候问题可能变成别的模型规定“取走最后一颗的人输”这种叫反巴什博弈结论也有一个很工整的变体当 n % (m 1) 1 时先手必败否则必胜需要单独记忆。我建议在学习阶段把巴什博弈的原型和反型放在一起对比着推导一遍因为它们几乎是同一棵博弈树只是终局判定的叶子节点反了一下。3.2 尼姆博弈Nim Game异或运算的优雅解法尼姆博弈把石子从“一堆”变成“多堆”。规则是有若干堆石子每堆数量已知双方轮流操作每次只能从其中一堆里取出任意正整数颗石子取走最后一颗的人获胜。这个问题看起来一下子复杂了但实际上它拥有一个极其简洁的判定条件把所有堆的石子数做按位异或XOR设结果为 XOR_sum如果 XOR_sum 0则先手必败否则先手必胜。我第一次看到这个结论时觉得很不可思议为什么异或能刻画一个多堆博弈的胜负后来动手推了几组例子才想通异或为 0 的状态无论你怎么动其中一堆都会把它变成非 0 状态而异或非 0 的状态一定可以通过调整某一堆的石子数把它变回 0。这就完全对应上了我们前面“必胜态可以转移到必败态必败态所有转移都是必胜态”的定义。具体操作上如果你的目标是取胜而不是只判定胜负那么当你面对一个必胜局面异或非 0时需要找到应该在哪一堆拿多少。设总异或值为 s遍历每一堆看 a[i] 的二进制中是否存在一个方案让某堆变成 a[i]使得新的异或值为 0。简单做法是找 s 的最高位在所有该位为 1 的堆里选一堆令 a[i] a[i] ^ s。由于 s 不为 0a[i] 一定小于 a[i]所以操作合法。这一步在输出方案的题目里是标准的套路。3.3 威佐夫博弈Wythoff Game黄金分割比在算法里的用武之地威佐夫博弈又是另一种规则有两堆石子双方轮流操作每次可以从任意一堆里取任意正整数颗或者从两堆里同时取出相同数量的石子取完所有石子的人获胜。用 (a, b) 表示两堆的数量这里假设 a ≤ b。它的结论和前面两个都不太一样引入了无理数比例。判定方式是计算差值 k b - a然后判断是否存在一个整数 t使得a floor(t * (1 sqrt(5)) / 2) 且 b a t这里的 (1 sqrt(5)) / 2 就是黄金分割比 φ。如果满足这个条件说明当前局面是一个“奇异局面”先手必败否则先手必胜。这个结论的推导过程比较长核心在于所有奇异局面之间满足一种递推关系第 t 个奇异局面的第一个数恰好是 floor(t * φ)第二个数是第一个数加上 t。前几个奇异局面是 (0, 0)、(1, 2)、(3, 5)、(4, 7)、(6, 10)、(8, 13)……你可以自己验算一下这些局面之间刚好覆盖了所有非负整数并且互不重复。实战中威佐夫博弈的坑主要在精度。因为要用到浮点数运算如果直接写 a (int)((b - a) * (1 sqrt(5)) / 2)可能会因为浮点误差在边界数据上出错。稳妥的做法是用 long double 计算或者两边同时平方或者把判定改成tmp (long long)((b - a) * (sqrt(5) 1) / 2)然后判断 if (tmp a)。同时要在计算前保留足够高的精度常数不要现场用 float 算 sqrt(5)。4. 找到套路的总钥匙SG函数与多个独立游戏4.1 为什么需要SG函数前面三个模型结论都很优雅但问题来了如果规则不是“取 1 到 m 颗”而是“只能取一个给定集合里的数量比如只能取 2 的幂次颗”或者“有 N 堆石子每次可以从任意 k 堆中各取 1 颗”前面那些公式还能用吗答案是很多都不能直接用。这时候就要请出博弈论里最常用的通用工具——SG函数Sprague-Grundy 函数。它的核心思想是把每一个局面映射成一个非负整数这个数能统一描述“这个局面是必胜还是必败”还能支持多个独立子局面的组合。SG 函数的定义是对于一个局面设它能直接转移到的所有局面的 SG 值构成的集合为 S那么这个局面的 SG 值就是不在 S 中的最小非负整数mex。特别地没有后继状态的终局 SG 值为 0。这个定义和我们前面说的必胜/必败判定有什么关系关系很简单SG 值为 0 的状态是必败态SG 值大于 0 的状态是必胜态。因为 SG 值为 0 意味着它所有后继的 SG 值都不为 0即后继全是必胜态这正好命中必败态的定义。4.2 多个独立子局面的组合SG 异或定理SG 函数最漂亮的地方在于它可以处理多个互不干扰的游戏同时进行的组合。比如取石子问题里有 3 堆石子每堆都是一个独立的“子游戏”玩家的每一步只影响其中一个子游戏那么整个局面的 SG 值就是所有子游戏 SG 值的异或。这个结论叫 Sprague-Grundy 定理。判定方式变成了所有子游戏 SG 值的异或结果 XOR_sum 0则当前局面必败否则必胜。你看这和尼姆博弈的结论形式完全一致。其实尼姆博弈本身就是 SG 函数的一个特例一堆石子数量为 x允许取任意正整数颗时这堆石子的 SG 值就是 x异或起来自然得到尼姆结论。这套理论的价值在于面对很多看似毫无规律的取石子变体你只需要搞清楚“单堆在给定规则下的 SG 值如何计算”然后套异或定理就能解决多堆的复合问题。所以算法竞赛里SG 函数题的解体思路通常分两步走先算单个局面的 SG 值再用异或组合起来。4.3 计算 SG 值的两种方式暴力递推与找循环节直接按定义计算 SG 值可以用 DFS 加记忆化搜索。对于石子数量 n 不超过几千、每次拿取选择数量较少的情况这个办法已经够用。但数据范围一旦到 10^9直接算肯定超时。好在取石子类游戏的 SG 值一般具有周期性或规律性。比如每次只能取 1、3、4 颗的规则可以先把前几十项 SG 值列出来用肉眼或者程序找循环节然后直接把 n 对循环节取模再查表。我在做这类题时有一个习惯先把小范围 n比如 0 到 100的 SG 值全部打表然后观察模式。如果发现有固定循环就大胆优化成 O(1) 判断如果没有循环再考虑题目是否存在更特殊的结构。打表找规律不是歪门邪道反而是竞赛中非常高效的务实手段很多看起来高深的博弈结论最初都是这样发现的。5. 代码模板与实操细节从会推到能写对5.1 巴什博弈的一行判定#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; // n 颗石子每次取 1~m 颗 if (n % (m 1) 0) cout 先手必败\n; else cout 先手必胜\n; return 0; }这段代码几乎不需要解释但请注意它的前置条件每人至少取 1 颗且取最后一颗的人赢。如果题目改成“取最后一颗的人输”判定式要换成 n % (m 1) 1。建议平时就把这两种情况做成两个小函数被反复调用。5.2 尼姆博弈完整流程#include bits/stdc.h using namespace std; int main() { int N; cin N; vectorint a(N); int xorsum 0; for (int i 0; i N; i) { cin a[i]; xorsum ^ a[i]; } if (xorsum 0) { cout 先手必败\n; } else { cout 先手必胜\n; // 如果要输出走法找到应该操作的一堆和应该变成的数 for (int i 0; i N; i) { int target a[i] ^ xorsum; // 让这堆变成 target if (target a[i]) { cout 从第 i 1 堆取走 a[i] - target 颗剩下 target 颗\n; break; } } } return 0; }这里的关键在于 target a[i] ^ xorsum 这一步。你可能会有疑问为什么这样做完异或和会变成 0因为原异或和是 xorsum当我们把 a[i] 替换成 a[i] ^ xorsum 时新的异或和等于 xorsum ^ a[i] ^ (a[i] ^ xorsum)先抵消 a[i]再抵消 xorsum结果一定为 0。同时因为 target a[i] 保证了操作合法。5.3 威佐夫博弈的精度处理#include bits/stdc.h using namespace std; int main() { long long a, b; cin a b; if (a b) swap(a, b); long long k b - a; long double phi (sqrtl(5.0L) 1.0L) / 2.0L; long long tmp (long long)((long double)k * phi); if (tmp a) cout 先手必败\n; else cout 先手必胜\n; return 0; }我强调过精度问题这里用 sqrtl 和 long double 是为了把边界误差尽量往后推。实际比赛中数据范围如果到 10^18这种浮点写法仍然可能翻车。更稳的替代方案是用高精度整数开方后的平方来比较判断也就是把“是否存在整数 t 满足 a floor(t * phi)”转成一个二次方程的整数判定。不过竞赛中大部分题目数据不会那么极端long double 已经能通过。5.4 SG 函数通用模板#include bits/stdc.h using namespace std; const int MAXN 100005; int sg[MAXN]; bool vis[MAXN]; vectorint moves; // 每次允许取的数量 int dfsSG(int x) { if (sg[x] ! -1) return sg[x]; vectorint reachable; for (int v : moves) { if (x v) { reachable.push_back(dfsSG(x - v)); } } int g 0; while (true) { bool found false; for (int r : reachable) { if (r g) { found true; break; } } if (!found) break; g; } return sg[x] g; } int main() { int n; cin n; // 石子总数 int m; cin m; // 可选拿取方式的数量 moves.resize(m); for (int i 0; i m; i) cin moves[i]; memset(sg, -1, sizeof(sg)); sg[0] 0; dfsSG(n); // 求单堆 n 的 SG 值 cout sg[n] \n; // 非 0 则先手必胜 return 0; }这个模板定义了“从当前石子数转移到当前石子数减去某个允许值”的单堆博弈。注意 vis 数组其实可以省掉因为这里只求最小值直接用一个 vector 收集后继 SG 值后再遍历即可。如果要处理多堆只需要把每一堆的 SG 值异或起来。实际做题时moves 和题意强相关比如“每次只能取 2 的幂次颗”那么 moves {1, 2, 4, 8, ...}要先用循环把允许的操作集合生成出来再跑模板。5.5 我的实战代码组织习惯比赛时博弈题的代码通常不长但我会刻意把三类模型和 SG 模板封装成函数而不是全写在 main 里。这个习惯有过一次救了我有一道题是综合题前半部分是一堆单石子巴什博弈后半部分是多堆尼姆博弈场景混在一起如果都堆在 main 里调试的时候极容易把变量搞混。我把代码分成三层输入层负责读题并归一化成统一表示判定层只接收标准规则参数并返回结果输出层负责按题目要求的格式输出。这样无论题目包装成“摆棋子”“分金币”还是“移动纸牌”只要识别出底层模型直接调用对应函数就行。6. 做题最容易踩的坑从规则细节到边界值6.1 规则细节取完最后一颗到底算赢还是算输这个问题听起来简单但实战中翻车率极高。巴什博弈、尼姆博弈、威佐夫博弈的经典结论都建立在“取最后一颗者胜”的前提下。一旦题目变成“取最后一颗者负”称为反博弈结论就要单独推导不能直接套正版的判定。以巴什博弈为例正版是 n % (m 1) 0 先手必败反版是 n % (m 1) 1 先手必败部分资料还要求特殊处理 n m 的情况。尼姆博弈的反版则更麻烦当所有堆都只有 1 颗时胜负取决于堆数的奇偶性否则退化成常规判定。这些特例只有亲手推一遍才能记得牢我建议你在笔记本上把正版和反版各推一遍而不是靠死记硬背。6.2 SG 值计算中的越界和记忆化问题DFS 求 SG 值时最容易犯的错是忘了初始化 sg 数组为 -1导致递归过程中重复状态没有记忆化指数级爆炸。另一个常见问题是递归深度如果石子数量达到 10^5且拿取方式也包括大数量递归栈可能溢出。遇到这种情况有两种处理思路改成自底向上的递推从 sg[0] 开始依次算 sg[1]、sg[2]……直到 n这种方式没有递归开销先在小范围内打印 SG 值观察循环节然后用模运算直接跳过中间过程。我通常先用第二个思路判断题目有没有规律如果没有规律再用第一个思路因为自底向上写起来虽然安全但代码长度和调试成本都会多一截。6.3 威佐夫博弈的输入顺序与精度陷阱威佐夫博弈的两个堆是无序的有人习惯把它当成有序来处理直接拿第一个数当成 a、第二个数当成 b结果在 a b 的场景下把差值算成负数。我自己的习惯是读入后立刻做 swap 保证 a b后面再也不用管顺序问题。精度陷阱前面提到过这里再展开一句如果你用的是 double 而不是 long double在 k 非常大的时候k * phi 的最低位可能会出现 1 的偏差导致 tmp 比真实的 floor 值大 1 或小 1最终判定错误。我见过不少选手因为这里丢分。如果题目数据范围超过 long long 能表示的范围请放弃浮点改用整数高精度方式处理。6.4 输出策略不止要判胜负可能还要输出走法部分题目不会只问“先手是否必胜”而是要求你输出一种必胜策略甚至要求按某字典序输出。这时候巴什博弈还好办因为策略固定尼姆博弈需要遍历找到 target a[i] 的那一堆威佐夫博弈的必胜操作会比较绕需要分三种情况讨论从大堆拿、从小堆拿、两堆同时拿每个情况还得判断操作后是否仍是局势合法。应对这类题我的经验是先落地一个函数给定当前局面返回所有可能让对手面对必败态的操作列表然后再按题目要求的排序规则输出第一个。这样哪怕题目变化输出要求你只需要改排序规则不用重写判定逻辑。6.5 常见问题速查表问题现象可能原因解决方案巴什博弈结果和样例不符谁取最后一颗的胜负规则搞反确认规则后用反版判定 n % (m1) 1尼姆博弈输出走法时 target a[i]用错了当前异或总值的堆计算目标值检查 xorsum 是否被更新过确保每轮用原异或和SG 模板跑大样例超时没有利用循环节或未记忆化打印前 50 项找规律或者改递推威佐夫博弈浮点边界判断错误用了 float 或漏了 long double换 sqrtl 和 long double或转整数判定多堆问题没有异或误把单堆 SG 直接当成答案记住 SG 定理总局面等于所有子局面异或边界石子数等于 0没有初始化 sg[0]明确终局 sg[0] 0这张表是我整理做题记录时总结出来的基本覆盖了新手到进阶选手最容易卡住的点。每次写博弈题之前扫一眼能省不少调试时间。7. 取石子问题的扩展方向与深入研究7.1 从取石子到图论游戏有向图博弈的统一视角取石子游戏看起来只是数学游戏但它的背后是“有向图博弈”把每一个局面看成图上的一个节点把合法操作看成有向边那么胜负判定就是在图上做拓扑式推导。这个视角最大的好处是能让 SG 函数顺理成章地推广到所有有限无偏博弈上而不再局限于石子。比如棋盘上的“移动棋子”游戏、纸牌游戏中“消去成对牌”的规则本质上都能建模成有向图博弈。掌握了这个视角之后你会发现自己遇到新题时有一种“降维打击”的感觉不再需要针对每道题硬凑规律而是先建图再套 SG 框架。7.2 取石子游戏变式限制拿取集合、多堆交叉、随机性引入取石子游戏的变式多到可以单独开一个专题。我挑几个常见的类型简单说一下限定拿取集合每次只能取斐波那契数颗或者只能取质数颗。这类问题 SG 值通常没有一眼看出的公式需要打表找规律每次操作可以影响多堆限制“最多选 k 堆每堆取相同数量”这就变成了“k 尼姆问题”复杂度和普通尼姆完全不在一个量级引入随机因素比如每次取的数量由骰子决定一部分这时候博弈论和概率论就交汇了判定从“必胜/必败”变成了“最大胜率策略”。这些扩展方向在算法竞赛中不会一次全考但理解它们的存在能帮你判断一道题到底是该套模板还是需要现场推新结论。7.3 怎么继续深入学习路径与练题建议回到开头说的“算法笔记”这四个字如果你想把博弈论这块彻底吃透我的建议是分三步走第一步把本文三个模型的正版和反版各写一遍代码并手动推至少 10 组数据验证结论。这个步骤看起来枯燥但能帮你把结论和推导过程牢牢绑定。第二步找一组低配题库从巴什博弈、尼姆博弈、威佐夫博弈的模板题开始然后尝试 SG 函数专项题训练自己在 10 分钟内完成“建模——打表——找规律——套模板”的流程。我以前做题时会刻意把每一道题意想不到的地方记在文档里一个月后回头看会发现自己已经形成了一套“识别模型”的直觉。第三步尝试给取石子游戏换壳。把一个经典模型改造成故事背景不同但数学结构相同的题目然后自己设计数据、验证结论。经常做这种训练后你会发现所谓“新题”大部分不过是旧模型换了个包装而已。8. 一些不那么常说、但很实用的幕后心得写到这里我想分享几段很少在题解里看到、但对实际做题很有帮助的经验。第一件事是“异或和判定的直观理解”。很多初学者背下了尼姆博弈的异或结论却不知道为什么异或能刻画石子堆之间的关系。我自己试着换过一个角度去理解把每一堆石子的数量写成二进制异或和不为 0 意味着这些二进制位中存在某些“位”没有配对成功。一次合法操作的本质是选择一个堆把它的二进制中的若干位翻转而高位的支配性决定了必胜策略的存在。当你理解了这层含义再遇到“每堆数量很大”的场景时就不容易慌。第二件事是“比赛时应对没见过的博弈题”。如果真的遇到一道完全没有头绪的取石子题我一般会先写一个暴力搜索程序把所有小规模局面的胜负情况打出来。然后盯着表格尝试把必败局面列出来看它们之间有什么规律。很多时候结论就是这样被“看”出来的而不是被“推”出来的。这听上去不够优雅但在限时比赛中有效比优雅重要得多。第三件事是关于错题的管理。博弈论题目的代码量通常很小所以你最大的风险不是写不出来而是想错方向后debug会非常痛苦——因为代码太短你甚至不知道该去哪里打日志。我的办法是每次写出结论后先自己构造几组“边界数据随机小数据”用暴力程序跑一遍对照结果确认无误后再提交。不要嫌这一步麻烦我靠它避免过太多次因为边界规则判断失误导致的罚时。第四件事是关于学习节奏。取石子游戏看起来是个小专题但它牵涉到的思维能力——顺推归纳、异或位运算、无理数精度处理、状态压缩思想——都是算法学习的地基。我建议你不要把它当作一个孤立的板块来背而是把它和动态规划、搜索剪枝、数学推导放在一起交叉练习。等你哪一天发现自己能在读题后 30 秒内判断出该用哪个模型再回头做基础题就会有一种“降维”的感觉。第五件事是代码风格。博弈题虽然短但我依然会保持变量名可读、注释清晰的习惯。因为这类题经常在不同比赛里反复出现你需要把“曾经的自己是怎么想的”留给“未来的自己”看。一行注释可能就能帮你省下重新推导半小时的时间这笔账怎么算都不亏。