小时候玩抓石子谁拿到最后一颗谁赢这个简单的游戏藏着博弈论里最经典的一类问题。后来刷算法题、打竞赛发现“取石子游戏”几乎是每个学博弈论的人绕不开的第一课从最简单的巴什博弈到带黄金分割的威佐夫博弈再到用异或一把梭的尼姆博弈它们串起来的不仅是一堆公式更是一整套“必胜/必败局面”的分析框架。这篇文章想把这些经典模型彻底讲透每条结论都带着推导和代码顺便把我自己踩过的坑也一并交代了。适合正在学算法的大学生、准备竞赛的选手以及面试前临时抱佛脚的工程师。看完你不仅能判断“先手能不能赢”还能在考场上遇到变形题时自己推出规律而不是干瞪眼。1. 内容整体设计与思路拆解取石子游戏之所以值得花一整篇文章来讲是因为它背后是一个完整的数学分支——组合博弈论。别被这个名词吓到它在算法题里落地时核心就一句话把一个游戏局面抽象成“必胜态”或“必败态”然后找到判断它们的规律。1.1 为什么说取石子是博弈论的“hello world”先看一个最朴素的场景桌上有一堆石子两个人轮流取每次至少取1颗最多取m颗取走最后一颗的人获胜。这种规则简单到不用讲规则但它蕴含了博弈论里最核心的思想——逆向推理。假设你面临某个局面如果你走完一步后把所有可能交给对手的局面都变成了“对手必败”那当前局面对你就是必胜的。反过来只要存在一个走法能让对手面临必败局面你就该走那一步。这个思想几乎适用于所有公平组合游戏两个玩家信息完全公开、无随机、无平局、有限步会结束的游戏。取石子游戏就是这类游戏最典型的代表。所以把它吃透等于把博弈论的地基打牢了。后面再遇到棋盘类、图论类博弈题你至少知道该从哪个方向思考。1.2 三大经典模型的分工与边界巴什博弈、威佐夫博弈、尼姆博弈这三兄弟看起来都是“取石子”但规则差异决定了它们分析工具的完全不同。巴什博弈只有一堆石子每次取[1, m]颗。结论极简单取模就行。威佐夫博弈有两堆石子你可以从一堆里取任意数量或者从两堆里同时取相同数量。这里冒出黄金分割比结论相当反直觉。尼姆博弈有若干堆石子每次只能从一堆里取任意数量至少1颗。用异或运算一行代码搞定是三者中“算法味”最浓的。从难度上说巴什是入门威佐夫是数学美感尼姆是抽象思维。三者不是互相替代的关系而是递进关系。巴什让你理解“剩余量”这个概念威佐夫让你接受“奇异局势”这种特殊状态尼姆则把所有局面压缩成一个异或值。1.3 建议的学习路径我在带新人时建议的顺序是先死磕巴什博弈把“必败态/必胜态”的推导过程亲手做一遍再去看威佐夫博弈的奇异局势最后学尼姆博弈的异或判定。等三套东西都会了再回头学SG定理把三者统一到一个框架里看。不要一上来就背代码。代码是最不值钱的部分真正的价值在于“你是怎么想到这个解法的”。比如尼姆博弈为什么是异或而不是求和如果你能自己推导出来这个知识点就永远不会忘。2. 巴什博弈一堆石子与模运算这是所有取石子问题里最基础的一个也是面试里最容易出现的变体。规则再强调一遍一堆石子总数n两人轮流取每次取1到m颗取走最后一颗的赢。2.1 先拿小数据试出感觉用手算一下n10、m3的情况。一共有10颗石子每次最多取3颗。先手有哪些选择取1颗剩9颗取2颗剩8颗取3颗剩7颗试着倒推。剩0颗时游戏结束轮到谁谁输。剩1、2、3颗时当前选手可以一次全取走所以这三个局面都是必胜态。剩4颗时呢你取1颗剩3取2颗剩2取3颗剩1无论怎么取都会给对手留下1到3颗的必胜局面所以剩4颗是必败态。剩5、6、7颗时你可以分别取1、2、3颗把局面丢给对手的“4颗”所以是必胜态。剩8颗时又陷入无论怎么取都会留给对手5到7颗的困境必败。看到这里规律已经很明显了4、8、12……这些4的倍数都是必败态。注意这里m3所以“4”其实是m1。必败态就是n能被(m1)整除的情况。2.2 核心结论的严谨推导为什么偏偏是m1这个数因为一轮游戏里无论对手取多少颗你都可以控制一轮总共取走(m1)颗。假设对手取k颗1≤k≤m你只需要取(m1-k)颗就能保证在一轮结束之后总数恰好减少m1颗。如果你面对的石子数是m1的整数倍不管对手怎么取你都能用这个方法保持“剩下的是m1的倍数”这个状态一步一步把它压到0最终把最后一颗留给对手也就是对手无石可取。这个策略叫什么控制节奏。生活里也很常见你没法预测别人怎么走但你可以保证每次两人合计稳定消耗固定数量。就这么一个简单的思路构成了巴什博弈的全部。结论如果 n % (m1) 0先手必败否则先手必胜。必胜时先手第一步应该取 n % (m1) 颗。注意这里的模运算结果刚好是“剩余量”。如果余数为0表示你已经处于必败态但仍要按规则取一颗理论上在双方都最优的前提下这盘已经输了。2.3 代码实现与变种提醒代码短到没朋友def bash_game(n: int, m: int) - bool: # 返回 True 表示先手必胜 return n % (m 1) ! 0 def first_move(n: int, m: int) - int: # 先手第一步应取的石子数若返回 0 表示必败 take n % (m 1) return take if take ! 0 else -1如果你遇到“取走最后一颗的人输”这种反过来的规则处理方法也不复杂把局面看成还没取时只剩1颗的情形稍微改一下判断条件就行了。我在实际题目里的做法是直接把规则转换成“取到倒数第二颗为胜”然后套用原公式。转换的时候注意边界就行别在原代码上硬改。提示很多变种题不会明说“每次取1到m颗”而是说“每次取不超过当前数量一半”之类这类情况通常需要你重新推算必败态分布别硬套巴什公式。3. 威佐夫博弈两堆石子里的黄金分割如果说巴什博弈是开胃菜威佐夫博弈就是一道主菜了。它的规则变成了两堆石子每次你可以在任意一堆里取任意数量也可以在两堆里同时取走相同数量的石子目标同样是拿走最后一颗的人获胜。3.1 奇异局势那些先手必败的局面两堆石子状态可以用(a, b)表示不妨设a≤b。先手必败的局面叫奇异局势。前几个奇异局势是啥手动枚举一下就能发现(0, 0)已经没石子了轮到谁谁输。(1, 2)尝试各种取法先手都赢不了。(3, 5)也是奇异局势。(4, 7)继续验证确实先手必败。(6, 10)、(8, 13)、(9, 15)……看到这一串有点懵对吧别急观察(a, b)的差值0, 1, 2, 3, 4, 5……还真就是递增的。而且每个正整数恰好出现一次或者作为a出现或者作为b出现。这种数列结构正是Beatty序列的特征。3.2 黄金分割比是怎么冒出来的对于第k个奇异局势k从0开始有a_k floor(k * φ)b_k a_k k其中 φ (1 √5) / 2 ≈ 1.618就是黄金分割比。验证一下k0时a0, b0k1时afloor(1.618)1, b2k2时afloor(3.236)3, b5k3时afloor(4.854)4, b7。全对上了。为什么是黄金分割比这涉及到Beatty定理如果1/α 1/β 1那么 floor(nα) 和 floor(nβ) 这两个序列合起来恰好不重复不遗漏地覆盖所有正整数。威佐夫博弈的奇异局势恰好满足这个结构α取φβ取φ1于是黄金分割就出现了。这不是人为设计的巧合而是博弈局面对应了一种自然的“公平分割”。3.3 判定方法与代码实战给定局面(a, b)假设a≤b怎么判是不是奇异局势思路是反推k因为 b - a k所以先算 k b - a然后验证 a 是否等于 floor(k * φ)。import math def wythoff_game(a: int, b: int) - bool: if a b: a, b b, a k b - a phi (1 math.sqrt(5)) / 2 a_k int(k * phi) return a a_k # True 表示先手必败这里有一个精度的坑当k特别大时浮动数的乘法可能带来误差。竞赛里的常见做法是用“k * φ 的整数部分”配合一个极小的误差修正或者直接用高精度整数运算来实现黄金分割比逼近算法但我在普通面试题和大部分竞赛题里直接用浮点数判定都够用。注意威佐夫博弈里两堆石子堆数固定为2别用异或那套暴力解法。虽然也能算但复杂度高得多而且容易出错。4. 尼姆博弈异或运算的魔法终于到了最经典、最常考的尼姆博弈了。规则有若干堆石子你每次只能从一堆里取任意数量至少1颗可以一次全取走取走最后一颗的人获胜。4.1 一个反直觉的核心公式尼姆博弈的结论特别漂亮把每堆石子数都转成二进制然后全部异或起来如果结果等于0则先手必败否则先手必胜。举个例子。三堆石子数量分别是3、4、5。3的二进制是0114是1005是101异或结果是011 ^ 100 ^ 101 010不等于0所以先手必胜。如果换成2、3、52是0103是0115是101异或结果是010 ^ 011 ^ 101 100也不等于0。如果三堆是1、2、31是0012是0103是011异或结果是000那就是先手必败。这个结论反直觉的地方在于它根本不管石子总数也不管哪一堆最大只看二进制逐位异或的结果。我第一次学的时候死活想不明白为什么异或能代表“胜负”。4.2 为什么异或和为0就必败来手动推逻辑。记所有堆石子数的异或结果为X。如果X0当前选手无论怎么走都会把一个异或值非0的局面交给对手。为什么因为你只能从一堆里取假设你从第i堆取了若干颗第i堆的数量从a_i变成了a_i而其他堆不变。新局面的异或结果Y X ^ a_i ^ a_i 0 ^ a_i ^ a_i a_i ^ a_i。因为a_i和a_i不相等你确实取走了一些石子所以a_i ^ a_i一定非0。于是你再怎么操作都会给对手一个X≠0的局面。反方向如果X≠0当前选手一定可以找到一堆石子通过取走适量数量让新的异或结果变成0。具体做法是找到X的最高位1在所有堆中找一个在这位上也是1的堆必然存在否则X这位不可能是1假设这堆数量为a你把它变成 a a ^ X。由于X的最高位是1而a这位也是1所以异或后这一位变成0a一定小于a也就是说“从a里取走a - a颗”是合法的。操作之后新异或结果等于X ^ a ^ a X ^ a ^ (a ^ X) 0。这就是尼姆博弈的全部秘密。X0是必败态X≠0是必胜态而且必胜态下怎么走都有明确的构造方式。4.3 构造必胜走法写代码时不仅要判断胜负有时还要输出具体走法这也是常见题型。def nim_win(stones): x 0 for s in stones: x ^ s if x 0: return False, None for i, s in enumerate(stones): target s ^ x if target s: return True, (i, s - target) # 从第i堆取走 s-target 颗 return False, None这个循环里找到第一个满足 target s 的堆就行。因为根据上面的推导这样的堆至少存在一个。target表示这堆变成多少颗s - target就是取走的数量。4.4 边界情况与常见变形尼姆博弈最经典的变形是“取走最后一颗的人输”也就是反尼姆miseré Nim。这个变形的判定稍微复杂一点。结论是当所有堆都是1颗时规则反转否则判断方式还是看异或和是否为0。我实际做题时遇到这种变形会先判断“是否全为1”这个特殊情况再走常规逻辑否则容易在边界上翻车。还有一个常见的坑石子堆数很多数量很大直接用Python的整数完全没问题但在C里要注意用long long别让异或运算中途溢出。5. SG定理把经典模型缝起来的万能框架学会了巴什、威佐夫、尼姆很多人就开始到处套公式了。但真正的竞赛题往往不会这么善良它会把取石子规则改得稀奇古怪比如“每次只能取质数颗”“每次取完必须分成两堆”“一轮可以取多个堆”……这些花式变形直接套上面的结论全都会碰壁。这时候就需要一个更底层的工具——SG定理。5.1 从具体状态到图论模型任何公平组合游戏都可以抽象成一张有向无环图节点是局面边表示一步合法操作。比如巴什博弈在n5、m2时5号局面可以走到4、3两个局面4号局面可以走到3、2以此类推。游戏过程就是沿着有向边从初始节点走到没有出边的节点。这种抽象有什么用它让我们不再关心游戏的具体规则只关心“局面可达哪些局面”进而就能定义SG函数。5.2 SG函数与mex运算定义一个函数g(x)表示局面x的SG值如果局面x没有合法后继g(x) 0。否则g(x) mex({ g(y) | x可以一步走到y })。mex就是“最小排斥值”即集合里没出现的最小非负整数。比如一个局面的后继SG值是{0, 1, 3}那它的SG值就是2。为什么SG0代表必败因为0表示它不能走到任何SG值为0的后继否则0就在集合里了。也就是说位于SG0的局面当前选手无论怎么走都会把局面交给SG≠0的对手。而SG≠0的局面由于mex的定义它必然存在一个后继SG0当前选手可以主动走到那个局面。这一进一出就复刻了我们在尼姆博弈里“X0必败、X≠0必胜”的整套逻辑。5.3 多个独立子游戏的组合异或登场SG定理最漂亮的地方在于如果一个游戏由多个相互独立的子游戏组成比如尼姆博弈里的每一堆石子都算一个子游戏那整个游戏的SG值等于各个子游戏SG值的异或和。这东西叫Sprague-Grundy定理。它把“分散的”游戏重新统一到了尼姆博弈的框架下——只要你会算单个局面的SG组合局面不过是做一次异或。尼姆博弈只是SG定理的一个特例一堆数量为a的石子规则是取1到a颗它的SG值算出来恰好等于a。所以多堆尼姆“异或所有堆石子数”的结论本质上是每个子游戏SGa_i再异或起来的结果没有任何魔法。5.4 记忆化搜索理论落地怎么写SG函数的代码通常用记忆化搜索实现因为一个局面的后继局面集合往往不大但局面总数可能很多。def compute_sg(x, memo, moves_func): if x in memo: return memo[x] reachable set() for y in moves_func(x): # 所有合法后继局面 reachable.add(compute_sg(y, memo, moves_func)) g 0 while g in reachable: g 1 memo[x] g return g这个写法有几个注意点。第一memo必须共享否则每个局面都从头算复杂度直接爆炸。第二moves_func要写得快如果后继状态太多搜索树会很大这时你需要先分析局面空间的大小。第三递归深度在极端情况下可能超过Python默认的递归限制建议提前sys.setrecursionlimit(1000000)或者把搜索改成迭代。注意SG定理只适用于“公平组合游戏”。如果两个玩家的可选操作不同或者存在隐藏信息SG定理直接失效别硬套。6. 常见问题与实战避坑实录写到这里把理论都过完了。但真正上考场、上机的时候还有一堆实际问题。我把自己踩过的坑集中整理一下当成速查手册用。6.1 三种经典博弈快速区分表特征巴什博弈威佐夫博弈尼姆博弈石子堆数1堆2堆多堆每次取法取1到m颗一堆取任意 或 两堆取相同数量单堆取任意数量判定方法n % (m1)差值与黄金分割比所有堆异或必败条件n是m1的倍数a floor((b-a)*φ)异或和为0代码复杂度O(1)O(1)O(堆数)这张表可以帮你快速定位题目类型但比表格更重要的一件事是判断“这题到底属于哪一类”。我的经验是先看有几堆石子再看取法限制。如果只有一堆且有上限巴什两堆且可以同取相同数量威佐夫多堆且单堆随便取尼姆。如果取法里有奇怪的限制那大概率要上SG函数。6.2 数据范围大时最容易翻的跟头竞赛题的数据范围经常是n ≤ 10^18m ≤ 10^9这种量级。这时候巴什博弈依然O(1)没问题威佐夫博弈的浮点数精度就会开始让人头疼。我实测过在k值大约超过10^12时直接用double计算floor(k * φ)有可能差1导致判断错误。解决办法有两个。一是用更高精度的浮点运算但治标不治本。二是用整数逼近因为φ的连分数表示是[1; 1, 1, 1, ...]你可以用斐波那契数列的相邻项比值来逼近黄金分割比然后通过整数乘法计算a_k。斐波那契数到第80项就超过10^16了覆盖绝大多数竞赛数据范围。还有一个更隐蔽的坑当局面数量很大时直接对每个局面算SG函数会超时。这时候要利用SG函数的周期性。很多变种游戏的SG值会从某个位置开始循环你可以先打表1000项然后肉眼找循环节再把大局面直接映射到循环节里。这个技巧我用了很多次屡试不爽。6.3 综合例题把流程完整走一遍来一道我自己编的变形题有两堆石子数量分别是a和b每次你可以从任意一堆取任意数量也可以从两堆中分别取x和y颗但要求|x - y| ≤ 1。问先手是否必胜。这题既不是威佐夫它允许同时取不同数量也不是尼姆它有同取约束没法直接套现成公式。我的分析思路是这样的第一步确认它是否公平组合游戏玩家操作完全对称无随机有限步是。所以可以用SG定理。第二步把局面看成二元组(a, b)。如果a、b太大直接搜不现实所以先打小表观察规律。对a和b从0到20枚举计算SG值。第三步观察SG为0的状态分布。很快能发现必败态集中在对角线附近某个窄带上而且看起来有周期结构。进一步分析会发现这个游戏其实就是威佐夫博弈的“近亲”奇异局势的差分序列变成了一个更复杂的递归——如果硬要通项可以借助Beatty序列推广但竞赛里更常见的做法是直接用数学归纳证明一个判定式。第四步证明或验证判定式后把它写成O(1)的判定代码。这四步流程是我做博弈类题目最通用的套路。拿到题别急着套公式先判断类型打表找规律再证明或反推公式最后代码收尾。顺序反了大概率会写出一个“看起来对但超时”的解。6.4 面试和竞赛现场的一些实操经验面试里博弈论题通常不会太偏巴什和尼姆出现的概率最高。我建议你把这两个模型的推导背得滚瓜烂熟做到随手就能解释“为什么取余”“为什么异或”。面试官更看重的是你能不能讲清楚思路而不是默写代码。竞赛里反而更容易遇到SG函数。建议提前准备一份模板包括记忆化搜索的写法、周期打表找循环节的辅助函数。考试时能少花10分钟在模板上就能多10分钟想核心逻辑。还有一个容易被忽略的点很多博弈题要求输出“第一步怎么走”。这时候光判断胜负不够还得会构造走法。巴什博弈构造方式是取余数尼姆博弈构造方式是找target s的堆威佐夫博弈的构造稍微复杂通常需要二分找k。把这些构造代码提前准备好能省很多时间。
