很多打算法竞赛的同学，一遇到“博弈论”三个字就想绕道走。说实话，当年我也一样，一看到什么“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可以表示为(m+1)的倍数时，也就是n % (m+1) == 0，先手必败；反之先手必胜，而且必胜策略是每回合取走(m+1)减去上回合对手取的数量的石子。
这个结论看起来太简洁了，简洁到很多人背下来就忘。但你要问两句“为什么”，就会发现自己还是不太懂。第一，为什么周期数是m+1；第二，先手必胜时的操作逻辑为什么是“永远保持在m+1的倍数点”上。
我换个方式来表述这个状态。m+1是一个临界值：无论当前取石子的人拿多少（合法的范围是1到m），下一回合你能拿到的剩余量都会被控制在1到m这个可控范围内。更具体地说，对手一次取走k个石子，下一回合你只要取走m+1-k个，就能保证两个人这一轮的总消耗恰好等于m+1。这个总消耗量是恒定的，所以我们只需要看总石子数对m+1取余是什么结果。
当n是m+1的倍数时，先手无论拿多少都会打破这个“整除平衡”，然后再被后手用补数策略拉回下一个整除点。当n不是m+1的倍数时，先手可以先取走n%(m+1)个石子，把局面直接变成m+1倍数的残局交给对方，相当于把必败态完整地转移出去。
2.2 巴什博弈的证明与周期思想
我们用严格一点的数学归纳来证明这个结论。先定义对于当前局面“还剩x个石子”，称其为必败态，意思是轮到当前玩家行动时，无论他怎么操作最终都会输；反之称为必胜态。
当x等于0时，游戏已经结束，轮到的人赢不了，所以是必败态。然后我从趋向终点的方向递推来看：终局前一个状态x在1到m之间，当前玩家可以一次取完，所以这些x都是必胜态；而x等于m+1时，当前玩家一次最多只能取m个，取完之后剩余量落在1到m之间，这些剩余状态全是必胜态，所以x等于m+1是必败态。
继续往上推，x等于m+2时，当前玩家取1个就能把m+1这个必败态交给对方，所以它是必胜态。m+3同理，取2个。一直到2m+1，都只需要取走对应的数量就能落到m+1。而2m+2呢？无论取多少，都会落到m+2到2m+1之间的某个必胜态，所以它又是必败态。如此循环递推，必败态恰好就是m+1的整数倍。
这个递推思想是整篇博文最基础也最核心的思维方式，往后的Nim博弈和SG函数本质都是相同思路的推广。巴什博弈只是把周期这个概念放在了最简单的一堆石子里，不要因为题目简单就跳过这一节的推导。
2.3 巴什博弈的变体与在题目中的伪装
巴什博弈在题目里不会永远穿“一堆石子”这件马甲。最常见的变形是“取到最后输”和“取石子数量范围变化”，就这两个方向的改动就能让一堆人翻车。
取到最后输的情况有个很巧妙的处理方式，既然谁拿最后一个谁输，我可以等价理解为拿完了就输，那相当于把游戏的目标改成“避免拿到最后一个”，处理时可以直接按n-1来套用原模型。为什么是n-1，因为最后一个石子是“罚球”，必败方拿到它反而要输，等价于局面倒数第二个石子被拿完时就强制结束。这个等价关系在做很多题目时很实用。
另外一类常见伪装是每次取的石子数量不是一个连续区间，而是限定在某个集合里，比如只能取1、5、6个。这种就不能直接套巴什博弈的m+1周期了，得回到递推法去逐状态手算胜败表，或者用后面的SG函数来求。这里先留个钩子：能取的数量集合有限时，状态胜败表往往会呈现出周期，但周期长度需要自己暴力打表找，不能做梦直接套m+1。
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是0101，7是0111，12是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函数登场。它的正式定义是递归的：对于一个状态x，SG(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值是一个正整数，设为k，mex({...}) = 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%(m+1)是否为0。很多同学会在这里犯一个经典错误：把m+1写成了m。我吃过一次亏，那次题目的m是5，周期是6而不是5，因为一次最多取5个，两个人轮流取一轮的总消耗量可以达到6。建议自己拿小数字手推验证，比如n=6，每次最多取5个，先手取1个后手可以取5个刚好取完；取2个后手取4个；取3个后手取3个；取4个后手取2个；取5个后手取1个。后手都能把总消耗凑成6，所以n=6确实是必败态。
如果题目要求输出具体步骤，先手只需要第一步取n%(m+1)个，之后每步都按“m+1-对手上一步取的数量”来应对。不要用随机策略，也不要看着剩余数量贪心，补数策略是保证周期性取胜的唯一方法。
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值异或起来。
单堆状态的转移定义：对于状态x（x >= 2），一次操作后变成两个正整数对(a, b)，满足a + b = x，且a > 0，b > 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) = 0，SG(1) = 0，因为没有合法分裂。SG(2)：可分裂为(1,1)，SG(1) xor SG(1) = 0，mex{0} = 1。SG(3)：可分裂为(1,2)，SG(1) xor SG(2) = 0 xor 1 = 1，mex{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)给出1，SG(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集合去重排序，集合里有重复值不能用数组长度直接判空。最后检查边界状态，比如n=0、m=1、只有一堆石子这些极端情况，用打表验证终值。
如果是SG函数实现暴露出问题，建议把打印SG值输出到文件里，小范围打表观察规律。SG序列有周期的可以当即剪枝，没有周期的就要考虑算法复杂度是否可以接受。我遇到过好多次“打表发现周期但代码里没有剪枝，导致TLE”的情况，周期检测不是可选项，而是SG题目的标配优化。
6.5 做题顺序比刷题量更重要
最后分享一个我自己调整过多次的专题训练顺序。不要一上来就开SG专题狂刷题，那样很容易被各种变形打懵。先花一天时间把巴什博弈证明到会自己推导的程度，然后用十道左右的经典Nim变体题巩固，确保能独立写出“判定加构造方案”的代码。接着手推至少三组SG序列，每一组都对照程序验证，再把SG定理用于复合游戏题。这样走下来，你再看大多数博弈题的时候，脑子里会自动浮现“这是巴什”、“这是Nim”、“这是SG拆分”的分类标签。
当年我一位队友说过一句话，我一直记到现在：博弈题不是靠背结论，而是靠把结论放在脑子里的逻辑推演里。结论会忘，但推演套路一旦熟练，题目再怎么变都能找到入口。这篇文章写到这里已经覆盖了从巴什到SG的全部核心证明和例题路径，剩下的就是你自己动手去把每一条递推亲手走一遍。把一个游戏状态的SG表从头到尾推出来一次，比做十道复制模板的题都管用。
