SG函数：让博弈“化整为零”

引言在算法竞赛中博弈论题目常常让人望而生畏两个绝顶聪明的人轮流操作问谁赢谁输。最简单的取石子游戏Nim 游戏有一个漂亮的结论——异或和为 0 则先手必败否则先手必胜。但题目稍微一变比如“可以把一堆石子分成两堆”这个结论就不够用了。SG 函数Sprague-Grundy Function正是为了统一解决这类公平组合游戏而生的。它将复杂的博弈局面映射为一个非负整数SG 值然后通过SG 定理将多个子游戏的组合转化为 Nim 和异或和。掌握 SG 函数你就掌握了解决大部分公平组合游戏的通法。如果说 Nim 游戏是一把“钥匙”那么 SG 函数就是“万能钥匙胚”——任何公平组合游戏只要算出每个局面的 SG 值就能用 Nim 和的思路判断胜负。前置知识在学习 SG 函数之前你需要掌握以下基础公平组合游戏ICG的定义两名玩家轮流行动。任何状态下两名玩家的合法操作集合完全相同。不能行动者输。游戏一定在有限步内结束。必胜态与必败态没有后继状态的状态是必败态P-position。存在至少一个后继状态为必败态的状态是必胜态W-position。所有后继状态都是必胜态的状态是必败态。mex 运算mex(S)表示不属于集合 S 的最小非负整数。例如mex({0, 2, 4}) 1。第一章SG函数的定义与计算1.1 SG 函数的定义对于公平组合游戏中的状态 xx其 SG 函数值定义为SG(x)mex({SG(y)∣y 是 x 的后继状态})SG(x)mex({SG(y)∣y 是 x 的后继状态})也就是说一个状态的 SG 值等于其所有后继状态的 SG 值集合中未出现的最小非负整数。理解 SG 函数的一个关键视角SG(x) k 意味着从状态 x 可以转移到 SG 值为 0, 1, ..., k-1 的所有状态。这使得 SG 值与 Nim 游戏中的一堆石子形成了完美的对应关系。1.2 计算 SG 函数的步骤第一步确定状态的表示明确每个博弈状态如何表示。例如 Nim 游戏中状态就是“各堆石子的数量”。第二步画出博弈图有向无环图从终止状态开始递推计算每个状态的 SG 值。第三步应用 mex 运算对于每个状态收集所有后继状态的 SG 值取 mex。第四步利用 SG 定理组合如果游戏由多个独立子游戏组成总 SG 值为各子游戏 SG 值的异或和。1.3 手算示例简单的取石子游戏游戏规则一堆石子每次可以取 1 颗或 3 颗取到最后一颗的人赢。计算 SG 值SG(0)0没有石子可取必败SG(1)mex({SG(0)})mex({0})1SG(2)mex({SG(1)})mex({1})0SG(3)mex({SG(2),SG(0)})mex({0,0})mex({0})1SG(4)mex({SG(3),SG(1)})mex({1,1})0规律SG(x)0SG(x)0 当且仅当 xx 是偶数。这个例子说明SG 值为 0 的状态对应必败态SG 值不为 0 的状态对应必胜态。第二章SG定理与Nim游戏2.1 SG 定理SG 定理Sprague-Grundy Theorem是公平组合游戏理论的基石一个组合游戏由若干子游戏组成的 SG 值等于各子游戏 SG 值的异或和Nim 和。换句话说如果游戏 GG 可以分解为若干互不影响的子游戏 G1,G2,...,GnG1​,G2​,...,Gn​那么SG(G)SG(G1)⊕SG(G2)⊕⋯⊕SG(Gn)胜负判定若 SG(G)0则先手必败。若 SG(G)≠0则先手必胜。这正是 Nim 游戏结论的推广Nim 游戏中每堆石子就是一个子游戏SG(一堆石子)石子数SG(一堆石子)石子数所以总 SG 值就是所有堆石子数的异或和。2.2 SG 定理的直观理解为什么 SG 值可以异或因为 SG 值k意味着该状态可以转移到 SG 值为 0, 1, ..., k-1 的任意状态。这和 Nim 游戏中一堆 k 颗石子的性质完全一样——你可以把它变成 0, 1, ..., k-1 颗。因此整个游戏等价于一个 Nim 游戏其中第 ii 堆石子的数量就是第 ii 个子游戏的 SG 值。第三章性质与复杂度性质说明SG 0 必败SG 值为 0 的状态是必败态SG ≠ 0 必胜SG 值不为 0 的状态是必胜态SG 定理总 SG 各子游戏 SG 的异或和计算方式从终止状态开始递推或 DFS 记忆化适用场景所有公平组合游戏复杂度O(状态数×转移数)O(状态数×转移数)第四章例题与详细解析例题1Nim游戏 —— 洛谷 P2197题目描述地上有 nn 堆石子每堆石子数量为 aiai​。两人轮流操作每次可以从任意一堆中取出任意数量的石子至少取 1 颗可以取完。不能操作者输。判断先手是否必胜。输入示例1 3 1 2 3输出示例Yes解题思路这是 Nim 游戏的模板题。每堆石子是一个独立的子游戏SG(一堆 x 颗石子)xSG(一堆 x 颗石子)x。根据 SG 定理总 SG 值为所有堆石子数的异或和。详细解析第一步认识 Nim 游戏的结论Nim 游戏有一个著名的定理先手必胜当且仅当所有堆石子数的异或和不为 0。证明思路简要若异或和为 0无论先手如何操作异或和都会变为非 0后手总能把异或和重新变为 0。若异或和非 0先手总能找到一堆石子从中取出若干颗使异或和变为 0。最终所有堆石子数为 0 时异或和为 0轮到谁谁输。第二步代码实现#include bits/stdc.h using namespace std; int main() { int T; cin T; while (T--) { int n; cin n; int xorsum 0; for (int i 0; i n; i) { int a; cin a; xorsum ^ a; } cout (xorsum ? Yes : No) \n; } return 0; }第三步复杂度分析时间复杂度 O(n)O(n)空间复杂度 O(1)O(1)。例题2高手过招 —— 洛谷 P2575题目描述有一个 n×20n×20 的棋盘每个格子有棋子1或没有棋子0。每次操作选择一个棋子将它向右移动到第一个空格处。如果某个棋子右边没有空格则不能移动该棋子。当所有棋子都不能移动时游戏结束不能操作者输。判断先手是否必胜。输入示例2 3 1 2 3 2 4 5输出示例YES解题思路这道题不能直接套用 Nim 游戏的结论需要先将其转化为阶梯 NimStaircase Nim问题。详细解析第一步观察游戏性质每一行是独立的子游戏总 SG 值为各行 SG 值的异或和。对于一行 20 个格子从右往左看连续的棋子构成“一段”。将相邻的有棋子的格子合并为一个“阶梯”阶梯上的棋子数等于该段连续棋子的长度。第二步转化为阶梯 Nim阶梯 Nim 的结论是只看奇数层阶梯上的石子数异或和不为 0 则先手必胜。为什么因为移动一个棋子到右边的空格等价于把石子从当前阶梯移到更低的阶梯。这和阶梯 Nim 的规则完全一致。第三步代码实现#include bits/stdc.h using namespace std; int main() { int T; cin T; while (T--) { int n; cin n; int ans 0; for (int i 0; i n; i) { int x; cin x; vectorint pos(20, 0); for (int j 0; j x; j) { int p; cin p; pos[p-1] 1; // 标记有棋子的位置 } // 从右往左处理转化为阶梯 Nim int cnt 0, step 0; for (int j 19; j 0; j--) { if (pos[j] 0) { step; // 空格增加进入下一级阶梯 } else { if (step % 2 1) cnt; // 奇数层阶梯上的棋子数 } } ans ^ cnt; // 每行的 SG 值异或起来[reference:76] } cout (ans ? YES : NO) \n; } return 0; }第四步复杂度分析每行 20 个格子nn 行时间复杂度 O(20n)O(20n)空间复杂度 O(1)O(1)。第五章常见变体与应用场景变体核心思路典型例题Nim 游戏所有堆异或和P2197阶梯 Nim只统计奇数层阶梯P2575Anti-Nim取到最后一颗石子的人输需特殊判断拆分 Nim可将一堆分成两堆SG 打表找规律HDU 3032树上博弈转化为阶梯 Nim 或 SG 函数各类树上删边游戏SG 打表找规律小范围计算 SG观察周期规律HDU 5795总结SG 函数是解决公平组合游戏问题的统一框架。它的核心流程是确定状态明确每个局面如何表示。计算 SG 值从终止状态开始利用mex运算递推。应用 SG 定理将总游戏的 SG 值分解为各子游戏 SG 值的异或和。判断胜负SG 值为 0 则必败否则必胜。从 P2197Nim 游戏模板的“直接异或”到 P2575高手过招的“转化为阶梯 Nim”SG 函数的价值在于化繁为简——无论游戏规则多么复杂只要能分解为若干独立的子游戏就能用 SG 定理统一求解