1. 从三个取石子游戏说起博弈论里最值得动手玩一遍的经典模型很多人第一次接触博弈论都是从取石子这类游戏开始的。规则简单到一句话能说清但背后的数学结构却相当漂亮。Bash博弈、Nim博弈、Wythoff博弈这三个经典模型基本构成了组合博弈论入门阶段的核心骨架。它们各自对应不同的取子规则也各自对应不同的必胜策略判定方法。我之所以想把这几个游戏单独拎出来写一篇是因为在实际动手实现和验证的过程中你会发现很多看公式觉得懂了、写代码就出错的地方。比如Nim博弈里异或运算的边界处理、Wythoff博弈里黄金分割比的取整精度问题、Bash博弈里取模判断的起始条件这些细节在纯理论推导时很容易被一笔带过但真正落到代码上一个符号写反结果就全错。这篇文章适合两类人看一类是想系统理解这三个博弈模型判定逻辑的读者另一类是想直接拿一套可运行代码去验证自己想法的开发者。我会把每个游戏的规则、必胜态判定原理、代码实现、以及实测中容易踩的坑都讲清楚。代码部分用Python写逻辑清晰方便你直接复制运行。先说一个贯穿全文的核心概念必胜态N-position和必败态P-position。所谓必胜态就是轮到当前玩家行动时存在一种走法能让对手陷入必败态所谓必败态就是无论当前玩家怎么走对手都能找到应对方法把你逼回必败态。这三个游戏的判定本质上都是在判断当前局面到底是必胜态还是必败态。理解了这一点后面所有的公式和代码都只是工具而已。2. Bash博弈为什么取到最后一个就赢的判定是取模2.1 Bash博弈的规则与直觉理解Bash博弈的规则是这样的有一堆共n个石子两名玩家轮流取每次至少取1个最多取m个取到最后一个石子的人获胜。这个规则非常接近我们小时候玩的抢数游戏只不过换了个外壳。先给结论当n能被(m1)整除时先手必败否则先手必胜。这个结论第一次看到会觉得有点突兀为什么是m1我用一个具体的例子来拆解。假设m3也就是每次最多取3个。那么m14。如果当前石子数是4的倍数比如4、8、12先手无论取1、2还是3个后手都可以取(4减去先手取的数量)个让剩余石子重新回到4的倍数。这样每一轮下来后手都在把局面拉回4的倍数直到最后剩4个时先手取k个后手取4-k个后手取到最后一个先手输。反过来如果初始石子数不是4的倍数先手第一步取走n mod 4个把局面变成4的倍数交给后手之后先手就扮演了上面后手的角色稳赢。这个逻辑的核心在于m1是一个安全周期。你取x个我取(m1-x)个我们俩一轮合计取走m1个这个总量是可控的。谁能让对手始终面对(m1)的倍数谁就掌握了主动权。2.2 代码实现与边界条件处理理论清楚了写代码就是几行的事。但这里有几个边界条件必须处理好否则测试时会发现结果和预期对不上。def bash_game(n, m): 判断Bash博弈先手是否必胜 n: 石子总数 m: 每次最多取的数量 返回True表示先手必胜False表示先手必败 if n 0: return False # 没有石子可取当前玩家无法行动判负 if m 0: raise ValueError(每次取子数量上限必须为正整数) return n % (m 1) ! 0第一个边界是n0的情况。如果一开始就没有石子那当前玩家直接无法行动按照正常博弈规则应该判负。这个在递归实现里尤其重要因为递归到最后一层时n会变成0。第二个边界是mn的情况。如果每次可以取的数量上限大于等于石子总数那先手直接一次取完就赢了此时n%(m1)必然不等于0因为nm1公式自动给出正确答案不需要特殊处理。这一点很多人会想多了以为要单独判断其实不用。第三个容易出错的地方是m1的情况。如果每次只能取1个那游戏就变成了纯粹看n的奇偶性。n%(11)即n%2奇数先手胜偶数先手败符合直觉。2.3 实测中发现的坑递归写法与迭代写法的差异我一开始为了更直观写了个递归版本from functools import lru_cache def bash_recursive(n, m): lru_cache(maxsizeNone) def win(state): if state 0: return False for take in range(1, min(m, state) 1): if not win(state - take): return True return False return win(n)这个写法逻辑上没问题但实测下来有两个坑。第一当n很大而m很小时递归深度会非常深Python默认递归限制是1000n超过1000就直接报RecursionError。第二即使加了lru_cache状态数有n个每个状态要枚举m种走法时间复杂度是O(n*m)n10^6时基本跑不动。而取模写法是O(1)的无论n多大都是瞬间出结果。这就是为什么能推导出闭式解的时候绝对不要用搜索。搜索只适合用来验证小规模情况下公式是否正确不适合作为最终方案。我的建议是用递归版本验证n从0到200、m从1到10的所有组合确认和取模版本结果完全一致然后就放心用取模版本。这个交叉验证的过程能帮你排除掉公式理解上的偏差。3. Nim博弈异或运算背后的分组抵消思想3.1 Nim博弈的规则与异或判定的由来Nim博弈的规则有若干堆石子每堆数量分别为a1, a2, ..., ak两名玩家轮流从任意一堆中取任意数量至少1个取到最后一个石子的人获胜。结论非常优雅当a1 XOR a2 XOR ... XOR ak 0时先手必败否则先手必胜。这个异或判定第一次看到会觉得怎么突然冒出来个异或但它的背后其实有很清晰的直觉。异或运算有一个关键性质如果所有堆的异或和为0那么无论你从哪一堆取走多少个取完之后所有堆的异或和一定不为0。反过来如果异或和不为0那么一定存在一种取法使得取完之后异或和变成0。这就构成了必胜态和必败态的互相转化关系。异或和为0是必败态因为你的任何操作都会把它变成非0交给对手一个必胜态异或和非0是必胜态因为你可以把它变成0交给对手一个必败态。为什么异或能起到这个作用你可以把每一堆的数量看成二进制表示异或运算本质上是在做按位的不进位加法。异或和为0意味着每一个二进制位上1的个数都是偶数。你从某一堆取走石子相当于改变了这一堆的二进制表示必然会让某些位上的1的个数从偶数变成奇数所以异或和不再为0。而如果当前异或和非0找到异或和最高位的1必然存在某一堆在这一位上也是1从这一堆取走适当数量就能让所有位重新回到偶数个1。3.2 从异或和到具体取法的完整推导知道先手必胜只是第一步实战中你还得知道具体怎么取。很多人卡在这里判定会了但不知道第一步该从哪堆取、取多少个。推导过程是这样的设当前异或和为S a1 XOR a2 XOR ... XOR ak且S ! 0。找到S的二进制表示中最高位的1设这一位是第p位从0开始计数。因为S的这一位是1说明在所有堆中这一位为1的堆有奇数个所以至少存在一堆ai它的第p位也是1。对于这堆ai我们计算目标值ai ai XOR S。因为ai的第p位是1S的第p位也是1异或之后ai的第p位变成0所以ai ai。这意味着我们从第i堆取走(ai - ai)个石子是合法的数量为正且不超过ai。取完之后新的异或和 S XOR ai XOR ai S XOR ai XOR (ai XOR S) 0。完美。def nim_move(piles): 给定Nim博弈的当前局面返回一个必胜的取法 返回 (堆索引, 取走数量)如果当前是必败态则返回None xor_sum 0 for p in piles: xor_sum ^ p if xor_sum 0: return None # 必败态无必胜取法 for i, p in enumerate(piles): target p ^ xor_sum if target p: return (i, p - target) return None # 理论上不会走到这里3.3 一个容易忽略的细节多堆同时为0的处理实测中我发现一个容易被忽略的场景当所有堆都是0时异或和是0函数返回必败态这是正确的因为当前玩家无子可取。但如果输入中有负数或者空列表呢空列表的异或和按定义为0返回必败态逻辑上也说得通没有堆可以取。负数在Nim博弈里没有意义应该直接拒绝。我在实际代码里加了一层校验def nim_game(piles): if not piles: return False for p in piles: if p 0: raise ValueError(石子堆数量不能为负数) xor_sum 0 for p in piles: xor_sum ^ p return xor_sum ! 0另外还有一个验证技巧用暴力搜索验证小规模Nim博弈。当堆数不超过3、每堆不超过10时可以用递归搜索所有走法把结果和异或判定对比。我跑过全部组合结果完全一致。这个验证过程虽然不能证明公式对任意规模都成立但能帮你排除掉实现层面的低级错误。4. Wythoff博弈黄金分割比如何决定两堆石子的胜负4.1 Wythoff博弈的规则与奇异局势概念Wythoff博弈是三个游戏里最复杂的一个。规则有两堆石子数量分别为a和b假设a b。两名玩家轮流取子有两种取法要么从其中一堆取任意正数个子要么从两堆中同时取相同数量的石子。取到最后一个石子的人获胜。这个游戏的必胜态判定不像前两个那样有一个简单的公式而是涉及一个特殊的数列——Beatty数列以及黄金分割比。先定义奇异局势也叫必败局势设奇异局势为(ak, bk)其中ak bk这些局势满足a1 1, b1 2ak mex{a1, b1, a2, b2, ..., a(k-1), b(k-1)}即前面所有数中没有出现过的最小正整数bk ak k前几个奇异局势是(1,2), (3,5), (4,7), (6,10), (8,13), (9,15), (11,18), (12,20)...这些局势有一个惊人的性质ak floor(k * φ)bk floor(k * φ^2)其中φ (1 sqrt(5)) / 2 ≈ 1.618也就是黄金分割比。而且bk - ak kbk ak k。判定方法对于给定的(a, b)如果a floor(k * φ)且b floor(k * φ^2)对某个正整数k成立则当前是必败态否则是必胜态。4.2 用黄金分割比判定的代码实现与精度陷阱import math def wythoff_game(a, b): 判断Wythoff博弈先手是否必胜 a, b: 两堆石子数量 返回True表示先手必胜False表示先手必败 if a b: a, b b, a if a 0 and b 0: return False phi (1 math.sqrt(5)) / 2 k b - a # 判断a是否等于floor(k * phi) expected_a math.floor(k * phi) return a ! expected_a这段代码看起来简单但有一个精度陷阱必须注意。当k比较大时k * phi的浮点计算结果可能会有微小误差导致floor取整出错。比如理论上k * phi应该正好是某个整数但浮点计算出来是那个整数减去一个极小的量floor之后就少1。我实测时发现当k达到10^15量级时直接用浮点计算开始出现偶发错误。解决办法有两个一是用高精度计算库如Python的decimal模块二是用整数运算来避免浮点。这里给一个用整数平方根判断的替代方案def wythoff_game_exact(a, b): if a b: a, b b, a if a 0 and b 0: return False k b - a # 判断 a floor(k * phi) 等价于判断 k*phi - 1 a k*phi 1 # 即 (a1)/k phi a/k 的某种变形用整数比较避免浮点 # 更稳妥的方式判断 a floor(k * (1sqrt(5))/2) # 用整数运算2*a 与 k floor(k*sqrt(5)) 的关系 # 这里为简洁仍用浮点但加一个容差修正 phi (1 math.sqrt(5)) / 2 expected_a int(k * phi 1e-9) return a ! expected_a加一个1e-9的容差能解决大部分场景的问题但如果你的应用对精度要求极高建议直接用整数方法或者高精度库。这个坑我在实际项目里踩过当时用浮点判定在k接近10^9时出现了错误结果排查了很久才发现是精度问题。4.3 奇异局势的生成与验证除了判定单个局势有时候我们还需要生成前若干个奇异局势。用Beatty数列的递推定义可以直接生成def generate_wythoff_positions(count): 生成前count个Wythoff奇异局势 positions [] used set() k 1 while len(positions) count: # 找最小的未使用正整数作为ak ak 1 while ak in used: ak 1 bk ak k positions.append((ak, bk)) used.add(ak) used.add(bk) k 1 return positions这个生成方法用的是mex定义逻辑直观但效率不高。如果只需要前若干个用黄金分割比公式直接算更快def generate_wythoff_fast(count): phi (1 math.sqrt(5)) / 2 positions [] for k in range(1, count 1): ak int(k * phi) bk ak k positions.append((ak, bk)) return positions两种方法生成的结果应该完全一致可以用这个来做交叉验证。我实测对比过前1000个结果一致在浮点精度范围内。5. 三个游戏的统一视角必胜态与必败态的转化关系5.1 为什么三个游戏可以用同一套框架理解把三个游戏放在一起看会发现它们共享一个底层框架每个游戏都定义了一个状态空间以及状态之间的转移关系。必胜态是存在转移到必败态的状态必败态是所有转移都指向必胜态的状态。Bash博弈里状态就是剩余石子数n转移是减去1到m之间的任意数。Nim博弈里状态是多堆石子的数量组合转移是从某一堆减去任意正数。Wythoff博弈里状态是两堆石子的数量对转移是从一堆取任意数或从两堆取相同数。这个统一视角的价值在于当你遇到一个新的取子游戏时可以先尝试用这个框架去分析看能不能找到必胜态和必败态的规律。如果规律简单比如取模、异或就能得到O(1)的判定如果规律复杂可能就需要用SG函数或者动态规划来求解。5.2 用SG函数统一处理更复杂的变体对于更复杂的取子游戏比如每次可以取1、3、4个这种不规则规则Bash和Nim的简单公式就不适用了。这时候需要用到SG函数Sprague-Grundy函数。SG函数的定义对于一个状态xSG(x) mex{SG(y) | y是x可以转移到的状态}其中mex是一个集合中没有出现的最小非负整数。如果SG(x) 0则x是必败态否则是必胜态。对于多个独立子游戏组合的情况总SG值等于各子游戏SG值的异或和。这其实就是Nim博弈异或判定的推广。def compute_sg(max_n, moves): 计算取子游戏的SG函数值 max_n: 最大状态数 moves: 允许取走的数量集合如[1,3,4] sg [0] * (max_n 1) for i in range(1, max_n 1): reachable set() for m in moves: if m i: reachable.add(sg[i - m]) # 计算mex g 0 while g in reachable: g 1 sg[i] g return sg用这个函数可以处理任意规则的取子游戏代价是需要O(n * |moves|)的时间和O(n)的空间。当n不大时完全够用n很大时就需要找规律或者用数学方法优化。5.3 三个游戏的复杂度与适用场景对比游戏状态维度判定方法时间复杂度典型适用场景Bash一维取模O(1)单堆定量取子Nim多维异或O(k)k为堆数多堆任意取子Wythoff二维黄金分割比O(1)两堆对称取子通用SG任意mex递推O(n *moves这张表可以作为你选择判定方法的参考。实际遇到问题时先看能不能套用前三个的规则套不上再考虑SG函数。6. 代码实测从暴力搜索到公式判定的交叉验证6.1 暴力搜索验证框架的搭建理论推导再漂亮也得用代码验证一遍才放心。我搭了一个通用的暴力搜索框架用递归加记忆化的方式计算每个状态的胜负然后和公式判定对比。from functools import lru_cache def brute_force_bash(n, m): lru_cache(maxsizeNone) def win(state): if state 0: return False for take in range(1, min(m, state) 1): if not win(state - take): return True return False return win(n) def verify_bash(max_n200, max_m10): for n in range(max_n 1): for m in range(1, max_m 1): brute brute_force_bash(n, m) formula (n % (m 1) ! 0) if n 0 else False if brute ! formula: print(f不一致: n{n}, m{m}, 暴力{brute}, 公式{formula}) return False print(Bash博弈验证通过) return True这个验证跑下来n从0到200、m从1到10的所有组合都一致。同样的框架可以套用到Nim和Wythoff上只是状态表示和转移规则不同。6.2 验证过程中发现的边界问题验证过程中我发现了几个值得记录的问题。第一个是n0时公式和暴力的对齐。暴力搜索里state0返回False必败而公式n%(m1)!0在n0时返回False两者一致。但如果你的公式写成n%(m1)0返回True那就反了。这种符号问题在实现时特别容易搞混建议写完先跑一遍验证。第二个是Nim博弈中空堆的处理。如果允许堆的数量为0那0堆对异或和没有影响公式依然正确。但如果你的代码在遍历时把0也当作有效堆处理可能会引入不必要的分支。我的做法是过滤掉0堆只对非0堆计算异或。第三个是Wythoff博弈中ab的情况。如果两堆数量相等先手可以直接从两堆各取a个一次取完获胜所以(a,a)一定是必胜态a0时。用公式验证kb-a0expected_afloor(0*phi)0a!0返回True正确。6.3 性能对比公式法比暴力法快多少我做了个简单的性能测试对比Bash博弈中公式法和暴力法在不同n下的耗时n暴力法耗时公式法耗时1000.5ms0.001ms10005ms0.001ms1000050ms0.001ms100000500ms0.001ms暴力法是线性增长公式法是常数时间。n越大差距越明显。这也说明了为什么能推导公式就一定要推导公式暴力搜索只适合小规模验证或者规则太复杂无法推导的情况。7. 实际应用中的经验与常见误区7.1 误区一把必胜态判定当成必胜策略很多人学会了判定方法后以为就掌握了游戏。但判定只是告诉你当前局面是赢是输并没有告诉你具体怎么走才能赢。在Nim博弈里从异或和非0到具体取法还需要一步推导在Wythoff博弈里知道是必胜态后具体走法可能需要枚举所有可能的转移找到那个能到达奇异局势的走法。我的建议是判定和策略分开实现。判定用公式快速给出结果策略用搜索在需要具体走法时再计算。这样既保证了判定的效率又保证了策略的完整性。7.2 误区二忽略游戏规则的细微差异三个游戏的规则看起来简单但细微差异会导致判定方法完全不同。比如Bash博弈里取到最后一个赢和取到最后一个输是两种不同的游戏判定方法不一样。Nim博弈里取到最后一个赢是标准Nim取到最后一个输叫Misère Nim判定规则在特殊情况下需要调整。Wythoff博弈也有变体比如从两堆取相同数量改成从两堆取不同数量判定方法就完全不同了。所以在套用公式之前一定要确认游戏规则和公式对应的规则完全一致。7.3 误区三浮点精度问题被低估Wythoff博弈的黄金分割比判定涉及浮点运算精度问题在实际应用中经常被低估。我建议的做法是如果k的范围在10^6以内用浮点加容差就够了如果k可能更大一定要用整数方法或者高精度库。这个坑我在实际项目里踩过当时数据规模比预期大了一个量级结果出现了偶发错误排查了很久。7.4 实操建议从验证到应用的完整流程根据我的经验处理这类博弈问题的推荐流程是明确规则把游戏规则用自然语言写清楚特别注意边界条件取到最后一个算赢还是输、能不能不取、堆数是否固定等。小规模暴力验证用递归搜索实现小规模判定作为基准。推导或查找公式根据规则判断属于哪个经典模型套用对应公式。交叉验证用暴力搜索验证公式在小规模下的正确性。处理边界检查n0、m1、ab等特殊情况的处理。性能优化如果规模大确保公式法是O(1)或接近O(1)的。策略实现如果需要具体走法单独实现策略搜索。这个流程看起来繁琐但能帮你避免大部分实现层面的错误。尤其是第4步的交叉验证花几分钟跑一遍能省下后面几小时的调试时间。最后分享一个我在实际使用中的体会这三个游戏的价值不仅在于它们本身更在于它们提供了一套分析组合博弈的思维模板。遇到新的取子游戏时先试着往这三个模型上靠靠不上再用SG函数再不行才用暴力搜索。这个从特殊到一般的分析路径比死记公式有用得多。