第一次看到 sg-ss 这个缩写我也愣了一下。它不像 RF、GBDT 那样一眼能猜到是哪几个单词的缩写在算法题和博弈场景里大家默认把它拆成两个部分sg 代表 Sprague-Grundy 函数ss 代表 state space 状态空间搜索。合在一起就是用状态空间 SG 值去分析一类有限、无环、双方轮流操作的博弈问题。这套东西能解决什么问题最简单一句话给定一个局面快速判断先手是必胜还是必败再进一步给定多个相互独立的子游戏直接算出整体胜负。适合刚学完 Nim 想继续深入的新手也适合写棋类 AI、决策系统的人参考。1. 从 SG 定理到 sg-ss为什么要做“算法分析”而不是直接搜索1.1 一个游戏怎么变成状态空间先说最朴素的理解。凡是“双方轮流走、结果只有输赢、信息完全公开”的博弈都可以画成一张有向图每个节点是一个局面每条边是一次合法操作。比如一堆石子每次只能拿 1 到 3 个那么状态 x 会连到 x-1、x-2、x-3。谁先拿不了谁输这就是一张典型的 DAG。为什么一定要先想到状态空间因为胜负判断本质上是在图上做“可达性分析”。当前局面是必胜当且仅当存在一个后继局面是必败当前局面是必败当且仅当所有后继局面都是必胜。这句话用递归写出来就是几行代码但如果不做任何缓存复杂度会指数爆炸。sg-ss 的核心思路是先把这个状态图定义清楚再用 Sprague-Grundy 函数把每个节点的胜负信息压缩成一个整数最后用整数运算代替整棵搜索树。很多新手会跳过我这一步直接去背“把所有堆的石子数异或起来非零就赢”。背熟了 Nim 没问题但换一个游戏规则就傻眼。原因就在于没理解状态空间才是底层模型异或只是 SG 值的一种合并方式。先有图后有 SG 值最后才有异或。1.2 SG 函数是“地图上的路标”Sprague-Grundy 函数定义一套规则对于终止状态SG 值为 0对于非终止状态SG 值是所有后继状态 SG 值集合的 mexminimum excludant最小未出现非负整数。举个小例子。假设一堆石子每次可以拿 1 个或 3 个不能拿则输SG(0) 0因为已经终止。SG(1) mex{SG(0)} mex{0} 1。SG(2) mex{SG(1)} mex{1} 0。SG(3) mex{SG(2), SG(0)} mex{0, 0} 1。SG(4) mex{SG(3), SG(1)} mex{1, 1} 0。SG 值等于 0代表这个状态是必败SG 值不等于 0代表必胜。为什么不能只用 0/1 两个布尔值而要用一个可能很大的整数因为后面要支持多个独立游戏合并。只靠“必胜/必败”无法推出两个游戏拼在一起的结果而 SG 值通过异或运算可以精确合并。把 SG 值看成地图上的路标就很直观每个节点不是简单标“胜/负”而是标一个“数字密码”。单独看一个游戏密码是 0 就输多个游戏叠加时把所有密码异或结果非零就是先手胜。1.3 把多个子游戏合并异或规则的本质sg-ss 里最容易理解错的一步是异或。它并不是从天上掉下来的奇技淫巧而是有一条定理如果整个局面由若干个互不影响的子游戏组成那么整体 SG 值等于每个子游戏 SG 值的异或。为什么是异或不是加法也不是取最大值因为异或运算正好对应二进制下的“对称差”能精确描述两个人轮流选一个子游戏操作时局面整体从“可操作集合”角度发生了什么样的变化。我见过很多人死记结论结果遇到“子游戏之间有公共资源”的题目照样直接异或最后 WA 到怀疑人生。用 sg-ss 分析多子游戏时必须做两件事先证明子游戏之间真正独立再计算每个独立子游戏的 SG 值。判断标准是某一手操作是否只会改变一个子游戏而不会影响其他子游戏的状态参数。如果会串场就不能异或。1.4 sg-ss 和直接暴力的本质区别直接暴力搜索会让同一个局面出现在大量不同路径里。比如八皇后式的棋盘博弈同一个盘面可以通过完全不同的操作顺序到达盲目递归会反复扫同一棵子树。sg-ss 的做法是“记忆化 状态压缩”把状态空间变成一张缓存表算过一个状态就把它对应的 SG 值存下来后面遇到直接查表。这种做法的优势在于复杂度从“路径数量”降到“状态数量 × 平均出度”。在很多经典组合游戏中状态数量远小于路径数量所以效果非常明显。换句话说状态空间是去重之后的节点集合搜索树是带重复的展开路径。sg-ss 分析的就是前者这是它高效的关键。2. 核心细节解析状态设计与 SG 计算的实操要点2.1 状态设计的三要素第一次写 sg-ss 的人最容易在“状态定义”上翻车。状态不能只是“我心里知道现在棋盘长什么样”必须显式地变成可比较、可哈希、可缓存的数据结构。我的经验是看三要素当前局面的完整信息、哪些信息对后续决策有影响、哪些信息可以压缩。比如拿石子游戏只需要记录每堆数量如果是棋盘上游走就需要记录当前位置如果是区间拆分游戏就需要记录区间左右端点。漏掉任何影响今后移动的信息SG 值一定算错。贪心压缩状态时要谨慎。有些题目里“棋子颜色”看起来不影响规则实际上会不会影响同一个格子的占用冲突这类隐性依赖最坑。我一般先写一个不压缩的版本用小数据验证正确再做状态压缩优化。2.2 转移关系别只列“看起来合法”的移动SG 计算要求你枚举当前状态的所有合法后继状态。这里的“合法”必须和题目规则一致边界条件、不可等分、不能重复取同一个物品、不能把局面拆成空游戏等细节都要写清楚。转移关系写错最直接的表现是 SG 序列和标准结果对不上。比如很多拆分游戏不允许拆出空堆也不允许拆出两个等大的堆。循环条件写成i x - i就会把[i, x-i]相等的情况算进去看似只多了一个状态实际整条 SG 序列都会偏移。后面我会拿 Grundys Game 完整演示这个坑。还有一个常见问题是状态图里有环。如果某一步操作能让你回到之前的状态比如“移动棋子然后可以选择再移回去”那普通 SG 的 DAG 前提就不成立了。sg-ss 主要用于无环状态图遇到有环博弈需要换用双端队列、强连通分量或者更高级的“冷热博弈”工具而不是硬套 mex。2.3 mex 计算的正确姿势计算 SG 值的时候最忌讳每次新建一个大数组然后 memset 清空。状态一多memset 的时间会悄悄变成性能黑洞。我在 C 里最常用“版本号数组”int seen[MAXN], ver 0; int get_mex(vectorint children) { ver; for (int v : children) seen[v] ver; int g 0; while (seen[g] ver) g; return g; }为什么这样更快因为不用把整个数组清空只需要给这次计算一个独特版本号判断时检查seen[v] ver即可。每个用过的位置只写一次版本号递增O(1) 平均额外开销。另一个细节children里如果出现重复 SG 值不需要去重mex 天然对去重不敏感。但如果你使用unordered_setint去重要注意哈希表在状态量大的时候内存占用很高C 竞赛环境里可能比版本号数组慢很多。Python 里用set是没办法的办法但也够用。2.4 记忆化与状态压缩技巧状态压缩的目标是让每个状态占用尽可能少的空间同时能快速比较相等。常见的压缩方式位掩码适合棋盘、选集合类状态。一个 int 存 32 个格子两个 int 可以存 64 格。进制编码适合多维状态。比如状态(a, b, c)每个维度范围已知可以编码成a * B * C b * C c变成一个连续整数直接用数组当 memo。字符串哈希适合规则比较怪的状态但要注意哈希冲突。实际上如果状态本身是字符串且总长度可控直接用unordered_mapstring, int简单可靠。选哪种取决于状态空间有没有“自然的整数映射”。有映射就用数组没有就用哈希表。数组速度最快但内存可能浪费哈希表灵活但常数大。做算法分析时我通常先算一下理论状态数量如果小于10^6直接数组如果到10^7以上再考虑压缩成位掩码或用unordered_map稀疏存储。3. 实操过程与核心实现以 Grundys Game 为例完整跑一遍3.1 题目规则和状态定义Grundys Game 是一个非常经典的 SG 练习题。规则如下有一堆大小为 n 的石子每次操作必须把一堆石子拆成两个大小不同的非空堆不能继续拆的人输。问初始 n 是否是先手必败。初看像是只有一个游戏但拆分之后会变成两个独立子游戏所以要使用异或合并。状态只需用一个整数x表示当前堆大小。没有可拆分的状态是x 1和x 2因为 1 不能拆2 只能拆成 1 和 1违反“大小不同”的条件。计算 SG 值的方法枚举i从 1 到x/2令j x - i只保留i j的分法保证不重复每个拆分得到两个独立子游戏组合值的异或为sg(i) ^ sg(j)sg(x)等于所有这些异或值的 mex。3.2 手算前几个状态建立直觉用手算一遍前几个值非常有价值。它比直接看代码更能建立“SG 到底在算什么”的直觉。x合法拆分子游戏 SG 异或集合sg(x)1无空集02无空集0312{0 ^ 0 0}mex{0}1413{0 ^ 1 1}mex{1}0514, 23{0^00, 0^11}mex{0,1}2615, 24{0^22, 0^00}mex{0,2}1716, 25, 34{0^11, 0^22, 1^01}mex{1,2}0817, 26, 35{0^00, 0^11, 1^23}mex{0,1,3}2注意第 8 行就会出现一个之前没出现过的值 3所以sg(8) 2。如果代码里seen数组开得太小或者 mex 循环上限不够这里就错了。从这个表也能看出SG 值并不一定随 n 递增它可能出现跳变和回落这就是博弈里“状态价值”的微妙之处。3.3 Python 与 C 实现对照Python 版本用递归记忆化最贴合思维过程import sys from functools import lru_cache sys.setrecursionlimit(100000) lru_cache(None) def sg(x): if x 2: return 0 seen set() for i in range(1, x // 2 1): j x - i if i j: continue seen.add(sg(i) ^ sg(j)) g 0 while g in seen: g 1 return g def first_player_win(piles): xor_sum 0 for p in piles: xor_sum ^ sg(p) return xor_sum ! 0C 版本我建议直接用递推避免递归栈和哈希表常数#include bits/stdc.h using namespace std; int main() { const int N 1000; vectorint sg(N 1, 0); vectorint seen(N 5, 0); int ver 0; for (int x 3; x N; x) { ver; for (int i 1; i * 2 x; i) { int j x - i; int val sg[i] ^ sg[j]; seen[val] ver; } int g 0; while (seen[g] ver) g; sg[x] g; } int t; cin t; while (t--) { int n; cin n; cout (sg[n] ? First : Second) \n; } return 0; }C 的循环条件i * 2 x是我特别想强调的它天然保证i j把“等分非法”写进了边界而不是靠循环里的 if 判断。代码少了分支语义也更清晰。3.4 复杂度与参数计算对于 n 最大到 N 的单个堆递推时每个状态x最多遍历x/2种拆分所以总复杂度是O(1 2 ... N/2) O(N^2)。如果 N 1000计算量大约是 25 万次异或加 mex毫秒级完成。如果 N 10万N^2 就是 50 亿次绝对不可行。这时候不能继续暴力递推需要观察 SG 序列的周期性或模式或者用更高效的数学性质。实战里我一般先跑一个小范围把 SG 序列打出来看有没有周期。很多博弈题的 SG 值会进入周期找到循环节后可以直接 O(N) 甚至 O(1) 求解。Grundys Game 本身的 SG 序列并不简单但它依然是小数据验证 sg-ss 流程的好例子。多条堆的复杂度更好算每个堆单独查 SG 值再全部异或复杂度近似 O(总石子数 堆数)。4. 常见问题与排查技巧实录4.1 算出来的 SG 值全是 0看到这种结果第一反应是检查合法移动集合。常见原因有两个一是把终止状态设错了比如 0 号一堆石子其实还能移动到空堆导致递归提前终止二是边界条件写反了比如拆分了空堆或者允许了等分导致每个状态都只能走到 SG0 的子状态。排查方法很简单手动模拟 n3 和 n4。如果连这两个小值都不符合手算结果那不是 SG 定理的问题是转移关系写错了。4.2 超时和状态爆炸我见过最离谱的一次超时是在 C 里用了unordered_mapint, int保存 SG 值状态数只有 5 万却跑了十几秒。问题出在自定义哈希函数太差或者频繁触发 rehash。解决方案优先看能不能把状态映射成连续整数。能就用vectorint不能再考虑unordered_map并提前reserve。另一个优化是 mex 计算别用set用版本号数组。4.3 多堆异或用错场景异或的前提是子游戏独立。如果一个操作会同时影响两个子游戏或者两个子游戏共享同一个资源池那么直接异或就是错的。比如两堆石子中间隔着一个障碍物移动某一堆的棋子可能导致另一堆的可移动范围变化这是典型的“非独立”。必须先通过状态设计把耦合拆开拆不开就不能用 sg-ss 的核心异或公式。很多博弈题难在“拆游戏”不在 SG 计算本身。4.4 递归爆栈与缓存失效Python 递归深度默认只有 1000计算大 n 的 SG 很容易炸。用sys.setrecursionlimit是个办法但递归层数和系统栈上限还是可能不够。建议在 Python 里也改成从小到大递推或者用显式栈。缓存失效的坑则常出现在多组测试用例之间如果lru_cache不清空上一组数据的状态可能残留。如果状态定义依赖于组内参数这个残留值就会污染下一组计算。批量处理时我习惯在每组数据里新建一个缓存或者把所有参数写进状态键里。4.5 问题排查汇总现象可能原因处理办法SG 序列和样例不一致转移边界、终止态错误手算前 5~8 个状态逐项核对运行超时状态无法映射为数组、mex 用 set换版本号数组、改用连续状态编码多堆答案错误子游戏不独立重新设计状态拆分耦合递归爆栈Python 默认递归深度小设为两倍状态数或改递推缓存污染lru_cache 跨用例保留每次用例重置缓存还有一个调试技巧写一个完全不去重的暴力 DFS和 sg-ss 版本对拍随机生成 1000 个小状态比较胜负结果。暴力版本常数大但逻辑简单适合当裁判。只要小规模对拍通过再跑大数据心里就有底。5. 进一步扩展sg-ss 在真实项目里能走多远5.1 算法竞赛中的固定套路sg-ss 是组合博弈专题里的核心思想。从 ICPC、Codeforces 到各种线上笔试凡是出现“有限状态、双方轮流、不能操作者输”的题目你都可以先尝试建模成状态图再用 SG 值分析。特别是拆分类、移动类、棋盘走位类游戏sg-ss 几乎是标准解法。它和普通 DP 的关系也很近SG 计算本质是一种带博弈语义的区间 DP/状态 DP。只是普通 DP 求最大最小值SG 求的是 mex。理解了这一层遇到“看起来像博弈的 DP”就不会慌。5.2 游戏 AI 与自动规划中的组合潜力在真实游戏 AI 里完美信息零和博弈常常使用 Alpha-Beta、MCTS 这类方法。sg-ss 和它们并不冲突反而可以当预处理工具。如果游戏能拆成多个独立子局面的和先用 SG 值算出每个子局面的归属再用搜索算法处理局部冲突整体搜索深度可以明显降低。我做棋类 Demo 时有过一次实践一个简单的“跳棋 取子”双规则小游戏拆成两个独立子游戏后AI 不再需要搜索整棵状态树只要用 SG 异或判断全局偏好再配合局部 Alpha-Beta 找具体落子。这套混合方案当时把单步决策时间从 900ms 压到了 120ms 左右。5.3 和 MCTS 搭配时的现实提醒MCTS 擅长处理大搜索空间和不确定分支但它给出的胜率评估是统计估计不是精确值。sg-ss 擅长给出精确胜负但要求状态空间有限且子游戏独立。混合使用时要格外小心如果子游戏之间的独立性被破坏直接把 SG 值塞进 MCTS 的评估函数会引入偏差。我的经验是SG 值可以作为“先验”来初始化 MCTS 节点的胜负信念但不能覆盖 MCTS 对实际局面的统计。两者属于不同粒度的信息SG 是全局结构结论MCTS 是局部探索结果。5.4 什么情况下该放弃 sg-ss状态空间无穷大或巨大、状态转移有环、玩家利益不是严格零和、存在随机性——这些场景都不是 sg-ss 的主场。比如带骰子的棋类、不完全信息扑克就不能只靠 SG 值做精确判断。此时更适合用期望收益、贝叶斯推断或强化学习。我自己的体会是sg-ss 的价值在于逼你把“规则”翻译成“状态图”。哪怕最后因为状态爆炸用不了完整解法这个建模过程也会让你对问题结构有更清楚的认识。做算法分析时先把状态空间想明白永远比盲目套用搜索算法更重要。