1. 从取石子游戏说起尼姆博弈到底在解决什么问题很多人第一次接触博弈论都是从一堆石子开始的。两堆石子两个人轮流取每次可以从任意一堆里取任意多颗取到最后一颗的人赢——这个看似简单的小游戏背后藏着一整套算法竞赛里高频出现的数学模型。尼姆博弈Nim Game就是这类取石子游戏的经典代表也是组合博弈论里最基础、最重要的一块基石。我在带新人刷题的时候发现一个现象大部分人能背出异或和为0则先手必败这个结论但一旦题目变形——比如限制每次最多取k颗、或者石子堆数量动态变化、或者要求输出具体的第一步策略——就立刻卡壳。根本原因在于他们只记住了公式没有理解尼姆博弈的状态转移逻辑和必胜态/必败态的判定本质。这篇文章面向的是已经了解基础博弈论知道什么是P-position和N-position、但在尼姆博弈的高阶变形题上反复翻车的读者。我会从最朴素的暴力搜索讲起一步步推导到Sprague-Grundy定理再延伸到反尼姆博弈、Moores Nim-k、阶梯尼姆等高频变形最后给出可直接套用的代码模板和我在实际比赛中踩过的坑。不管你是准备算法竞赛还是单纯想搞懂这类问题的底层逻辑这篇内容都能让你少走很多弯路。需要提前说明的是尼姆博弈的高阶篇并不是指某个单一的算法而是一类问题的统称。它们的共同特征是游戏可以分解为若干个独立的子游戏每个子游戏的状态可以用一个非负整数SG值表示整个游戏的胜负由所有子游戏SG值的异或和决定。理解了这条主线后面所有的变形都只是在这条主线上做加减法。2. 尼姆博弈的数学根基为什么异或和能判定胜负2.1 从暴力枚举到规律发现先回到最原始的尼姆博弈定义有n堆石子第i堆有a_i颗。两人轮流操作每次选择一堆从中取走至少一颗、至多整堆的石子。取走最后一颗石子的人获胜正常规则Normal Play。对于小规模的情况我们可以用递归暴力搜索所有状态来判断胜负。假设状态用石子堆的元组表示比如(3, 4, 5)那么from functools import lru_cache lru_cache(maxsizeNone) 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位是1S的第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经过一次合法操作能到达的状态 }其中mexminimum excludant是一个集合中最小非负整数的意思。比如mex{0,1,3} 2mex{1,2} 0mex{} 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_take3的情况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 (k1)整个游戏的SG值是所有(a_i mod (k1))的异或和。如果这个异或和非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 ! 04.2 Moores Nim-k每次最多操作k堆Moores Nim-k是尼姆博弈的另一个重要推广每次可以选择至多k堆从每堆中取走任意多颗至少一颗。当k1时退化为普通尼姆博弈。这个变形的判定条件不再是简单的异或和而是按二进制位统计对于每一个二进制位统计所有堆在该位上为1的个数将这些个数对(k1)取模。如果所有位的模值都为0则先手必败否则先手必胜。我举个具体例子。假设k2三堆石子分别为(1, 2, 3)第0位最低位1的个数是2来自1和32 mod 3 2第1位1的个数是2来自2和32 mod 3 2模值不全为0所以先手必胜。再比如(1, 1, 1)k2第0位1的个数是33 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级i1或者从第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 通用尼姆博弈判定模板把前面讲的内容整合成一个通用的判定函数覆盖正常尼姆、反尼姆、Moores Nim-k三种常见情况def solve_nim(piles, modenormal, k1): piles: 各堆石子数列表 mode: normal 正常尼姆, misere 反尼姆, moore Moores Nim-k k: Moores 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 False5.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值时把每一步的中间结果打印出来。特别是Moores Nim-k的逐位统计很容易在某一位上算错打印出来一目了然。技巧三注意空堆的处理。有些题目允许堆数为0或者取完后堆消失。在计算异或和时0不影响结果但在计算SG值或统计位数时空堆可能导致数组越界或除零错误。我习惯在输入处理后先过滤掉0堆除非题目明确要求保留。6. 那些年我在尼姆博弈上踩过的坑6.1 把异或和为0当成必输的唯一条件这是最经典的坑。在正常尼姆里异或和为0确实是必败态但在反尼姆里全1局面的判定完全不同。我曾经在一道反尼姆题上因为没处理全1情况连续WA了五次最后对着(1,1,1)这个样例手动模拟才发现问题。教训每次看到取到最后一颗输这类字眼立刻警觉是不是反尼姆先检查全1情况。6.2 Moores Nim-k中k值的理解偏差Moores 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_take2因为SG值不会超过可达状态数。如果开小了会越界开大了浪费空间。我一般开到max_take2就够用。6.4 多组测试数据的初始化问题尼姆博弈题经常有多组测试数据如果SG值打表是在循环外只算一次要注意表的范围是否覆盖所有测试用例的最大值。我有一次因为表只打到了1000而某组数据有1500颗石子导致数组越界。后来改成先读入所有数据、找到最大值、再打表就再也没出过这个问题。6.5 阶梯尼姆中台阶编号的陷阱阶梯尼姆的结论是只看奇数级台阶但台阶编号是从1开始还是从0开始会影响奇偶判断。有些题目把最底层台阶编号为0有些编号为1。我在一道题上因为没注意这个细节把奇偶搞反了样例都过不了。应对方法读完题后先确认编号规则然后手动模拟一个最简单的样例比如只有一级台阶有一颗石子来验证自己的奇偶判断是否正确。7. 从尼姆博弈延伸出去组合博弈的学习路径尼姆博弈是组合博弈论的入口但远不是终点。如果你已经掌握了正常尼姆、反尼姆、Moores Nim-k和SG定理接下来可以往这几个方向深入第一个方向是SG定理的更多应用。比如取石子后堆会分裂的游戏如Grundys Game、在图上移动棋子的游戏如Green Hackenbush这些游戏的SG值计算各有技巧但底层逻辑都是SG定理。第二个方向是博弈与DP的结合。当游戏状态空间很大、无法直接打表时需要用DP或记忆化搜索来计算SG值。这类题目往往需要先分析状态转移方程再优化计算效率。第三个方向是博弈中的策略输出。很多竞赛题不仅要求判断胜负还要求输出最优策略或策略数量。这需要在判定条件的基础上进一步分析状态转移的具体路径。第四个方向是博弈与组合计数的结合。比如有多少种初始局面是先手必胜这类计数问题需要结合异或的性质和组合数学。我在学习路径上的建议是先把正常尼姆的证明彻底搞懂再学SG定理然后用SG定理重新推导一遍反尼姆和Moores Nim-k的结论。这个从特殊到一般再从一般回到特殊的过程比死记结论有效得多。最后分享一个我个人的习惯每次遇到新的博弈变形题先不急着写代码而是用纸笔列出小规模的所有状态手动标出必胜态和必败态观察规律。这个手动打表的过程虽然慢但能帮你建立对问题的直觉。等直觉建立起来之后再去看公式和定理理解会深刻很多。尼姆博弈的异或判定、SG定理的mex计算、反尼姆的全1分叉这些结论我都是先手动验证了几十个状态之后才真正记住的比单纯背公式牢靠得多。