博弈论SG函数详解：从集合-Nim游戏理解公平组合游戏通用解法

1. 项目概述从一道题看透博弈论的核心骨架看到“集合-Nim游戏”这个标题很多刚开始接触博弈论的同学可能会有点发怵觉得这又是那种理论深奥、代码难写的“劝退题”。但我想说这道题恰恰是打开博弈论SG函数这扇大门最完美的一把钥匙。它不像一些纯理论的证明题那样飘在空中而是给出了一个非常具体的、可操作的框架给你几堆石子再给你一个可取石子数的集合两人轮流取无法操作者输。题目要求你判断先手是否必胜。这听起来就是Nim游戏的变种对吧但它的价值在于它强迫你去理解并实现SG函数那个“模板化”的求解过程。所谓“模板题”意味着它的解法结构是固定的你只要吃透这一道以后遇到一大类公平组合游戏问题都能套用这个框架来解决。我在最初学习时就是通过反复琢磨这道题才真正把SG函数从书本上的定义变成了自己脑子里的算法直觉。今天我们就来彻底拆解它不仅写出AC代码更要弄明白每一个步骤背后的“为什么”让你下次遇到类似的博弈问题能像做四则运算一样条件反射地写出解法。2. 核心思路拆解为什么SG函数是博弈问题的“通用语言”在直接看代码之前我们必须先建立正确的认知模型。很多人学博弈论喜欢直接背结论比如“Nim游戏各堆石子数异或和为0则先手必败”但这道题显然不能直接套这个结论因为取石子的规则被一个集合S限制了。这时候SG函数的价值就体现出来了。2.1 从具体游戏到抽象状态集合-Nim游戏的核心约束是每次操作你只能从某一堆石子中取走一定数量而这个数量必须属于题目给定的一个集合S。比如S{2, 5}那你一次就只能取2颗或5颗不能取1颗、3颗或其他数量。SG函数Sprague-Grundy函数的作用就是为每一个独立的游戏状态在这里就是“某一堆还剩多少石子”这个状态赋予一个非负整数值我们称之为SG值。这个设计的精妙之处在于终态定义清晰对于一堆石子当石子数为0时你无法进行任何合法操作这个状态是必败态。我们定义终态的SG值为0。状态转移可计算对于一个非终态石子数x0你可以进行若干种合法操作即取走属于集合S的石子数。假设你取走s个石子后状态变为x-s。那么状态x的SG值就是所有可能的后继状态x-s的SG值所组成的集合中最小的、没有出现的非负整数。这个定义有点绕我举个例子。假设S{1, 3, 4}我们想计算石子数x5时的SG值。从5出发可以走到4取1、2取3、1取4这三个后继状态。我们需要知道SG(4), SG(2), SG(1)的值。假设我们已经算出SG(4)2, SG(2)0, SG(1)1。那么后继状态的SG值集合就是{2, 0, 1}。最小的、没有在这个集合中出现的非负整数是3因为0,1,2都有了下一个是3。所以SG(5) 3。这个计算过程是不是很像一个动态规划或者记忆化搜索没错SG函数的计算本质上就是一个带备忘录的递归搜索。2.2 多堆游戏的胜负判定异或运算的魔力当我们只有一堆石子时SG值大于0代表当前玩家面对这堆石子的人有必胜策略等于0代表必败。那么对于多堆石子多个独立的子游戏呢这就是Sprague-Grundy定理的核心内容整个游戏的SG值等于所有子游戏SG值的异或和。如果这个总的异或和为0那么当前局面是必败态先手必败否则是必胜态先手必胜。为什么是异或这背后有严谨的数学证明类似于Nim游戏的证明我们可以直观理解为异或运算完美地刻画了“对称”与“平衡”。当所有子游戏的SG值异或为0时任何操作都会破坏这种平衡将非0的局面留给对手而对手总能在非0的局面中找到一种操作将平衡异或为0的局面还给你。如此往复直到你面对所有子游戏终态SG值全为0异或自然为0而失败。所以解决集合-Nim游戏的算法框架就非常清晰了预处理对于每一堆可能的石子数上限由题目给出计算出它的SG值并存储起来。这是一个记忆化搜索的过程。求解读入每一堆当前的石子数查找其对应的SG值。判断将所有堆的SG值进行异或根据结果是否为0输出答案。注意SG函数的计算是这道题的核心也是性能关键。因为石子堆数可能很多但每堆的石子数范围是有限的通常题目会给出上限比如10000。我们需要避免对每一堆都重新从头计算SG值必须通过记忆化搜索进行复用。3. 代码实现与逐行解析理解了原理我们来看C实现。下面的代码是标准的SG函数模板几乎可以原封不动地用于解决所有类似的公平组合游戏问题。#include iostream #include cstring #include unordered_set using namespace std; const int N 110, M 10010; // N: 集合S的大小上限 M: 石子数上限 int s[N], sg[M]; // s[]: 存储可取石子数的集合 sg[]: 记忆化存储每个石子数对应的SG值 int k, n; // k: 集合S中元素个数 n: 石子堆数 // 记忆化搜索计算SG(x) int getSG(int x) { // 如果已经计算过直接返回 if (sg[x] ! -1) return sg[x]; // 用一个哈希表来记录所有后继状态的SG值 unordered_setint S; for (int i 0; i k; i) { int take s[i]; if (x take) { S.insert(getSG(x - take)); // 递归计算后继状态SG值 } } // 计算mex值最小的不属于集合S的非负整数 for (int i 0; ; i) { if (!S.count(i)) { sg[x] i; return i; } } } int main() { cin k; for (int i 0; i k; i) cin s[i]; // 初始化sg数组为-1表示未计算 memset(sg, -1, sizeof sg); cin n; int res 0; // 用于累加异或和 for (int i 0; i n; i) { int h; cin h; res ^ getSG(h); // 计算每堆石子的SG值并异或 } if (res) cout Yes endl; // 异或和非零先手必胜 else cout No endl; // 异或和为零先手必败 return 0; }3.1 关键数据结构选择数组s[N]存储可取石子数的集合。这里用数组而非vector是因为输入规模确定数组访问效率更高。数组sg[M]这是记忆化的核心。sg[x]表示石子数为x时的SG值。初始化为-1这是一个非常实用的技巧因为SG值本身是非负整数用-1可以明确表示“未计算”状态。unordered_setint S在getSG函数内部用于临时存储当前状态x的所有后继状态的SG值。选择unordered_set而不是set是因为我们只关心存在性查询count和插入不关心顺序哈希表在平均情况下有O(1)的查询复杂度比红黑树实现的setO(log n)更快。3.2getSG函数记忆化搜索的典范这个函数是灵魂所在我们拆开看边界与记忆化if (sg[x] ! -1) return sg[x];这是记忆化搜索的标准开头避免重复计算将指数级复杂度降为O(M * K)M是石子数上限K是集合S大小。枚举所有可能操作for (int i 0; i k; i)遍历集合S中的每一个可取石子数take。只有当前石子数x take时该操作才合法。递归计算后继状态S.insert(getSG(x - take));这是最精妙的一步。要计算x的SG值我需要知道所有x-take的SG值。于是递归调用自身因为有了记忆化每个状态最多只计算一次。计算mex值for (int i 0; ; i)这是一个从0开始的无限循环直到找到第一个不在集合S中的整数i。这个i就是状态x的SG值。找到后存入sg[x]并返回。实操心得mex的计算循环写成for (int i 0; ; i)看起来有点危险但实际上是安全的。因为对于任何有限集合S总存在一个最小的非负整数不在其中。循环一定会终止。你也可以写成for (int i 0; i S.size(); i)因为mex值最大不会超过集合S的大小最坏情况是SG值从0连续到S.size()-1那么mex就是S.size()。3.3 主函数逻辑异或定胜负主函数的逻辑非常直白读入集合S。初始化记忆化数组。读入每一堆的石子数h调用getSG(h)得到其SG值并与之前的结果res进行异或^操作。根据最终的res是否为0输出结果。这里有一个极其重要的细节res的初始值是0。因为0与任何数a异或结果还是a。所以这个初始化是正确的。4. 深度剖析时间复杂度与优化边界很多同学满足于AC但如果不分析复杂度遇到数据更强的题目可能会吃亏。我们来算一下假设石子数上限是MaxH集合S的大小是K。每个状态x(0 x MaxH) 最多被计算一次。计算每个状态x时需要遍历K种取法如果x足够大并对每种取法将其后继状态的SG值插入哈希集合。插入和查询的复杂度平均为O(1)。最后计算mex值最坏情况下需要遍历从0到K的整数如之前分析mex值不超过K。所以总的时间复杂度大约是O(MaxH * K)。空间复杂度是O(MaxH)用于存储sg数组加上递归调用栈的深度O(MaxH)最坏情况是一条链式递归。对于AcWing 893题的数据范围通常MaxH在10000以内K在100以内这个复杂度是绰绰有余的。但是如果题目数据范围增大比如MaxH10^5, K10^5O(10^10)的复杂度就无法承受了。进阶思考有没有优化空间对于特定的集合SSG值可能存在规律或周期。例如如果S{1}这就是一个简单的巴什博奕SG(x) x % 2。如果S{1, 2, ..., m}SG(x) x % (m1)。通过打表观察SG值的序列有时能找到数学规律从而用O(1)的公式代替搜索。但这需要敏锐的数学观察力和证明在竞赛中通常记忆化搜索就是通用且可靠的解法。5. 从模板到应用常见变种与应对策略掌握了这个模板你就能解决一大片问题。下面列举几种常见变种并说明如何调整我们的模板5.1 变种一操作规则变化原题是“从一堆中取走若干石子”。如果规则变成“将一堆石子分成两堆”或者“操作后石子数必须满足某个条件”怎么办解法核心在于getSG函数中“枚举后继状态”的部分。你需要根据新规则生成所有合法的后继状态比如分成的两堆石子数然后递归计算这些新状态的SG值。SG函数计算mex的逻辑完全不变。5.2 变种二多个不同的游戏组合题目可能不只有一种石子堆还可能混合了其他公平游戏比如翻硬币、移棋子等。解法Sprague-Grundy定理的强大之处在于它允许游戏是“不相关”的。你只需要为每一种类型的游戏状态可能是石子数、硬币状态、棋子位置独立计算其SG函数。最后将所有子游戏无论是哪种类型的SG值全部异或起来判断总和即可。我们的模板只需要为每种游戏分别实现一个getSG函数。5.3 变种三求必胜的第一步操作有时题目不仅问是否必胜还要求如果必胜输出一种可行的第一步操作。解法在计算出整个局面的SG值res异或和非零后我们知道存在至少一种操作能使对手面对必败态即操作后总SG值变为0。我们需要遍历所有子游戏每一堆和所有合法操作。假设我们对第i堆石子数为hSG值为sg_h进行操作取走take个使其变为h-takeSG值变为sg_new。那么操作后总SG值变为res ^ sg_h ^ sg_new因为从总异或和中去掉旧的sg_h加入新的sg_new。我们需要找到一组(i, take)使得这个结果等于0。这只需要在判断必胜后加一层循环枚举即可。6. 调试技巧与边界情况处理即使思路清晰代码也可能因为细节出错。分享几个我调试这类题目时的检查清单SG数组初始化memset(sg, -1, sizeof sg)这行千万别漏。同时要在主函数中、读入数据后、开始计算前进行初始化。递归边界在getSG函数中必须优先处理边界。通常我们会把sg[0]显式地设为0。可以在初始化时做也可以在getSG函数开头加if(x 0) return 0;。确保你的记忆化判断if(sg[x]!-1)在边界判断之后。集合S的顺序题目没有说集合S是有序的我们的算法也不依赖其顺序。但有时为了优化mex查找速度如果集合S是连续的整数范围我们可以用布尔数组代替哈希集合但通用模板用unordered_set就好。输入规模与数组大小这是最经典的错误。const int M必须开得比题目给出的最大石子数至少大1。如果题目说每堆石子数不超过10000那么M至少要10001。我习惯会多开一点比如const int M 10010;。异或运算的优先级res ^ getSG(h);这里没问题。但在更复杂的表达式中要注意异或(^)的优先级很低低于比较运算符。如果不确定就加括号。7. 思维延伸SG函数与动态规划的关系如果你熟悉动态规划会发现SG函数的记忆化搜索过程就是一种特殊的DP。sg[x]就是我们的“状态”其“状态转移”是sg[x] mex{ sg[x - s[i]] for all valid i }。但它和经典DP求最优解最大/最小值不同它求的是mex。这个mex操作保证了SG函数能够完美地建模“双方都采取最优策略”的公平博弈。你可以把SG值为0的状态理解为DP中的“必败点”SG值大于0的状态理解为“必胜点”。而这个mex机制确保了从必胜点总可以走到必败点从必败点只能走到必胜点。理解这一点能帮助你更好地将博弈论问题转化为状态机模型并用类似的搜索或DP方法来解决更复杂的、非标准的博弈问题。最后我再强调一次893. 集合-Nim游戏的价值就在于它提供了一个毫无花哨的、纯粹的SG函数应用场景。把这里的代码和理解吃透记住这个“计算单状态SG值 - 多状态SG值异或 - 判零定胜负”的三步流程你就掌握了解决一大类博弈问题的通用武器。下次再看到“公平组合游戏”、“轮流操作”、“无法操作者输”这些关键词你应该能会心一笑知道该从哪里入手了。编程竞赛中的博弈论很多时候考验的就是将实际问题准确映射到这个经典模型上的能力。