很多打算法竞赛的同学一遇到“博弈论”三个字就想绕道走。说实话当年我也一样一看到什么“Nim积”“SG函数”“威佐夫博弈”就头皮发麻感觉这东西不是我这种脑回路能驾驭的。但后来被一道题逼到墙角硬着头皮啃了几篇论文和别人的博客才慢慢发现博弈论这块其实有非常清晰的套路入门阶段所有复杂局面到最后都指向几个核心模型——巴什博弈、Nim博弈、SG函数和对称策略。一旦你搞懂了它们的来龙去脉再从结论倒回去看原题会发现大多数博弈题本质上都是在“伪装”成这些经典模型。这篇总结就是写给那些刚接触博弈专题或者接触了但一直没理顺“证明逻辑”的朋友。我会把巴什博弈、Nim博弈、SG函数的完整证明掰开揉碎地讲一遍再配上我实际做题时遇到的例题套路和思考过程。看完之后你至少能明白三件事必胜态和必败态是怎么推导出来的异或操作在Nim博弈里为什么是上帝视角以及SG拆游戏背后的思想到底是什么。顺便也会把我踩过的坑和调试经验一并分享出来这些属于跟队训练、打比赛时才真正学得到的“场外经验”。1. 内容整体设计与思路拆解1.1 为什么博弈题总是从“取石子”讲起所有博弈论入门教材几乎都要拿“取石子”举例子不是没有原因。巴什博弈、Nim博弈甚至后面的一大堆变种底层数学模型都能归结为“若干个石子堆每回合拿取若干谁拿最后一个谁赢”。这个模型抽象度不高但足够承载“公平组合游戏”的所有核心思想。先说一个最基础的共识两个玩家都足够聪明不存在失误输赢在开局就已经被决定。这个设定对很多第一次接触的同学来说很反直觉但恰恰是博弈论最迷人的地方。我们在学习博弈题的时候不是在模拟一个玩家会怎么赢而是在判断“在双方都不犯错的前提下先手到底有没有必胜策略”。我自己的理解方式是这样的把“必胜态”理解成“我在这个状态有办法把一个必败态丢给对方”把“必败态”理解成“无论我怎么操作都会把必胜态交给对方”。这两个定义递归地互锁构成了博弈状态判断的全部基础。1.2 整个专题的知识主线是什么从入门到能做题我建议把知识主线拉成四级台阶。第一级是巴什博弈它告诉你“取物问题”中为什么会有周期的概念。第二级是Nim博弈它把局面抽象成了异或运算这是博弈论里最惊艳的一个跳板。第三级是SG函数它告诉你每一个独立子游戏的状态可以映射成一个整数而这个整数之间用“mex”运算串起来。第四级就是SG定理也叫Sprague-Grundy定理它把“多个独立游戏叠加”的问题一刀切成了“分别算SG然后求Nim-sum”。很多教程一上来就丢给你SG函数的计算模板确实可以应付部分题目但遇到需要构造证明或者需要推导状态规律的题没有前面的逻辑铺垫很容易挂。所以这篇文章在编排上刻意按照递进顺序来把“为什么”放在“怎么用”前面。如果你已经能秒切Nim博弈也可以直接跳到SG函数那一章但建议有空还是从头通读一遍证明过程有帮助理解背后模型的共通之处。2. 巴什博弈一切周期性的起点2.1 巴什博弈的模型定义与必胜判定巴什博弈的规矩非常简单有一堆总数固定的石子两个玩家交替取每次至少取1个、至多取m个取到最后一个石子的人获胜。问先手在什么条件下有必胜策略。先说结论当石子总数n可以表示为(m1)的倍数时也就是n % (m1) 0先手必败反之先手必胜而且必胜策略是每回合取走(m1)减去上回合对手取的数量的石子。这个结论看起来太简洁了简洁到很多人背下来就忘。但你要问两句“为什么”就会发现自己还是不太懂。第一为什么周期数是m1第二先手必胜时的操作逻辑为什么是“永远保持在m1的倍数点”上。我换个方式来表述这个状态。m1是一个临界值无论当前取石子的人拿多少合法的范围是1到m下一回合你能拿到的剩余量都会被控制在1到m这个可控范围内。更具体地说对手一次取走k个石子下一回合你只要取走m1-k个就能保证两个人这一轮的总消耗恰好等于m1。这个总消耗量是恒定的所以我们只需要看总石子数对m1取余是什么结果。当n是m1的倍数时先手无论拿多少都会打破这个“整除平衡”然后再被后手用补数策略拉回下一个整除点。当n不是m1的倍数时先手可以先取走n%(m1)个石子把局面直接变成m1倍数的残局交给对方相当于把必败态完整地转移出去。2.2 巴什博弈的证明与周期思想我们用严格一点的数学归纳来证明这个结论。先定义对于当前局面“还剩x个石子”称其为必败态意思是轮到当前玩家行动时无论他怎么操作最终都会输反之称为必胜态。当x等于0时游戏已经结束轮到的人赢不了所以是必败态。然后我从趋向终点的方向递推来看终局前一个状态x在1到m之间当前玩家可以一次取完所以这些x都是必胜态而x等于m1时当前玩家一次最多只能取m个取完之后剩余量落在1到m之间这些剩余状态全是必胜态所以x等于m1是必败态。继续往上推x等于m2时当前玩家取1个就能把m1这个必败态交给对方所以它是必胜态。m3同理取2个。一直到2m1都只需要取走对应的数量就能落到m1。而2m2呢无论取多少都会落到m2到2m1之间的某个必胜态所以它又是必败态。如此循环递推必败态恰好就是m1的整数倍。这个递推思想是整篇博文最基础也最核心的思维方式往后的Nim博弈和SG函数本质都是相同思路的推广。巴什博弈只是把周期这个概念放在了最简单的一堆石子里不要因为题目简单就跳过这一节的推导。2.3 巴什博弈的变体与在题目中的伪装巴什博弈在题目里不会永远穿“一堆石子”这件马甲。最常见的变形是“取到最后输”和“取石子数量范围变化”就这两个方向的改动就能让一堆人翻车。取到最后输的情况有个很巧妙的处理方式既然谁拿最后一个谁输我可以等价理解为拿完了就输那相当于把游戏的目标改成“避免拿到最后一个”处理时可以直接按n-1来套用原模型。为什么是n-1因为最后一个石子是“罚球”必败方拿到它反而要输等价于局面倒数第二个石子被拿完时就强制结束。这个等价关系在做很多题目时很实用。另外一类常见伪装是每次取的石子数量不是一个连续区间而是限定在某个集合里比如只能取1、5、6个。这种就不能直接套巴什博弈的m1周期了得回到递推法去逐状态手算胜败表或者用后面的SG函数来求。这里先留个钩子能取的数量集合有限时状态胜败表往往会呈现出周期但周期长度需要自己暴力打表找不能做梦直接套m1。3. Nim博弈与异或理论3.1 从一堆石子到多堆石子的跨越巴什博弈本质上是只有一堆石子的模型可博弈论真正好玩的场景从多堆开始。有三堆石子数量分别是a、b、c每一回合你可以选择其中一堆从中取走任意正整数个石子谁取走最后一颗石子谁赢。这就是经典的Nim博弈。单堆的时候问题可以通过简单的整除判断解决。多堆的时候直觉上应该找一个能综合三堆数量的“聚合指标”让我一看这个指标就知道当前局面是必胜还是必败。第一次接触Nim博弈的时候最迷茫的地方就在这里为什么偏偏是全部异或而不是全部求和或者取最大值你可以回忆一下异或运算是什么二进制逐位比对相同为0不同为1。这个性质比起加法和最大值多了两个非常关键的点。第一异或操作在状态转移中天然具备“可逆性”。第二异或为0这个状态在任意合法移动后一定会变成非0反过来任何非0状态一定能通过一次合法移动变成0。这两个性质正是必胜态和必败态判定所需要的。3.2 Nim-sum判定的完整证明引入记号把所有堆石子数量的异或和记为X a1 xor a2 xor ... xor an。结论是如果X等于0当前局面是必败态如果X不等于0当前局面是必胜态。证明分两条腿走。第一条腿证明“从异或为0的局面出发任意一次合法移动都会让新局面的异或变为非0”。这个其实不用高深技巧反证法就够了。假设当前各堆异或为0而你选择第i堆从a_i取到a_i。因为游戏规定必须改变至少一个石子的数量所以a_i和a_i不相等。这时如果我们想象新的异或和X它等于原始异或和0再异或上a_i再异或上a_i因为除了第i堆以外其他堆的数字都没变这些堆的异或贡献还是原来的那部分而原有的总和异或为0所以X的值化简为a_i xor a_i。因为a_i和a_i不相等异或结果一定非0。这一步搞定。第二条腿证明“从异或为非0的局面出发一定能找到一次合法移动使新局面的异或和变为0”。这个方向需要构造。设当前X不等于0看X的最高位二进制中第k位是1。必然至少有一堆石子a_i在第k位也是1。我构造如下把a_i这堆改成a_i a_i xor X。等下会有人担心a_i会不会大于a_i如果大了我就不算合法移动了。这里有个关键性质因为X的最高位是第k位而第i堆在这一位上是1那么做异或之后a_i的第k位会变成0但a_i第k位原来是1。这意味着a_i在最高不同位上的值是0而a_i是1。比较二进制大小从最高位开始第一次出现差异的地方a_i已经比a_i小了因此a_i一定小于a_i。所以从第i堆取走a_i - a_i颗石子是完全合法的操作。之后新局面的异或和就是原来的异或和X再异或掉原来的第i堆数值a_i再异或进新的a_i。化简一下就是X xor a_i xor a_i把a_i a_i xor X代入得到X xor a_i xor (a_i xor X) 0。构造成功。两条腿都落地了加上终态全0局面显然是必败态Nim结论得到完美闭环。第一次看这个证明的时候我觉得那个“最高位取反”的构造尤其精髓它不是随机试出来的而是基于“要让所有堆异或归零必须更正二进制中所有1的位置”这个原则推出来的。3.3 必胜策略的构造与实操示例光会判定还不够真正比赛里经常要求你输出第一步的具体操作。我们走一个实际例子来体会构造法。假设三堆石子数量分别为5、7、12。先把它们写成二进制形式5是01017是011112是1100。做逐位异或得到1010即十进制的10。因为10不是0所以先手必胜。现在要决定该动哪一堆、改成多少。按照证明里的构造看异或结果10的最高位是第3位二进制从低位往高位从0开始数10的二进制是1010最高位是3。此时需要在堆中找到一个第3位为1的数。12的二进制是1100满足条件。将12异或10得到0110也就是6。6小于12所以操作合法。因此先手策略就是把12那堆取走6颗留下6颗。取完后三堆变成5、7、6异或和是5 xor 7 xor 6 0局面交到后手手里就是必败态。单看这个例子可能觉得是碰巧算出来的我推荐你在纸上多验证几个三堆的随机数字。验的次数多了你会发现异或非0的情况总能通过一次操作归零而能归零的那一堆往往不止一个候选。候选中的任何一堆都可以但结果堆数必须小于原来的数这一步务必检查。3.4 Nim博弈和巴什博弈的内在联系这两种模型本质上有什么共同点你可以把巴什博弈看成是Nim博弈的一个极端退化版本。想象Nim博弈中所有堆都只有一颗石子而且每次只能取一颗其实就是很多堆“必须整堆清空”的游戏。但巴什博弈里一堆石子可以取1到m个这是数字的连续变化和Nim的“任取任意多”相比限制条件更多。不过从必胜态的判定方式来看两者都遵循“可以从必败态转移”和“无法从必败态转移到必败态”这两条公理。差异在于聚合指标巴什博弈用模运算Nim博弈用异或。如果你以后再做“可以取任意多块的正整数分割”之类的题会发现它们的判断指标又变成了其他的等价关系。形式上不同内功心法完全一致。4. 从单一游戏到复合局面SG函数的心法4.1 为什么需要SG函数Nim博弈虽然漂亮但它有一定的局限性每堆石子只能取任意正整数个取完就停。真实比赛里的博弈题往往规定一次能从某堆中拿的数量必须是一个指定集合或者一个局面能分裂成两个局面。这时再直接套异或函数就不灵了我们需要一个更通用的工具来刻画“单堆单个游戏的胜负本质”。于是SG函数登场。它的正式定义是递归的对于一个状态xSG(x) mex{ SG(y) | x可以一步转移到y }。其中mex的意思是最小排除值也就是从0开始数第一个没在集合里出现过的非负整数。举个例子假设某堆石子当前有0颗没有合法后继状态集合为空mex(空集) 0所以SG(0) 0。如果当前有1颗能转移到0后继状态集的SG值为{0}mex{0} 1所以SG(1) 1。如果当前有2颗能转移到1和0后继状态SG集合为{1, 0}mex{0, 1} 2所以SG(2) 2。在“每次能取任意正整数”这个规则下SG(x)恰好等于x。这个性质不是巧合它说明Nim博弈本身就是SG函数的一个特例。4.2 SG(x)0才是必败态的原因先把结论说清楚在一个单独的游戏中当且仅当SG(x) 0时当前状态x是必败态。这个结论可以用一条很短的归纳证明。终态必然没有后继所以它的SG值为0同时它也是必败态起点成立。假设所有后继状态的“SG是否为0”与“必胜必败”的对应关系已经成立当前状态SG(x)的值由mex计算得到。如果SG(x) 0意味着所有后继状态的SG值都不等于0因为0被mex排除了而0是出现过才不能被纳入。既然所有后继都是必胜态当前状态只能交给对方一个好局面所以当前状态必败。反过来如果SG(x)不等于0那SG值是一个正整数设为kmex({...}) k意味着0一定在后继状态SG集合中也就是说一定存在一个后继状态y满足SG(y) 0那么这个后继是必败态当前玩家可以转移到这个必败态所以当前状态必胜。这就是为什么很多代码模板里直接把“SG值是否为0”当作判断胜负的标准。这条证明没有依赖具体规则因此适用于任何公平组合游戏。4.3 SG定理复合游戏的神器真正让人激动的结论是SG定理也叫Sprague-Grundy定理如果一个大局由若干个互不干涉的子游戏组成每回合玩家恰好选择其中一个子游戏操作一次那么整个大局的SG值等于所有子游戏各自SG值的异或和。这个定理允许我们把一个复杂的复合游戏拆成多个简单游戏分别算SG值最后做一次Nim-sum判断。证明思路和Nim博弈的证明非常相似可以分成两个方向。第一从总SG值为0的局面出发一次只能改一个子游戏的SG值对于这个子游戏新的SG值必然不等于旧的SG值。由于其他子游戏SG值不变整体异或结果就会变成“旧值异或新值”而这两个值不同所以异或结果非0。第二从总SG值非0的局面出发采用Nim的修法和所有“其他子游戏原异或和X”对应的最高位调整策略找到那个需要调整的子游戏。通过SG函数的mex定义一定能找到一条转移路径把它变成想要的更小SG值。注意这里要保证选择调整的子游戏确实存在“达到目标SG值”的后继状态mex定义保证了这一点。所以在实际做题时我们不需要关心复合游戏的完整状态空间有多大只需要分别求出每个独立部分从起点出发所能到达所有状态的SG值。空间和时间复杂度比直接搜整个大局面低了一个数量级甚至更多。4.4 手算SG序列时的常用技巧SG序列经常需要自己手动打表尤其在题目规模不大、规则比较特殊时手推比写程序还快。手推有几个技巧强烈建议掌握。第一打表前先把状态定义清楚。很多同学手推乱掉是因为没有明确“当前状态是什么”。比如“一堆石子每次能取2或3颗”状态就是剩余石子数而“棋盘上骑士走日字”这种题状态就是坐标(x, y)。有了状态定义转移才算有依据。第二mex只需要看所有直接后继的SG值不要贪心去算更深层的状态。手推的时候一层一层往外推先把所有终态的SG标成0然后从终态反推前驱。每算出一个新状态的SG随时更新前驱集合。这个过程很像记忆化搜索的逆序版本。第三对于“每次取2或3颗”这样的规则SG序列往往会出现周期性。我见过很多同学没有意识到周期可以直接剪掉硬推到了几百个状态。事实上当连续一段SG值的排列在前面出现过一次之后就会无限循环。发现周期的标准是连续一段长度大于一个安全阈值并且与前面某段完全相同此时可以直接把序列延伸到n。周期长度不固定通常取前面足够长的部分作为判断基准。5. 例题实拆拿到一道博弈题该想什么5.1 先判断是不是公平组合游戏我强烈建议在写任何代码之前先用以下特征做一个快速分流。公平组合游戏的判断标准有五个两个玩家轮流行动任何人都可以走所有合法状态没有随机因素不涉及隐藏信息保证游戏在有限步内结束。如果题目满足这些条件基本可以确认是博弈论模型如果涉及概率就要转期望DP如果涉及不对称的操作集合就要从SG定理的适用条件来额外检查。实际做题中有一种很常见的陷阱就是“某些状态对先手和后手来说能走的边不一样”这种不对称游戏不能直接套公平组合游戏模板需要改造状态定义把“当前轮到谁”也并进状态里。但这样做往往会让状态数翻倍做题时如果发现SG思路全局不通就应该停下来检查规则公平性。5.2 例题一单堆取模问题的巴什博弈实战题目描述大意有一堆石子数量为n两个人轮流取每次能取1到m个取到最后一个石子的人获胜。但是m可能很大n也可能很大直接模拟肯定不行。这类题就是标准的巴什博弈判定条件就是n%(m1)是否为0。很多同学会在这里犯一个经典错误把m1写成了m。我吃过一次亏那次题目的m是5周期是6而不是5因为一次最多取5个两个人轮流取一轮的总消耗量可以达到6。建议自己拿小数字手推验证比如n6每次最多取5个先手取1个后手可以取5个刚好取完取2个后手取4个取3个后手取3个取4个后手取2个取5个后手取1个。后手都能把总消耗凑成6所以n6确实是必败态。如果题目要求输出具体步骤先手只需要第一步取n%(m1)个之后每步都按“m1-对手上一步取的数量”来应对。不要用随机策略也不要看着剩余数量贪心补数策略是保证周期性取胜的唯一方法。5.3 例题二多堆Nim的变种与输出第一步题目描述大意有三堆石子每堆数量给定可以任意选择一堆拿走任意正整数个问先手能否获胜如果能输出一种第一步操作方案。标准的Nim博弈判定加构造按我前面说的流程来。先计算三个数的异或和X。若X为0直接输出先手必败。否则遍历每一堆a_i计算a_i a_i xor X若a_i a_i则这一堆是合法的操作目标输出取走a_i - a_i个石子的方案。这里特别提醒两个检查点第一a_i必须严格小于a_i否则意味着你实际上是在“加石子”这种操作不合规则。出现过同学直接按max伪造结果导致输出错误。第二当存在多堆满足条件时任意输出其中一堆即可不要求最小或最大的取法判断系统一般只验证操作后的局面SG值是否为0。自己本地测试的时候可以用“操作后全局异或是否为0”来自查。5.4 例题三使用SG函数的复合游戏拆解题目描述大意若干堆石子每堆的数量不一定相同。每次操作可以选择一堆如果这堆里有x颗石子你可以把它分成两堆要求分出的两堆都非空且不等于原来的石子数。取完所有石子的人获胜。这个题直接套Nim异或就不行了因为一次操作不是单纯取走而是把一个堆分裂成两个新堆。这种“分裂型”操作需要借助SG函数处理单堆再把每堆的SG值异或起来。单堆状态的转移定义对于状态xx 2一次操作后变成两个正整数对(a, b)满足a b x且a 0b 0。后继状态是“两个独立的子游戏”每个子游戏又各自是一个“单堆石子分裂游戏”。根据SG定理在一个拥有两堆石子的“子局面”中它的SG值就是SG(a) xor SG(b)。所以状态x的SG(x) mex{ SG(a) xor SG(b) | a b x, a 0, b 0 }。接下来打表找规律SG(0) 0SG(1) 0因为没有合法分裂。SG(2)可分裂为(1,1)SG(1) xor SG(1) 0mex{0} 1。SG(3)可分裂为(1,2)SG(1) xor SG(2) 0 xor 1 1mex{1} 0。SG(4)分裂方案有(1,3)SG(1) xor SG(3) 0 xor 0 0(2,2)SG(2) xor SG(2) 1 xor 1 0所以后继SG集合只有{0}mex{0} 1。SG(5)(1,4)给出1SG(1) xor SG(4) 0 xor 1 1(2,3)给出1 xor 0 1所以后继集合{1}mex{1} 0。往下推会交替出现0和1规律就是奇数堆SG为0、偶数堆SG为1。算完单堆SG之后所有堆的SG异或和就是最终判定。这道题过后你会对“把一个局面操作等价成对若干独立游戏做Nim-sum”这个思想有实质性的体感。6. 常见问题与排查技巧实录6.1 误区一把SG值当成了必须取的石子数SG值是mex得到的“判断指标”不是“这一堆我该取多少颗”。我把这两者搞混的那阵子写过很多错误的输出方案。正确的思路是先用SG值判断全局胜负然后如果要构造方案再回到原始题目规则里去找具体操作而不是直接用SG值操作。比如某个状态SG值为3根本不代表这堆里有3颗石子可拿而是代表“它等效于一个3颗石子的Nim堆”这个等效性很抽象但实际应用时你只需要利用它的标号特性。构造时要重新关注原题的转移关系找到那个能让全局异或归零的具体后继状态。6.2 误区二状态定义不包含“当前轮到谁”公平组合游戏的定义里包含了一个默认条件游戏规则对两个玩家完全相同而且当前局面能走哪些边只取决于局面本身不取决于轮到谁。如果你把“轮到谁”也加入状态定义SG分析会变得复杂得多。要尽量把规则设计到公平的游戏里如果确实有玩家专属操作那说明这道题可能不是用SG函数模板能解决的需要升级成“非对称博弈”来处理。初学者最容易犯的错误是把所有博弈题都当成两个人轮流操作就能套SG而忽略了“当前玩家是否能移动某个棋子取决于另一个棋子的位置”这类耦合规则。一个子游戏的边界如果不清晰SG值就算出来了合并不一定正确。6.3 误区三贪心取最大堆或最小堆在Nim博弈中如果异或和为零我们先手必败千万不要试图“通过拿走较多石子来改变命运”因为任意合法操作都会把局面变成异或非零而对方存在一步修正操作把异或归零。哪怕你第一眼看过去某堆数量很大似乎取走一部分后对方就无法应对了但实际上这种判断是错觉。记得有一道题我赛中快结束时想贪心一把看到三堆是7、8、15异或和8非0于是贪心地想取掉15那堆的大部分。一算才发现异或和8把15改成7才是正解也就是取走8颗留下7颗而不是把堆掏空。如果贪心掏空15新异或和变成7 xor 8 xor 0 15非0对方立刻可以修正。所以永远不要放弃异或这个判定工具去凭感觉操作。6.4 排查流程从算法到实现的故障定位写博弈题代码时经常出现“判定对了但输出方案错了”的情况这个我深有体会。建议按照下面的流程排查。先检查异或和计算是否正确尤其是多个变量名混用的时候很容易把某堆覆盖掉。再检查a_i的合法性判断很多人漏了a_i a_i。然后检查mex实现求mex之前要把后继SG集合去重排序集合里有重复值不能用数组长度直接判空。最后检查边界状态比如n0、m1、只有一堆石子这些极端情况用打表验证终值。如果是SG函数实现暴露出问题建议把打印SG值输出到文件里小范围打表观察规律。SG序列有周期的可以当即剪枝没有周期的就要考虑算法复杂度是否可以接受。我遇到过好多次“打表发现周期但代码里没有剪枝导致TLE”的情况周期检测不是可选项而是SG题目的标配优化。6.5 做题顺序比刷题量更重要最后分享一个我自己调整过多次的专题训练顺序。不要一上来就开SG专题狂刷题那样很容易被各种变形打懵。先花一天时间把巴什博弈证明到会自己推导的程度然后用十道左右的经典Nim变体题巩固确保能独立写出“判定加构造方案”的代码。接着手推至少三组SG序列每一组都对照程序验证再把SG定理用于复合游戏题。这样走下来你再看大多数博弈题的时候脑子里会自动浮现“这是巴什”、“这是Nim”、“这是SG拆分”的分类标签。当年我一位队友说过一句话我一直记到现在博弈题不是靠背结论而是靠把结论放在脑子里的逻辑推演里。结论会忘但推演套路一旦熟练题目再怎么变都能找到入口。这篇文章写到这里已经覆盖了从巴什到SG的全部核心证明和例题路径剩下的就是你自己动手去把每一条递推亲手走一遍。把一个游戏状态的SG表从头到尾推出来一次比做十道复制模板的题都管用。
