博弈论这个词听起来像是经济学课堂上的高深概念但实际上它离我们非常近。只要涉及到两个或多个人做决策、彼此影响结果博弈就发生了。而“三大游戏”——Bash博弈、Nim博弈、Wythoff博弈是组合博弈论里最经典、最常被拿出来讲的三颗明珠。它们看起来只是简单的取石子游戏但背后藏着完整的数学结构必胜态与必败态的划分、SG函数、Beatty定理等等。我第一次接触这三个游戏的时候觉得规则简单到有点无聊但真正动手推导了一遍必胜策略之后才发现这里面的思维方式可以直接迁移到很多现实决策场景中。这篇文章我会把这三个游戏的来龙去脉、核心原理、必胜策略的推导过程、代码实现以及我在实际操作中踩过的坑全部拆开讲清楚。不管你是刚接触博弈论的新手还是想复习一下组合博弈的老手应该都能从里面拿到有用的东西。1. 三大博弈游戏的整体设计与思路拆解1.1 为什么是这三个游戏组合博弈论里有非常多取石子类的游戏但Bash、Nim、Wythoff这三个之所以被反复提及是因为它们构成了一个从简单到复杂的完整阶梯。Bash博弈是最基础的一层一堆石子每次取1到m个谁取最后一个谁赢。它的必胜策略非常直接基本上理解了“余数”这个概念就能掌握。Nim博弈进了一步多堆石子每次可以从任意一堆里取任意多个谁取最后一个谁赢。它的必胜策略需要用到异或运算是二进制思维在博弈论里最漂亮的应用之一。Wythoff博弈则再上一层两堆石子每次可以从一堆里取任意多个或者从两堆里同时取相同数量的石子谁取最后一个谁赢。它的必胜态涉及Beatty定理和黄金分割比是三个游戏里数学味最浓的。这三个游戏放在一起刚好覆盖了组合博弈论里三种不同层次的思维方式余数思维、异或思维、以及数学构造思维。你把这几个吃透了再去看其他变体游戏会发现很多都是在这三个基础上做加减法。1.2 核心概念必胜态与必败态在展开具体游戏之前必须先把这个核心概念说清楚不然后面所有推导都无从谈起。在组合博弈中我们通常做这样的定义一个状态是必败态如果轮到当前玩家行动时无论他怎么走都会把局面交给对手一个必胜态一个状态是必胜态如果存在至少一种走法能让对手面对一个必败态。这个定义是递归的。最简单的终止状态——比如没有石子可取了——通常是必败态因为轮到你时你已经没法行动了按照正常规则你就输了。然后从这个终止状态往回推就能确定所有状态的胜负属性。我习惯用一个生活化的类比来理解把必败态想象成一个“烫手山芋”谁拿到谁倒霉。必胜态就是你手里有一个办法能把这个山芋扔给对方。所以整个博弈的过程就是双方轮流扔山芋谁最后手里拿着山芋谁就输了。注意必胜态和必败态的判断依赖于具体的游戏规则。同一个局面在不同规则下可能是必胜态也可能是必败态。所以每次分析新游戏时第一步永远是明确规则。1.3 从暴力搜索到数学规律对于任何一个组合博弈理论上你都可以用递归加记忆化的方式暴力搜索出每个状态的胜负属性。但暴力搜索的问题是状态空间可能非常大尤其是Nim和Wythoff这种状态数量随石子数增长的游戏。所以真正的思路是先用暴力搜索小规模的状态观察规律然后尝试用数学方式证明这个规律最后得到一个O(1)或O(log n)的判断方法。这个“暴力打表找规律再证明”的流程是我在做这类问题时最常用的方法论。三个游戏的具体规律各不相同但推导路径是一致的。下面我逐个拆解。2. Bash博弈余数思维的最佳入门2.1 规则与基本分析Bash博弈的规则很简单只有一堆石子数量为n。两个人轮流取每次至少取1个最多取m个。取走最后一个石子的人获胜。先看最简单的情况。如果n ≤ m那先手直接一次全部取完先手必胜。这个没什么好说的。如果n m 1呢先手无论取多少个1到m个剩下的石子数量都在1到m之间后手可以一次全部取完。所以n m 1是先手必败态。再往下推。如果n m 2呢先手可以取1个剩下m 1个给后手后手面对的是必败态所以先手必胜。同理n从m 2到2m 1先手都可以通过取适当数量让剩下的石子变成m 1从而获胜。到了n 2m 2先手无论怎么取剩下的数量都在m 2到2m 1之间而这些全是必胜态所以n 2m 2是必败态。规律已经很清楚了必败态是n % (m 1) 0的所有状态。2.2 必胜策略的完整推导为什么是m 1这个周期核心逻辑是这样的如果n能被(m 1)整除那么无论先手取k个1 ≤ k ≤ m剩下的数量n - k一定不能被(m 1)整除因为n是(m 1)的倍数减去一个1到m之间的数之后余数就是(m 1 - k)这个值在1到m之间不为零。然后后手可以取(m 1 - k)个让剩下的石子重新变成(m 1)的倍数。这样每一轮下来后手都能把局面恢复到(m 1)的倍数状态。最终当石子数变成0时刚好是先手面对0因为0也是(m 1)的倍数先手无法行动先手输。反过来如果n不能被(m 1)整除先手只需要取n % (m 1)个石子就能把局面变成(m 1)的倍数交给后手一个必败态。之后先手只需要模仿上面后手的策略每次取(m 1 - k)个就能保证获胜。这个策略的美妙之处在于它的对称性你取多少我就补到m 1。这种“补足”思维在很多博弈问题里都会出现。2.3 代码实现与实操细节Bash博弈的判断代码非常简单一行就够了def bash_game(n, m): 判断Bash博弈先手是否必胜 n: 石子总数 m: 每次最多取的数量 返回True表示先手必胜False表示先手必败 return n % (m 1) ! 0但实际写代码的时候有几个细节需要注意。第一个是边界条件。如果n 0按照规则先手无法行动先手输。n % (m 1) 0返回False正确。如果m 0呢这意味着每次只能取0个游戏永远无法结束。这种退化情况在实际问题中通常不会出现但写通用函数的时候最好加一个参数校验。第二个是如果题目问的是“谁取最后一个谁输”也就是Misère版本那策略会完全不同。Misère Bash博弈的必败态判断会变成n % (m 1) 1当n 1时。这个变体我在实际做题时遇到过好几次每次都要重新推一遍所以建议把两个版本的判断条件都记住。第三个是当m ≥ n时先手直接全取完必胜。这个情况其实已经被n % (m 1) ! 0覆盖了因为如果m ≥ n那m 1 nn % (m 1) n ≠ 0返回True。逻辑上是自洽的。实操心得Bash博弈虽然简单但它是理解“周期性格局”的最佳入口。很多复杂的博弈问题拆到最后都会发现某个子游戏本质上就是一个Bash博弈。所以不要因为它简单就跳过把这个余数思维刻在脑子里后面会反复用到。3. Nim博弈异或运算的经典应用3.1 从两堆到多堆的思维跃迁Nim博弈的规则是有若干堆石子每堆数量任意。两个人轮流操作每次可以从任意一堆中取走任意多个至少1个取走最后一个石子的人获胜。如果只有一堆那和Bash博弈里m无限大的情况一样先手直接全取完就赢了。如果有两堆呢假设两堆数量分别是a和b。如果a b先手取多少后手就在另一堆取同样的数量始终保持两堆相等。最终先手面对两堆都是0的局面先手输。所以两堆相等是必败态。如果a ≠ b呢先手从多的那堆取走|a - b|个让两堆变成相等交给后手一个必败态。所以两堆不等是先手必胜。两堆的情况很直观。但到了三堆、四堆甚至更多堆就没法用“保持相等”这种简单策略了。这时候需要引入一个新的数学工具异或运算。3.2 异或运算的核心原理先简单说一下异或运算XOR。异或的规则是两个二进制位相同则为0不同则为1。比如5 XOR 3101 XOR 011 ------- 110 6异或运算有几个关键性质a XOR a 0a XOR 0 a异或运算满足交换律和结合律。Nim博弈的必胜态判断定理是把所有堆的石子数量做异或运算如果结果不为0先手必胜如果结果为0先手必败。这个定理的证明思路和Bash博弈的余数思维有相似之处。异或结果为0的状态无论你怎么取都会让异或结果变成非0而异或结果非0的状态你总存在一种取法能让异或结果重新变成0。具体来说假设当前所有堆的异或结果是S ≠ 0。设S的最高位1在第k位从低位往高位数的第k位。那么一定存在某一堆石子其第k位也是1因为S的第k位是1说明有奇数堆的第k位是1。设这堆石子数量为x我们把这堆取到x XOR S。因为x XOR S xS的最高位和x的最高位相同异或之后最高位变成0所以结果一定小于x所以这是一个合法操作。操作之后所有堆的异或结果变成S XOR x XOR (x XOR S) S XOR S 0。这就证明了从异或非0的状态总能一步走到异或为0的状态。而异或为0的状态无论取哪一堆的多少个石子都会让异或结果变成非0因为改变了一堆的值异或结果必然改变。3.3 代码实现与策略还原Nim博弈的判断代码同样简洁from functools import reduce def nim_game(piles): 判断Nim博弈先手是否必胜 piles: 每堆石子数量的列表 返回True表示先手必胜False表示先手必败 xor_sum reduce(lambda x, y: x ^ y, piles, 0) return xor_sum ! 0但如果题目要求输出具体的必胜走法就需要多写几步def nim_winning_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这段代码的逻辑是找到一堆石子使得把它取到p XOR xor_sum之后整体异或结果变成0。因为p XOR xor_sum一定小于p前面证明过所以取走的数量就是p - (p XOR xor_sum)。注意Nim博弈可能有多个必胜走法上面的代码只返回找到的第一个。如果题目要求输出所有必胜走法或者特定条件下的走法需要遍历所有堆并收集所有满足条件的操作。3.4 Nim博弈的常见变体Nim博弈有很多变体我在实际中遇到过的主要有这几种Misère Nim取走最后一个石子的人输。这个变体的策略和标准Nim略有不同。如果所有堆的数量都是1那胜负取决于堆数的奇偶性奇数堆先手必败偶数堆先手必胜。如果至少有一堆数量大于1那策略和标准Nim一样用异或判断。这个结论我第一次看到的时候觉得很反直觉后来自己推了几组小数据才确认是对的。限制每次取的数量比如每次最多取m个。这种变体需要对每堆石子数量先对(m 1)取模然后再做异或。本质上就是把Bash博弈的余数思维和Nim的异或思维结合起来了。阶梯Nim石子放在阶梯上每次从某一级取若干石子放到下一级取到地面上的石子的人获胜。这个变体只需要考虑奇数级阶梯上的石子做异或偶数级的不用管。这个结论非常漂亮但证明需要一些技巧。4. Wythoff博弈黄金分割的博弈论呈现4.1 规则与与Nim的区别Wythoff博弈的规则是有两堆石子数量分别为a和b。两个人轮流操作每次可以有两种取法从其中一堆取任意多个至少1个或者从两堆中同时取相同数量的石子至少1个。取走最后一个石子的人获胜。和Nim的区别在于Nim可以从任意一堆取任意多个但不能同时从多堆取Wythoff只能操作两堆但多了一个“同时取相同数量”的选项。这个额外的选项让Wythoff博弈的数学结构比Nim复杂得多。4.2 必败态的规律发现先用暴力搜索打表看看必败态长什么样。假设a ≤ b列出小范围内的必败态ab差值0001213524736104813591561118712208观察这些数据能发现几个规律第一每个必败态的差值b - a是递增的从0开始每次加1。第二每个正整数恰好出现在一个必败态中作为a或b。第三a的值似乎和差值有关。具体来看差值为k的必败态中a的值是前面所有必败态中未出现过的最小正整数。比如差值为1时a 10已经出现过差值为2时a 31和2已经出现过差值为3时a 41、2、3、5已经出现过最小未出现的是4。这个规律可以递归地构造出所有必败态但我们需要一个封闭形式的公式。4.3 Beatty定理与黄金分割Wythoff博弈的必败态有一个非常漂亮的封闭形式涉及Beatty定理和黄金分割比。Beatty定理说的是如果两个正无理数α和β满足1/α 1/β 1那么数列{⌊nα⌋}和{⌊nβ⌋}n 1, 2, 3, ...恰好构成正整数的一个划分也就是说每个正整数恰好出现在其中一个数列中。对于Wythoff博弈取α φ (1 √5) / 2黄金分割比β φ² φ 1。可以验证1/φ 1/φ² 1。那么第n个必败态从n 0开始就是a_n ⌊nφ⌋b_n ⌊nφ²⌋ a_n n验证一下n 1时a ⌊1.618⌋ 1b ⌊2.618⌋ 2对应(1, 2)。n 2时a ⌊3.236⌋ 3b ⌊5.236⌋ 5对应(3, 5)。n 3时a ⌊4.854⌋ 4b ⌊7.854⌋ 7对应(4, 7)。和打表结果完全一致。所以Wythoff博弈的必胜态判断就变成了给定(a, b)且a ≤ b计算n b - a然后检查a是否等于⌊nφ⌋。如果等于就是必败态否则是必胜态。4.4 代码实现与浮点精度问题Wythoff博弈的判断代码看起来简单但有一个很大的坑浮点数精度。import math def wythoff_game(a, b): 判断Wythoff博弈先手是否必胜 a, b: 两堆石子数量 返回True表示先手必胜False表示先手必败 if a b: a, b b, a n b - a phi (1 math.sqrt(5)) / 2 expected_a int(n * phi) return a ! expected_a问题在于当n比较大的时候n * phi的浮点计算结果可能会有误差导致int()截断后的结果偏大或偏小1。比如n 1000000时n * phi ≈ 1618033.9887int()之后是1618033这是对的。但如果某个n使得n * phi的小数部分极其接近1浮点误差可能让它变成整数部分加1导致结果错误。解决方法是使用整数运算来避免浮点误差。可以利用黄金分割比的连分数逼近或者直接用整数平方根来计算。一个常用的技巧是def wythoff_game_exact(a, b): 使用整数运算避免浮点精度问题 if a b: a, b b, a n b - a # 计算 floor(n * phi) 的精确值 # phi (1 sqrt(5)) / 2 # floor(n * phi) floor((n n * sqrt(5)) / 2) # 需要精确计算 floor(n * sqrt(5)) sqrt5_n math.isqrt(5 * n * n) # 调整因为isqrt是向下取整 while (sqrt5_n 1) * (sqrt5_n 1) 5 * n * n: sqrt5_n 1 while sqrt5_n * sqrt5_n 5 * n * n: sqrt5_n - 1 expected_a (n sqrt5_n) // 2 return a ! expected_a这段代码用整数平方根来计算⌊n√5⌋然后通过(n ⌊n√5⌋) / 2来得到⌊nφ⌋。因为φ (1 √5) / 2所以nφ (n n√5) / 2。取整的时候需要注意⌊(n n√5) / 2⌋不一定等于(n ⌊n√5⌋) / 2的整数部分需要仔细处理。实际上由于n和n√5的奇偶性这个等式在大多数情况下成立但边界情况需要验证。实操心得Wythoff博弈是我在三个游戏里踩坑最多的一个。第一次写的时候直接用浮点数小数据测试全过一上大数据就WA。后来改成整数运算才稳定。如果你在刷题平台上遇到Wythoff博弈的题目强烈建议用整数运算版本不要图省事用浮点。5. 三大游戏的统一视角与扩展思路5.1 SG函数组合博弈的通用工具前面三个游戏都是单个游戏的胜负判断。但如果一个游戏是由多个子游戏组合而成的呢比如一个游戏里既有Nim的规则又有Bash的规则怎么判断胜负这时候就需要用到SG函数Sprague-Grundy函数。SG函数的定义是一个状态的SG值等于所有它能到达的状态的SG值中最小的非负整数。终止状态的SG值为0。有了SG函数之后组合博弈的胜负判断就变得统一了如果一个游戏由多个子游戏组成每次操作只能在一个子游戏中进行那么整个游戏的SG值等于所有子游戏SG值的异或。如果异或结果非0先手必胜如果为0先手必败。你会发现Nim博弈其实就是SG函数的一个特例每堆石子的SG值就是石子数量整个游戏的SG值就是所有堆石子数量的异或。Bash博弈的SG值则需要对(m 1)取模。Wythoff博弈因为不能拆分成独立的子游戏两堆石子是联动的所以不能直接用SG函数需要单独分析。SG函数是组合博弈论里最核心的工具之一掌握了它很多看起来复杂的博弈问题都能拆解成简单的子问题。5.2 三个游戏的难度递进关系从思维难度上来说这三个游戏构成了一个清晰的递进Bash博弈考察的是周期思维。你需要发现必败态以(m 1)为周期循环出现然后利用这个周期性制定策略。这个思维在很多数学问题里都会用到。Nim博弈考察的是二进制思维。你需要把石子数量看成二进制数用异或运算来捕捉局面的本质特征。这种思维方式在计算机科学里非常重要很多算法问题都涉及二进制位的操作。Wythoff博弈考察的是数学构造思维。你需要发现必败态和黄金分割比之间的联系这需要一定的数学直觉和推导能力。Beatty定理的应用更是把数论和博弈论结合在了一起。我的建议是严格按照这个顺序来学习。先把Bash博弈的余数思维吃透再进入Nim的异或世界最后挑战Wythoff的数学构造。跳着学的话很容易在Wythoff这里卡住。5.3 实际应用场景这三个游戏虽然看起来只是数学游戏但它们的思维方式在实际中是有用的。Bash博弈的周期思维可以用在资源分配问题上。比如你和一个竞争对手轮流从资源池里取资源每次有上限你可以用类似的思路来判断自己是否处于有利位置。Nim博弈的异或思维在编码理论、校验码设计里有直接应用。异或运算的性質使得它非常适合用来检测和纠正错误。Wythoff博弈涉及的Beatty定理在调度问题、序列构造问题里有应用。黄金分割比出现在这里也不是巧合它和自然界里很多最优分割问题都有联系。当然更直接的应用场景是编程竞赛和算法面试。这三个游戏是博弈论类题目的基础很多变体题目都是在它们的基础上加条件、改规则。把基础打牢了遇到变体才不会慌。6. 常见问题与排查技巧实录6.1 三个游戏的判断条件速查表游戏局面表示必败态条件核心运算Bash一堆数量n每次取1到mn % (m 1) 0取模Nim多堆数量piles[]所有堆异或 0异或Wythoff两堆数量a ≤ ba ⌊(b - a) * φ⌋乘法取整这张表建议背下来。做题的时候先判断是哪个游戏然后直接套条件能省很多时间。6.2 常见错误与排查思路错误一把必胜态和必败态搞反。这是最常见的错误。记住必败态是轮到谁谁输必胜态是轮到谁谁赢。判断条件返回True表示先手必胜返回False表示先手必败。写代码的时候变量命名要清晰比如用is_winning而不是result减少混淆。错误二边界条件没处理好。比如n 0的情况比如m 0的情况比如石子堆为空的情况。这些边界在正常题目里可能不会出现但写通用函数的时候一定要考虑。我的习惯是在函数开头加参数校验把非法输入直接排除掉。错误三Wythoff博弈的浮点精度。前面详细说过了这里再强调一次能用整数运算就用整数运算不要依赖浮点数。如果非要用浮点至少加一个epsilon容差并且在小数部分接近0或1的时候特别小心。错误四Misère版本的规则混淆。标准版本是取最后一个赢Misère版本是取最后一个输。两个版本的策略不同尤其是Bash和Nim的Misère版本必败态条件会发生变化。做题的时候一定要先确认是哪个版本。错误五Nim博弈的必胜走法输出。判断胜负很简单但输出具体走法的时候容易出错。关键是要找到那一堆满足p ^ xor_sum p的石子然后取走p - (p ^ xor_sum)个。注意可能有多个满足条件的堆题目可能要求输出任意一个或者特定规则下的一个。6.3 暴力打表验证法不管你推导出了什么规律都建议先用暴力搜索验证小规模的数据。具体做法是写一个递归函数枚举所有可能的操作用记忆化避免重复计算然后打印出所有必败态和你推导的规律对比。这个方法看起来笨但非常有效。我在推导Wythoff博弈的规律时就是先打表打出前20个必败态然后观察差值规律再猜测和黄金分割比的关系最后用Beatty定理验证。整个过程如果没有打表验证很容易推错。暴力搜索的代码框架大概是这样from functools import lru_cache lru_cache(maxsizeNone) def is_winning(state): 判断状态是否为必胜态 state的具体形式取决于游戏规则 for next_state in get_all_moves(state): if not is_winning(next_state): return True return False这个框架对三个游戏都适用只需要根据具体规则实现get_all_moves函数即可。6.4 性能优化建议对于Nim博弈如果堆数很多异或运算是O(n)的已经很快了。但如果题目要求输出所有必胜走法就需要O(n)遍历每一堆总体还是O(n)。对于Wythoff博弈用整数运算的版本是O(log n)的因为isqrt的复杂度比浮点版本稍慢但更稳定。如果n特别大比如10^18级别可能需要用更高效的整数平方根算法。对于Bash博弈O(1)的判断没什么优化空间。如果遇到多个子游戏组合的情况记得用SG函数把每个子游戏的SG值算出来再做异或不要试图直接分析整个游戏。最后分享一个小技巧如果你在比赛中遇到一个博弈题一时看不出是哪个游戏先写暴力搜索打表打出前几十个必败态然后观察规律。大部分博弈题的规律都能从打表中看出来。打表是博弈题最可靠的突破口没有之一。 
长河君 · 2026/10/9 16:29:55 · 阅读 1.2k 组合博弈论三大经典游戏：Bash、Nim与Wythoff博弈原理与实战
博弈论这个词听起来像是经济学课堂上的高深概念但实际上它离我们非常近。只要涉及到两个或多个人做决策、彼此影响结果博弈就发生了。而“三大游戏”——Bash博弈、Nim博弈、Wythoff博弈是组合博弈论里最经典、最常被拿出来讲的三颗明珠。它们看起来只是简单的取石子游戏但背后藏着完整的数学结构必胜态与必败态的划分、SG函数、Beatty定理等等。我第一次接触这三个游戏的时候觉得规则简单到有点无聊但真正动手推导了一遍必胜策略之后才发现这里面的思维方式可以直接迁移到很多现实决策场景中。这篇文章我会把这三个游戏的来龙去脉、核心原理、必胜策略的推导过程、代码实现以及我在实际操作中踩过的坑全部拆开讲清楚。不管你是刚接触博弈论的新手还是想复习一下组合博弈的老手应该都能从里面拿到有用的东西。1. 三大博弈游戏的整体设计与思路拆解1.1 为什么是这三个游戏组合博弈论里有非常多取石子类的游戏但Bash、Nim、Wythoff这三个之所以被反复提及是因为它们构成了一个从简单到复杂的完整阶梯。Bash博弈是最基础的一层一堆石子每次取1到m个谁取最后一个谁赢。它的必胜策略非常直接基本上理解了“余数”这个概念就能掌握。Nim博弈进了一步多堆石子每次可以从任意一堆里取任意多个谁取最后一个谁赢。它的必胜策略需要用到异或运算是二进制思维在博弈论里最漂亮的应用之一。Wythoff博弈则再上一层两堆石子每次可以从一堆里取任意多个或者从两堆里同时取相同数量的石子谁取最后一个谁赢。它的必胜态涉及Beatty定理和黄金分割比是三个游戏里数学味最浓的。这三个游戏放在一起刚好覆盖了组合博弈论里三种不同层次的思维方式余数思维、异或思维、以及数学构造思维。你把这几个吃透了再去看其他变体游戏会发现很多都是在这三个基础上做加减法。1.2 核心概念必胜态与必败态在展开具体游戏之前必须先把这个核心概念说清楚不然后面所有推导都无从谈起。在组合博弈中我们通常做这样的定义一个状态是必败态如果轮到当前玩家行动时无论他怎么走都会把局面交给对手一个必胜态一个状态是必胜态如果存在至少一种走法能让对手面对一个必败态。这个定义是递归的。最简单的终止状态——比如没有石子可取了——通常是必败态因为轮到你时你已经没法行动了按照正常规则你就输了。然后从这个终止状态往回推就能确定所有状态的胜负属性。我习惯用一个生活化的类比来理解把必败态想象成一个“烫手山芋”谁拿到谁倒霉。必胜态就是你手里有一个办法能把这个山芋扔给对方。所以整个博弈的过程就是双方轮流扔山芋谁最后手里拿着山芋谁就输了。注意必胜态和必败态的判断依赖于具体的游戏规则。同一个局面在不同规则下可能是必胜态也可能是必败态。所以每次分析新游戏时第一步永远是明确规则。1.3 从暴力搜索到数学规律对于任何一个组合博弈理论上你都可以用递归加记忆化的方式暴力搜索出每个状态的胜负属性。但暴力搜索的问题是状态空间可能非常大尤其是Nim和Wythoff这种状态数量随石子数增长的游戏。所以真正的思路是先用暴力搜索小规模的状态观察规律然后尝试用数学方式证明这个规律最后得到一个O(1)或O(log n)的判断方法。这个“暴力打表找规律再证明”的流程是我在做这类问题时最常用的方法论。三个游戏的具体规律各不相同但推导路径是一致的。下面我逐个拆解。2. Bash博弈余数思维的最佳入门2.1 规则与基本分析Bash博弈的规则很简单只有一堆石子数量为n。两个人轮流取每次至少取1个最多取m个。取走最后一个石子的人获胜。先看最简单的情况。如果n ≤ m那先手直接一次全部取完先手必胜。这个没什么好说的。如果n m 1呢先手无论取多少个1到m个剩下的石子数量都在1到m之间后手可以一次全部取完。所以n m 1是先手必败态。再往下推。如果n m 2呢先手可以取1个剩下m 1个给后手后手面对的是必败态所以先手必胜。同理n从m 2到2m 1先手都可以通过取适当数量让剩下的石子变成m 1从而获胜。到了n 2m 2先手无论怎么取剩下的数量都在m 2到2m 1之间而这些全是必胜态所以n 2m 2是必败态。规律已经很清楚了必败态是n % (m 1) 0的所有状态。2.2 必胜策略的完整推导为什么是m 1这个周期核心逻辑是这样的如果n能被(m 1)整除那么无论先手取k个1 ≤ k ≤ m剩下的数量n - k一定不能被(m 1)整除因为n是(m 1)的倍数减去一个1到m之间的数之后余数就是(m 1 - k)这个值在1到m之间不为零。然后后手可以取(m 1 - k)个让剩下的石子重新变成(m 1)的倍数。这样每一轮下来后手都能把局面恢复到(m 1)的倍数状态。最终当石子数变成0时刚好是先手面对0因为0也是(m 1)的倍数先手无法行动先手输。反过来如果n不能被(m 1)整除先手只需要取n % (m 1)个石子就能把局面变成(m 1)的倍数交给后手一个必败态。之后先手只需要模仿上面后手的策略每次取(m 1 - k)个就能保证获胜。这个策略的美妙之处在于它的对称性你取多少我就补到m 1。这种“补足”思维在很多博弈问题里都会出现。2.3 代码实现与实操细节Bash博弈的判断代码非常简单一行就够了def bash_game(n, m): 判断Bash博弈先手是否必胜 n: 石子总数 m: 每次最多取的数量 返回True表示先手必胜False表示先手必败 return n % (m 1) ! 0但实际写代码的时候有几个细节需要注意。第一个是边界条件。如果n 0按照规则先手无法行动先手输。n % (m 1) 0返回False正确。如果m 0呢这意味着每次只能取0个游戏永远无法结束。这种退化情况在实际问题中通常不会出现但写通用函数的时候最好加一个参数校验。第二个是如果题目问的是“谁取最后一个谁输”也就是Misère版本那策略会完全不同。Misère Bash博弈的必败态判断会变成n % (m 1) 1当n 1时。这个变体我在实际做题时遇到过好几次每次都要重新推一遍所以建议把两个版本的判断条件都记住。第三个是当m ≥ n时先手直接全取完必胜。这个情况其实已经被n % (m 1) ! 0覆盖了因为如果m ≥ n那m 1 nn % (m 1) n ≠ 0返回True。逻辑上是自洽的。实操心得Bash博弈虽然简单但它是理解“周期性格局”的最佳入口。很多复杂的博弈问题拆到最后都会发现某个子游戏本质上就是一个Bash博弈。所以不要因为它简单就跳过把这个余数思维刻在脑子里后面会反复用到。3. Nim博弈异或运算的经典应用3.1 从两堆到多堆的思维跃迁Nim博弈的规则是有若干堆石子每堆数量任意。两个人轮流操作每次可以从任意一堆中取走任意多个至少1个取走最后一个石子的人获胜。如果只有一堆那和Bash博弈里m无限大的情况一样先手直接全取完就赢了。如果有两堆呢假设两堆数量分别是a和b。如果a b先手取多少后手就在另一堆取同样的数量始终保持两堆相等。最终先手面对两堆都是0的局面先手输。所以两堆相等是必败态。如果a ≠ b呢先手从多的那堆取走|a - b|个让两堆变成相等交给后手一个必败态。所以两堆不等是先手必胜。两堆的情况很直观。但到了三堆、四堆甚至更多堆就没法用“保持相等”这种简单策略了。这时候需要引入一个新的数学工具异或运算。3.2 异或运算的核心原理先简单说一下异或运算XOR。异或的规则是两个二进制位相同则为0不同则为1。比如5 XOR 3101 XOR 011 ------- 110 6异或运算有几个关键性质a XOR a 0a XOR 0 a异或运算满足交换律和结合律。Nim博弈的必胜态判断定理是把所有堆的石子数量做异或运算如果结果不为0先手必胜如果结果为0先手必败。这个定理的证明思路和Bash博弈的余数思维有相似之处。异或结果为0的状态无论你怎么取都会让异或结果变成非0而异或结果非0的状态你总存在一种取法能让异或结果重新变成0。具体来说假设当前所有堆的异或结果是S ≠ 0。设S的最高位1在第k位从低位往高位数的第k位。那么一定存在某一堆石子其第k位也是1因为S的第k位是1说明有奇数堆的第k位是1。设这堆石子数量为x我们把这堆取到x XOR S。因为x XOR S xS的最高位和x的最高位相同异或之后最高位变成0所以结果一定小于x所以这是一个合法操作。操作之后所有堆的异或结果变成S XOR x XOR (x XOR S) S XOR S 0。这就证明了从异或非0的状态总能一步走到异或为0的状态。而异或为0的状态无论取哪一堆的多少个石子都会让异或结果变成非0因为改变了一堆的值异或结果必然改变。3.3 代码实现与策略还原Nim博弈的判断代码同样简洁from functools import reduce def nim_game(piles): 判断Nim博弈先手是否必胜 piles: 每堆石子数量的列表 返回True表示先手必胜False表示先手必败 xor_sum reduce(lambda x, y: x ^ y, piles, 0) return xor_sum ! 0但如果题目要求输出具体的必胜走法就需要多写几步def nim_winning_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这段代码的逻辑是找到一堆石子使得把它取到p XOR xor_sum之后整体异或结果变成0。因为p XOR xor_sum一定小于p前面证明过所以取走的数量就是p - (p XOR xor_sum)。注意Nim博弈可能有多个必胜走法上面的代码只返回找到的第一个。如果题目要求输出所有必胜走法或者特定条件下的走法需要遍历所有堆并收集所有满足条件的操作。3.4 Nim博弈的常见变体Nim博弈有很多变体我在实际中遇到过的主要有这几种Misère Nim取走最后一个石子的人输。这个变体的策略和标准Nim略有不同。如果所有堆的数量都是1那胜负取决于堆数的奇偶性奇数堆先手必败偶数堆先手必胜。如果至少有一堆数量大于1那策略和标准Nim一样用异或判断。这个结论我第一次看到的时候觉得很反直觉后来自己推了几组小数据才确认是对的。限制每次取的数量比如每次最多取m个。这种变体需要对每堆石子数量先对(m 1)取模然后再做异或。本质上就是把Bash博弈的余数思维和Nim的异或思维结合起来了。阶梯Nim石子放在阶梯上每次从某一级取若干石子放到下一级取到地面上的石子的人获胜。这个变体只需要考虑奇数级阶梯上的石子做异或偶数级的不用管。这个结论非常漂亮但证明需要一些技巧。4. Wythoff博弈黄金分割的博弈论呈现4.1 规则与与Nim的区别Wythoff博弈的规则是有两堆石子数量分别为a和b。两个人轮流操作每次可以有两种取法从其中一堆取任意多个至少1个或者从两堆中同时取相同数量的石子至少1个。取走最后一个石子的人获胜。和Nim的区别在于Nim可以从任意一堆取任意多个但不能同时从多堆取Wythoff只能操作两堆但多了一个“同时取相同数量”的选项。这个额外的选项让Wythoff博弈的数学结构比Nim复杂得多。4.2 必败态的规律发现先用暴力搜索打表看看必败态长什么样。假设a ≤ b列出小范围内的必败态ab差值0001213524736104813591561118712208观察这些数据能发现几个规律第一每个必败态的差值b - a是递增的从0开始每次加1。第二每个正整数恰好出现在一个必败态中作为a或b。第三a的值似乎和差值有关。具体来看差值为k的必败态中a的值是前面所有必败态中未出现过的最小正整数。比如差值为1时a 10已经出现过差值为2时a 31和2已经出现过差值为3时a 41、2、3、5已经出现过最小未出现的是4。这个规律可以递归地构造出所有必败态但我们需要一个封闭形式的公式。4.3 Beatty定理与黄金分割Wythoff博弈的必败态有一个非常漂亮的封闭形式涉及Beatty定理和黄金分割比。Beatty定理说的是如果两个正无理数α和β满足1/α 1/β 1那么数列{⌊nα⌋}和{⌊nβ⌋}n 1, 2, 3, ...恰好构成正整数的一个划分也就是说每个正整数恰好出现在其中一个数列中。对于Wythoff博弈取α φ (1 √5) / 2黄金分割比β φ² φ 1。可以验证1/φ 1/φ² 1。那么第n个必败态从n 0开始就是a_n ⌊nφ⌋b_n ⌊nφ²⌋ a_n n验证一下n 1时a ⌊1.618⌋ 1b ⌊2.618⌋ 2对应(1, 2)。n 2时a ⌊3.236⌋ 3b ⌊5.236⌋ 5对应(3, 5)。n 3时a ⌊4.854⌋ 4b ⌊7.854⌋ 7对应(4, 7)。和打表结果完全一致。所以Wythoff博弈的必胜态判断就变成了给定(a, b)且a ≤ b计算n b - a然后检查a是否等于⌊nφ⌋。如果等于就是必败态否则是必胜态。4.4 代码实现与浮点精度问题Wythoff博弈的判断代码看起来简单但有一个很大的坑浮点数精度。import math def wythoff_game(a, b): 判断Wythoff博弈先手是否必胜 a, b: 两堆石子数量 返回True表示先手必胜False表示先手必败 if a b: a, b b, a n b - a phi (1 math.sqrt(5)) / 2 expected_a int(n * phi) return a ! expected_a问题在于当n比较大的时候n * phi的浮点计算结果可能会有误差导致int()截断后的结果偏大或偏小1。比如n 1000000时n * phi ≈ 1618033.9887int()之后是1618033这是对的。但如果某个n使得n * phi的小数部分极其接近1浮点误差可能让它变成整数部分加1导致结果错误。解决方法是使用整数运算来避免浮点误差。可以利用黄金分割比的连分数逼近或者直接用整数平方根来计算。一个常用的技巧是def wythoff_game_exact(a, b): 使用整数运算避免浮点精度问题 if a b: a, b b, a n b - a # 计算 floor(n * phi) 的精确值 # phi (1 sqrt(5)) / 2 # floor(n * phi) floor((n n * sqrt(5)) / 2) # 需要精确计算 floor(n * sqrt(5)) sqrt5_n math.isqrt(5 * n * n) # 调整因为isqrt是向下取整 while (sqrt5_n 1) * (sqrt5_n 1) 5 * n * n: sqrt5_n 1 while sqrt5_n * sqrt5_n 5 * n * n: sqrt5_n - 1 expected_a (n sqrt5_n) // 2 return a ! expected_a这段代码用整数平方根来计算⌊n√5⌋然后通过(n ⌊n√5⌋) / 2来得到⌊nφ⌋。因为φ (1 √5) / 2所以nφ (n n√5) / 2。取整的时候需要注意⌊(n n√5) / 2⌋不一定等于(n ⌊n√5⌋) / 2的整数部分需要仔细处理。实际上由于n和n√5的奇偶性这个等式在大多数情况下成立但边界情况需要验证。实操心得Wythoff博弈是我在三个游戏里踩坑最多的一个。第一次写的时候直接用浮点数小数据测试全过一上大数据就WA。后来改成整数运算才稳定。如果你在刷题平台上遇到Wythoff博弈的题目强烈建议用整数运算版本不要图省事用浮点。5. 三大游戏的统一视角与扩展思路5.1 SG函数组合博弈的通用工具前面三个游戏都是单个游戏的胜负判断。但如果一个游戏是由多个子游戏组合而成的呢比如一个游戏里既有Nim的规则又有Bash的规则怎么判断胜负这时候就需要用到SG函数Sprague-Grundy函数。SG函数的定义是一个状态的SG值等于所有它能到达的状态的SG值中最小的非负整数。终止状态的SG值为0。有了SG函数之后组合博弈的胜负判断就变得统一了如果一个游戏由多个子游戏组成每次操作只能在一个子游戏中进行那么整个游戏的SG值等于所有子游戏SG值的异或。如果异或结果非0先手必胜如果为0先手必败。你会发现Nim博弈其实就是SG函数的一个特例每堆石子的SG值就是石子数量整个游戏的SG值就是所有堆石子数量的异或。Bash博弈的SG值则需要对(m 1)取模。Wythoff博弈因为不能拆分成独立的子游戏两堆石子是联动的所以不能直接用SG函数需要单独分析。SG函数是组合博弈论里最核心的工具之一掌握了它很多看起来复杂的博弈问题都能拆解成简单的子问题。5.2 三个游戏的难度递进关系从思维难度上来说这三个游戏构成了一个清晰的递进Bash博弈考察的是周期思维。你需要发现必败态以(m 1)为周期循环出现然后利用这个周期性制定策略。这个思维在很多数学问题里都会用到。Nim博弈考察的是二进制思维。你需要把石子数量看成二进制数用异或运算来捕捉局面的本质特征。这种思维方式在计算机科学里非常重要很多算法问题都涉及二进制位的操作。Wythoff博弈考察的是数学构造思维。你需要发现必败态和黄金分割比之间的联系这需要一定的数学直觉和推导能力。Beatty定理的应用更是把数论和博弈论结合在了一起。我的建议是严格按照这个顺序来学习。先把Bash博弈的余数思维吃透再进入Nim的异或世界最后挑战Wythoff的数学构造。跳着学的话很容易在Wythoff这里卡住。5.3 实际应用场景这三个游戏虽然看起来只是数学游戏但它们的思维方式在实际中是有用的。Bash博弈的周期思维可以用在资源分配问题上。比如你和一个竞争对手轮流从资源池里取资源每次有上限你可以用类似的思路来判断自己是否处于有利位置。Nim博弈的异或思维在编码理论、校验码设计里有直接应用。异或运算的性質使得它非常适合用来检测和纠正错误。Wythoff博弈涉及的Beatty定理在调度问题、序列构造问题里有应用。黄金分割比出现在这里也不是巧合它和自然界里很多最优分割问题都有联系。当然更直接的应用场景是编程竞赛和算法面试。这三个游戏是博弈论类题目的基础很多变体题目都是在它们的基础上加条件、改规则。把基础打牢了遇到变体才不会慌。6. 常见问题与排查技巧实录6.1 三个游戏的判断条件速查表游戏局面表示必败态条件核心运算Bash一堆数量n每次取1到mn % (m 1) 0取模Nim多堆数量piles[]所有堆异或 0异或Wythoff两堆数量a ≤ ba ⌊(b - a) * φ⌋乘法取整这张表建议背下来。做题的时候先判断是哪个游戏然后直接套条件能省很多时间。6.2 常见错误与排查思路错误一把必胜态和必败态搞反。这是最常见的错误。记住必败态是轮到谁谁输必胜态是轮到谁谁赢。判断条件返回True表示先手必胜返回False表示先手必败。写代码的时候变量命名要清晰比如用is_winning而不是result减少混淆。错误二边界条件没处理好。比如n 0的情况比如m 0的情况比如石子堆为空的情况。这些边界在正常题目里可能不会出现但写通用函数的时候一定要考虑。我的习惯是在函数开头加参数校验把非法输入直接排除掉。错误三Wythoff博弈的浮点精度。前面详细说过了这里再强调一次能用整数运算就用整数运算不要依赖浮点数。如果非要用浮点至少加一个epsilon容差并且在小数部分接近0或1的时候特别小心。错误四Misère版本的规则混淆。标准版本是取最后一个赢Misère版本是取最后一个输。两个版本的策略不同尤其是Bash和Nim的Misère版本必败态条件会发生变化。做题的时候一定要先确认是哪个版本。错误五Nim博弈的必胜走法输出。判断胜负很简单但输出具体走法的时候容易出错。关键是要找到那一堆满足p ^ xor_sum p的石子然后取走p - (p ^ xor_sum)个。注意可能有多个满足条件的堆题目可能要求输出任意一个或者特定规则下的一个。6.3 暴力打表验证法不管你推导出了什么规律都建议先用暴力搜索验证小规模的数据。具体做法是写一个递归函数枚举所有可能的操作用记忆化避免重复计算然后打印出所有必败态和你推导的规律对比。这个方法看起来笨但非常有效。我在推导Wythoff博弈的规律时就是先打表打出前20个必败态然后观察差值规律再猜测和黄金分割比的关系最后用Beatty定理验证。整个过程如果没有打表验证很容易推错。暴力搜索的代码框架大概是这样from functools import lru_cache lru_cache(maxsizeNone) def is_winning(state): 判断状态是否为必胜态 state的具体形式取决于游戏规则 for next_state in get_all_moves(state): if not is_winning(next_state): return True return False这个框架对三个游戏都适用只需要根据具体规则实现get_all_moves函数即可。6.4 性能优化建议对于Nim博弈如果堆数很多异或运算是O(n)的已经很快了。但如果题目要求输出所有必胜走法就需要O(n)遍历每一堆总体还是O(n)。对于Wythoff博弈用整数运算的版本是O(log n)的因为isqrt的复杂度比浮点版本稍慢但更稳定。如果n特别大比如10^18级别可能需要用更高效的整数平方根算法。对于Bash博弈O(1)的判断没什么优化空间。如果遇到多个子游戏组合的情况记得用SG函数把每个子游戏的SG值算出来再做异或不要试图直接分析整个游戏。最后分享一个小技巧如果你在比赛中遇到一个博弈题一时看不出是哪个游戏先写暴力搜索打表打出前几十个必败态然后观察规律。大部分博弈题的规律都能从打表中看出来。打表是博弈题最可靠的突破口没有之一。