尼姆博弈高阶变形与SG定理实战：从异或判定到反尼姆、Moore‘s Nim-k

1. 从"取石子游戏"说起：尼姆博弈到底在解决什么问题

很多人第一次接触博弈论，都是从一堆石子开始的。两堆石子，两个人轮流取，每次可以从任意一堆里取任意多颗，取到最后一颗的人赢——这个看似简单的小游戏，背后藏着一整套算法竞赛里高频出现的数学模型。尼姆博弈（Nim Game）就是这类"取石子游戏"的经典代表，也是组合博弈论里最基础、最重要的一块基石。

我在带新人刷题的时候发现一个现象：大部分人能背出"异或和为0则先手必败"这个结论，但一旦题目变形——比如限制每次最多取k颗、或者石子堆数量动态变化、或者要求输出具体的第一步策略——就立刻卡壳。根本原因在于，他们只记住了公式，没有理解尼姆博弈的状态转移逻辑和必胜态/必败态的判定本质。

这篇文章面向的是已经了解基础博弈论（知道什么是P-position和N-position）、但在尼姆博弈的高阶变形题上反复翻车的读者。我会从最朴素的暴力搜索讲起，一步步推导到Sprague-Grundy定理，再延伸到反尼姆博弈、Moore's Nim-k、阶梯尼姆等高频变形，最后给出可直接套用的代码模板和我在实际比赛中踩过的坑。不管你是准备算法竞赛，还是单纯想搞懂这类问题的底层逻辑，这篇内容都能让你少走很多弯路。

需要提前说明的是，尼姆博弈的"高阶篇"并不是指某个单一的算法，而是一类问题的统称。它们的共同特征是：游戏可以分解为若干个独立的子游戏，每个子游戏的状态可以用一个非负整数（SG值）表示，整个游戏的胜负由所有子游戏SG值的异或和决定。理解了这条主线，后面所有的变形都只是在这条主线上做加减法。

2. 尼姆博弈的数学根基：为什么异或和能判定胜负

2.1 从暴力枚举到规律发现

先回到最原始的尼姆博弈定义：有n堆石子，第i堆有a_i颗。两人轮流操作，每次选择一堆，从中取走至少一颗、至多整堆的石子。取走最后一颗石子的人获胜（正常规则，Normal Play）。

对于小规模的情况，我们可以用递归暴力搜索所有状态来判断胜负。假设状态用石子堆的元组表示，比如(3, 4, 5)，那么：

from functools import lru_cache @lru_cache(maxsize=None) def is_winning(state): # state是排序后的元组，表示各堆石子数 for i in range(len(state)): for take in range(1, state[i] + 1): new_state = list(state) new_state[i] -= take new_state = tuple(sorted(s for s in new_state if s > 0)) if not is_winning(new_state): return True return False

跑一遍小数据就会发现规律：当且仅当所有堆石子数的异或和（XOR）为0时，当前局面是必败态。比如(1,1)异或为0，先手必败；(1,2,3)异或为0，先手必败；(3,4,5)异或为2，先手必胜。

这个结论不是巧合，它背后有严格的数学证明，而这个证明过程恰恰是理解所有变形题的钥匙。

2.2 必胜态与必败态的两个核心性质

尼姆博弈的胜负判定依赖于两个基本性质，我习惯把它们叫做"终态锚定"和"一步可达"：

性质一（终态锚定）：全空状态(0,0,...,0)是必败态。此时异或和为0，没有石子可取，轮到谁谁输。

性质二（一步可达）：对于任意异或和非0的局面，一定存在一种取法，使得操作后的局面异或和为0；对于任意异或和为0的局面，无论怎么取，操作后的局面异或和一定非0。

性质二是整个证明的核心。我来展开说一下为什么它成立。

设当前局面异或和为S = a_1 ⊕ a_2 ⊕ ... ⊕ a_n。如果S ≠ 0，设S的最高位（最左边的1）在第k位。那么必然存在至少一堆石子a_i，其第k位也是1（否则S的第k位不可能是1）。我们选择这一堆，令a_i' = a_i ⊕ S。由于a_i的第k位是1，S的第k位也是1，异或后第k位变成0，所以a_i' < a_i，这是一个合法的取法（从a_i中取走a_i - a_i'颗）。操作后新的异或和 = S ⊕ a_i ⊕ a_i' = S ⊕ a_i ⊕ (a_i ⊕ S) = 0。

如果S = 0，假设存在一种取法使新异或和仍为0。设从a_i取到a_i'，则新异或和 = a_1 ⊕ ... ⊕ a_i' ⊕ ... ⊕ a_n = 0。而原异或和 = a_1 ⊕ ... ⊕ a_i ⊕ ... ⊕ a_n = 0。两式异或得a_i ⊕ a_i' = 0，即a_i = a_i'，但这与"至少取走一颗"矛盾。所以从异或和为0的局面出发，必然转移到异或和非0的局面。

这两条性质合起来，就构成了完整的归纳证明：异或和非0的局面总能转移到异或和为0的局面，而异或和为0的局面只能转移到异或和非0的局面，终态是异或和为0的必败态。因此异或和非0是先手必胜态，异或和为0是先手必败态。

2.3 一个容易混淆的点：异或和为0不等于"两两相等"

新手最常见的误解是把"异或和为0"等同于"所有堆石子数两两配对相等"。确实，(1,1)、(2,2,3,3)这类局面异或和为0，但反过来不成立。比如(1,2,3)异或和为0，但三堆互不相等。再比如(1,1,1,1)异或和为0，(1,1,2,2)也是。

这个误解会导致在变形题中做出错误的策略判断。记住：异或和为0是一个代数条件，不是结构条件。判断的时候老老实实算异或，不要试图用"配对"的直觉去猜。

3. Sprague-Grundy定理：把一切公平组合游戏变成尼姆博弈

3.1 为什么需要SG定理

原始尼姆博弈的规则很具体：从一堆里取任意多颗。但实际题目里，游戏规则千变万化——有的限制每次只能取1到k颗，有的规定取完后堆会分裂成两堆，有的甚至不是取石子而是移动棋子。如果每遇到一种新规则就重新推导一遍胜负条件，效率太低。

Sprague-Grundy定理的价值就在于：它证明了任何有限状态的、无平局的、双方操作集合相同的公平组合游戏（Impartial Game），都可以等价为一个尼姆博弈。每个游戏状态对应一个非负整数SG值，整个游戏的SG值是各子游戏SG值的异或和，SG值为0则必败，非0则必胜。

这就把"分析具体游戏规则"的问题，转化成了"计算SG值"的问题。而SG值的计算有统一的递推公式，不需要针对每种游戏单独证明。

3.2 SG值的定义与计算

对于一个游戏状态x，它的SG值定义为：

SG(x) = mex{ SG(y) | y是x经过一次合法操作能到达的状态 }

其中mex（minimum excludant）是一个集合中最小非负整数的意思。比如mex{0,1,3} = 2，mex{1,2} = 0，mex{} = 0。

这个定义看起来很抽象，但用起来很直接。以"每次最多取k颗"的尼姆博弈为例，单堆游戏的SG值计算如下：

def compute_sg(max_take, max_stones): sg = [0] * (max_stones + 1) for i in range(1, max_stones + 1): reachable = set() for take in range(1, min(i, max_take) + 1): reachable.add(sg[i - take]) # 计算mex g = 0 while g in reachable: g += 1 sg[i] = g return sg

跑一下max_take=3的情况，SG序列是0,1,2,3,0,1,2,3,...，也就是SG(i) = i mod 4。这意味着"每次最多取3颗"的尼姆博弈，等价于每堆石子数对4取模后的普通尼姆博弈。

3.3 SG定理的适用边界

SG定理虽然强大，但有明确的适用条件，我在实际做题时总结了几条判断标准：

前三条不满足时，SG定理直接失效，需要另想办法。第四条不满足时，SG定理的结论需要修正，这就是后面要讲的反尼姆博弈。

3.4 多堆游戏的SG值合成

当游戏由多个独立子游戏组成时，整个游戏的SG值是各子游戏SG值的异或和。这里的"独立"指的是：一个子游戏中的操作不影响其他子游戏的状态。

以"每次最多取k颗"的多堆尼姆为例，每堆是独立的子游戏，第i堆的SG值是a_i mod (k+1)，整个游戏的SG值是所有(a_i mod (k+1))的异或和。如果这个异或和非0，先手必胜。

我在实际编码时习惯把SG值的计算和异或合成分成两步：先写一个函数计算单个子游戏的SG值（通常用打表或递推），再在主逻辑里对所有子游戏的SG值做异或。这样代码结构清晰，也方便调试。

4. 尼姆博弈的高频变形与应对策略

4.1 反尼姆博弈：取到最后一颗的人输

反尼姆博弈（Misère Nim）的规则是：取走最后一颗石子的人输。这个规则改动看似微小，但胜负判定条件完全不同。

反尼姆博弈的判定分两种情况：

• 如果所有堆的石子数都等于1，则胜负取决于堆数的奇偶性：奇数堆先手必败，偶数堆先手必胜。
• 如果至少有一堆石子数大于1，则判定条件与正常尼姆博弈相同：异或和非0先手必胜，异或和为0先手必败。

为什么会有这个分叉？直觉上的解释是：当所有堆都是1时，游戏变成了"轮流取一颗"，没有策略空间，纯粹看奇偶。而当存在大于1的堆时，先手可以通过控制局面，把游戏引导到对自己有利的奇偶状态。

我在第一次遇到反尼姆时，直接套用了正常尼姆的异或判定，结果在(1,1,1)这种局面上翻了车——异或和为1（非0），按正常尼姆判断是先手必胜，但实际上先手取一颗后剩(1,1)，对手取一颗后剩(1)，先手被迫取最后一颗而输。所以反尼姆一定要单独处理全1的情况。

def misere_nim(piles): if all(p == 1 for p in piles): return len(piles) % 2 == 0 # 偶数堆先手胜 xor_sum = 0 for p in piles: xor_sum ^= p return xor_sum != 0

4.2 Moore's Nim-k：每次最多操作k堆

Moore's Nim-k是尼姆博弈的另一个重要推广：每次可以选择至多k堆，从每堆中取走任意多颗（至少一颗）。当k=1时，退化为普通尼姆博弈。

这个变形的判定条件不再是简单的异或和，而是按二进制位统计：对于每一个二进制位，统计所有堆在该位上为1的个数，将这些个数对(k+1)取模。如果所有位的模值都为0，则先手必败；否则先手必胜。

我举个具体例子。假设k=2，三堆石子分别为(1, 2, 3)：

• 第0位（最低位）：1的个数是2（来自1和3），2 mod 3 = 2
• 第1位：1的个数是2（来自2和3），2 mod 3 = 2

模值不全为0，所以先手必胜。

再比如(1, 1, 1)，k=2：

• 第0位：1的个数是3，3 mod 3 = 0

所有位模值都为0，先手必败。验证一下：先手最多取2堆，无论怎么取，后手都能取完剩下的，先手输。

这个判定的实现需要逐位统计，代码比普通尼姆复杂一些：

def moores_nim_k(piles, k): max_bit = max(piles).bit_length() for bit in range(max_bit): count = sum((p >> bit) & 1 for p in piles) if count % (k + 1) != 0: return True # 先手必胜 return False # 先手必败

4.3 阶梯尼姆：石子堆在台阶上

阶梯尼姆（Staircase Nim）的游戏设置是：石子分布在编号为1到n的台阶上，每次可以从第i级台阶取任意多颗石子移到第i-1级（i>1），或者从第1级台阶取走石子（移出游戏）。取走最后一颗石子的人赢。

这个游戏的结论很漂亮：只需要考虑奇数级台阶上的石子，把它们当作普通尼姆博弈。偶数级台阶上的石子对胜负没有影响。

原因在于：如果对手移动偶数级台阶上的石子到奇数级，你可以把同样多的石子从那一级奇数台阶移到下一级偶数台阶，相当于"镜像"操作，保持奇数级台阶的异或和不变。所以偶数级台阶只是"缓冲区"，不影响核心博弈。

这个结论我第一次看到时觉得很反直觉，但用SG定理推导一遍就清楚了：偶数级台阶上的石子，其SG值经过两次移动后会被抵消，最终只有奇数级台阶的SG值对总异或和有贡献。

4.4 尼姆博弈与动态规划的结合

有些题目会在尼姆博弈的基础上加入"取石子有代价"或"取石子数量有限制且限制随状态变化"的条件，这时候单纯的异或判定就不够用了，需要结合动态规划。

比如这样一道变形题：有n堆石子，每次可以从第i堆取走恰好c_i颗（c_i是给定的），取到最后一颗的人赢。这时候每堆的SG值需要用DP单独计算，因为取法不是"任意多颗"而是固定数量。

def compute_sg_with_fixed_takes(pile_size, takes): sg = [0] * (pile_size + 1) for i in range(1, pile_size + 1): reachable = set() for t in takes: if t <= i: reachable.add(sg[i - t]) g = 0 while g in reachable: g += 1 sg[i] = g return sg

这类题目的关键是：先确认游戏是否满足SG定理的适用条件，再用DP计算各子游戏的SG值，最后异或合成。不要一看到"尼姆"两个字就条件反射地写异或和。

5. 实战中的代码模板与调试技巧

5.1 通用尼姆博弈判定模板

把前面讲的内容整合成一个通用的判定函数，覆盖正常尼姆、反尼姆、Moore's Nim-k三种常见情况：

def solve_nim(piles, mode='normal', k=1): """ piles: 各堆石子数列表 mode: 'normal' 正常尼姆, 'misere' 反尼姆, 'moore' Moore's Nim-k k: Moore's Nim-k中的k值 """ if mode == 'normal': xor_sum = 0 for p in piles: xor_sum ^= p return xor_sum != 0 elif mode == 'misere': if all(p == 1 for p in piles): return len(piles) % 2 == 0 xor_sum = 0 for p in piles: xor_sum ^= p return xor_sum != 0 elif mode == 'moore': max_bit = max(piles).bit_length() if piles else 0 for bit in range(max_bit): count = sum((p >> bit) & 1 for p in piles) if count % (k + 1) != 0: return True return False

5.2 输出第一步策略的写法

很多题目不仅要求判断胜负，还要求输出先手的第一步具体操作。对于正常尼姆，策略是：找到异或和S的最高位，选择在该位上为1的任意一堆a_i，将其变为a_i ⊕ S。

def first_move_normal(piles): xor_sum = 0 for p in piles: xor_sum ^= p if xor_sum == 0: return None # 必败态，无必胜第一步 # 找到最高位 highest_bit = xor_sum.bit_length() - 1 for i, p in enumerate(piles): if (p >> highest_bit) & 1: new_p = p ^ xor_sum return (i, p - new_p) # 从第i堆取走p - new_p颗 return None

这里有个细节容易出错：选择的那一堆必须满足"第highest_bit位为1"，而不是随便找一堆。如果选错了堆，new_p可能大于p，变成非法操作。我在早期写这道题时就是因为没检查这一位，导致输出负数取石数而WA。

5.3 调试尼姆博弈题的三个实用技巧

技巧一：用小规模暴力对拍。写一个递归暴力搜索的版本，对n≤4、每堆≤6的所有局面，与你的公式版本逐一对比。如果全部一致，基本可以确认公式正确。这个方法帮我抓出过好几次边界条件的错误。

技巧二：打印中间状态。在计算异或和或SG值时，把每一步的中间结果打印出来。特别是Moore's Nim-k的逐位统计，很容易在某一位上算错，打印出来一目了然。

技巧三：注意空堆的处理。有些题目允许堆数为0，或者取完后堆消失。在计算异或和时，0不影响结果，但在计算SG值或统计位数时，空堆可能导致数组越界或除零错误。我习惯在输入处理后先过滤掉0堆，除非题目明确要求保留。

6. 那些年我在尼姆博弈上踩过的坑

6.1 把"异或和为0"当成"必输"的唯一条件

这是最经典的坑。在正常尼姆里，异或和为0确实是必败态，但在反尼姆里，全1局面的判定完全不同。我曾经在一道反尼姆题上，因为没处理全1情况，连续WA了五次，最后对着(1,1,1)这个样例手动模拟才发现问题。

教训：每次看到"取到最后一颗输"这类字眼，立刻警觉是不是反尼姆，先检查全1情况。

6.2 Moore's Nim-k中k值的理解偏差

Moore's Nim-k的"每次最多操作k堆"，我一开始理解成了"每次最多取k颗"，导致判定条件完全写错。这两个概念差得很远：前者限制的是操作的堆数，后者限制的是单堆取石数。

后来我养成了一个习惯：读题时把"每次可以……"这句话逐字拆开，明确三个要素——操作对象（几堆）、操作数量（几颗）、操作方向（取走还是移动）。这三个要素任何一个理解错，公式就会用错。

6.3 SG值打表时的mex计算效率问题

在计算SG值时，如果用集合存储可达状态再逐个检查mex，当状态数很大时效率会很低。我优化过的一个写法是用布尔数组标记：

def compute_sg_fast(max_n, max_take): sg = [0] * (max_n + 1) for i in range(1, max_n + 1): visited = [False] * (max_take + 2) for take in range(1, min(i, max_take) + 1): v = sg[i - take] if v < len(visited): visited[v] = True g = 0 while visited[g]: g += 1 sg[i] = g return sg

这个写法的关键是visited数组的大小要足够，至少是max_take+2，因为SG值不会超过可达状态数。如果开小了会越界，开大了浪费空间。我一般开到max_take+2就够用。

6.4 多组测试数据的初始化问题

尼姆博弈题经常有多组测试数据，如果SG值打表是在循环外只算一次，要注意表的范围是否覆盖所有测试用例的最大值。我有一次因为表只打到了1000，而某组数据有1500颗石子，导致数组越界。后来改成先读入所有数据、找到最大值、再打表，就再也没出过这个问题。

6.5 阶梯尼姆中台阶编号的陷阱

阶梯尼姆的结论是"只看奇数级台阶"，但台阶编号是从1开始还是从0开始，会影响奇偶判断。有些题目把最底层台阶编号为0，有些编号为1。我在一道题上因为没注意这个细节，把奇偶搞反了，样例都过不了。

应对方法：读完题后先确认编号规则，然后手动模拟一个最简单的样例（比如只有一级台阶有一颗石子）来验证自己的奇偶判断是否正确。

7. 从尼姆博弈延伸出去：组合博弈的学习路径

尼姆博弈是组合博弈论的入口，但远不是终点。如果你已经掌握了正常尼姆、反尼姆、Moore's Nim-k和SG定理，接下来可以往这几个方向深入：

第一个方向是SG定理的更多应用。比如"取石子后堆会分裂"的游戏（如Grundy's Game）、"在图上移动棋子"的游戏（如Green Hackenbush），这些游戏的SG值计算各有技巧，但底层逻辑都是SG定理。

第二个方向是博弈与DP的结合。当游戏状态空间很大、无法直接打表时，需要用DP或记忆化搜索来计算SG值。这类题目往往需要先分析状态转移方程，再优化计算效率。

第三个方向是博弈中的策略输出。很多竞赛题不仅要求判断胜负，还要求输出最优策略或策略数量。这需要在判定条件的基础上，进一步分析状态转移的具体路径。

第四个方向是博弈与组合计数的结合。比如"有多少种初始局面是先手必胜"这类计数问题，需要结合异或的性质和组合数学。

我在学习路径上的建议是：先把正常尼姆的证明彻底搞懂，再学SG定理，然后用SG定理重新推导一遍反尼姆和Moore's Nim-k的结论。这个"从特殊到一般，再从一般回到特殊"的过程，比死记结论有效得多。

最后分享一个我个人的习惯：每次遇到新的博弈变形题，先不急着写代码，而是用纸笔列出小规模的所有状态，手动标出必胜态和必败态，观察规律。这个"手动打表"的过程虽然慢，但能帮你建立对问题的直觉。等直觉建立起来之后，再去看公式和定理，理解会深刻很多。尼姆博弈的异或判定、SG定理的mex计算、反尼姆的全1分叉，这些结论我都是先手动验证了几十个状态之后才真正记住的，比单纯背公式牢靠得多。