小时候玩抓石子，谁拿到最后一颗谁赢，这个简单的游戏藏着博弈论里最经典的一类问题。后来刷算法题、打竞赛，发现“取石子游戏”几乎是每个学博弈论的人绕不开的第一课：从最简单的巴什博弈，到带黄金分割的威佐夫博弈，再到用异或一把梭的尼姆博弈，它们串起来的不仅是一堆公式，更是一整套“必胜/必败局面”的分析框架。
这篇文章想把这些经典模型彻底讲透，每条结论都带着推导和代码，顺便把我自己踩过的坑也一并交代了。适合正在学算法的大学生、准备竞赛的选手，以及面试前临时抱佛脚的工程师。看完你不仅能判断“先手能不能赢”，还能在考场上遇到变形题时，自己推出规律，而不是干瞪眼。
1. 内容整体设计与思路拆解
取石子游戏之所以值得花一整篇文章来讲，是因为它背后是一个完整的数学分支——组合博弈论。别被这个名词吓到，它在算法题里落地时，核心就一句话：把一个游戏局面抽象成“必胜态”或“必败态”，然后找到判断它们的规律。
1.1 为什么说取石子是博弈论的“hello world”
先看一个最朴素的场景：桌上有一堆石子，两个人轮流取，每次至少取1颗，最多取m颗，取走最后一颗的人获胜。
这种规则简单到不用讲规则，但它蕴含了博弈论里最核心的思想——逆向推理。假设你面临某个局面，如果你走完一步后，把所有可能交给对手的局面都变成了“对手必败”，那当前局面对你就是必胜的。反过来，只要存在一个走法能让对手面临必败局面，你就该走那一步。
这个思想几乎适用于所有公平组合游戏（两个玩家信息完全公开、无随机、无平局、有限步会结束的游戏）。取石子游戏就是这类游戏最典型的代表。所以把它吃透，等于把博弈论的地基打牢了。后面再遇到棋盘类、图论类博弈题，你至少知道该从哪个方向思考。
1.2 三大经典模型的分工与边界
巴什博弈、威佐夫博弈、尼姆博弈，这三兄弟看起来都是“取石子”，但规则差异决定了它们分析工具的完全不同。
- 巴什博弈：只有一堆石子，每次取[1, m]颗。结论极简单，取模就行。
- 威佐夫博弈：有两堆石子，你可以从一堆里取任意数量，或者从两堆里同时取相同数量。这里冒出黄金分割比，结论相当反直觉。
- 尼姆博弈：有若干堆石子，每次只能从一堆里取任意数量（至少1颗）。用异或运算一行代码搞定，是三者中“算法味”最浓的。
从难度上说，巴什是入门，威佐夫是数学美感，尼姆是抽象思维。三者不是互相替代的关系，而是递进关系。巴什让你理解“剩余量”这个概念，威佐夫让你接受“奇异局势”这种特殊状态，尼姆则把所有局面压缩成一个异或值。
1.3 建议的学习路径
我在带新人时，建议的顺序是：先死磕巴什博弈，把“必败态/必胜态”的推导过程亲手做一遍，再去看威佐夫博弈的奇异局势，最后学尼姆博弈的异或判定。等三套东西都会了，再回头学SG定理，把三者统一到一个框架里看。
不要一上来就背代码。代码是最不值钱的部分，真正的价值在于“你是怎么想到这个解法的”。比如尼姆博弈为什么是异或而不是求和？如果你能自己推导出来，这个知识点就永远不会忘。
2. 巴什博弈：一堆石子与模运算
这是所有取石子问题里最基础的一个，也是面试里最容易出现的变体。规则再强调一遍：一堆石子总数n，两人轮流取，每次取1到m颗，取走最后一颗的赢。
2.1 先拿小数据试出感觉
用手算一下n=10、m=3的情况。一共有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的倍数都是必败态。注意这里m=3，所以“4”其实是m+1。必败态就是n能被(m+1)整除的情况。
2.2 核心结论的严谨推导
为什么偏偏是m+1这个数？因为一轮游戏里，无论对手取多少颗，你都可以控制一轮总共取走(m+1)颗。
假设对手取k颗（1≤k≤m），你只需要取(m+1-k)颗，就能保证在一轮结束之后，总数恰好减少m+1颗。如果你面对的石子数是m+1的整数倍，不管对手怎么取，你都能用这个方法保持“剩下的是m+1的倍数”这个状态，一步一步把它压到0，最终把最后一颗留给对手（也就是对手无石可取）。
这个策略叫什么？控制节奏。生活里也很常见：你没法预测别人怎么走，但你可以保证每次两人合计稳定消耗固定数量。就这么一个简单的思路，构成了巴什博弈的全部。
结论：如果 n % (m+1) == 0，先手必败；否则先手必胜。必胜时，先手第一步应该取 n % (m+1) 颗。
注意，这里的模运算结果刚好是“剩余量”。如果余数为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，就是黄金分割比。
验证一下：k=0时，a=0, b=0；k=1时，a=floor(1.618)=1, b=2；k=2时，a=floor(3.236)=3, b=5；k=3时，a=floor(4.854)=4, b=7。全对上了。
为什么是黄金分割比？这涉及到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的二进制是011，4是100，5是101，异或结果是011 ^ 100 ^ 101 = 010，不等于0，所以先手必胜。如果换成2、3、5，2是010，3是011，5是101，异或结果是010 ^ 011 ^ 101 = 100，也不等于0。如果三堆是1、2、3，1是001，2是010，3是011，异或结果是000，那就是先手必败。
这个结论反直觉的地方在于：它根本不管石子总数，也不管哪一堆最大，只看二进制逐位异或的结果。我第一次学的时候，死活想不明白为什么异或能代表“胜负”。
4.2 为什么异或和为0就必败
来手动推逻辑。记所有堆石子数的异或结果为X。
如果X=0，当前选手无论怎么走，都会把一个异或值非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，所以异或后这一位变成0，a'一定小于a，也就是说“从a里取走a - a'颗”是合法的。操作之后，新异或结果等于X ^ a ^ a' = X ^ a ^ (a ^ X) = 0。
这就是尼姆博弈的全部秘密。X=0是必败态，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 从具体状态到图论模型
任何公平组合游戏，都可以抽象成一张有向无环图：节点是局面，边表示一步合法操作。比如巴什博弈在n=5、m=2时，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。
为什么SG=0代表必败？因为0表示它不能走到任何SG值为0的后继（否则0就在集合里了）。也就是说，位于SG=0的局面，当前选手无论怎么走，都会把局面交给SG≠0的对手。而SG≠0的局面，由于mex的定义，它必然存在一个后继SG=0，当前选手可以主动走到那个局面。这一进一出，就复刻了我们在尼姆博弈里“X=0必败、X≠0必胜”的整套逻辑。
5.3 多个独立子游戏的组合：异或登场
SG定理最漂亮的地方在于：如果一个游戏由多个相互独立的子游戏组成，比如尼姆博弈里的每一堆石子都算一个子游戏，那整个游戏的SG值等于各个子游戏SG值的异或和。
这东西叫Sprague-Grundy定理。它把“分散的”游戏重新统一到了尼姆博弈的框架下——只要你会算单个局面的SG，组合局面不过是做一次异或。
尼姆博弈只是SG定理的一个特例：一堆数量为a的石子，规则是取1到a颗，它的SG值算出来恰好等于a。所以多堆尼姆“异或所有堆石子数”的结论，本质上是每个子游戏SG=a_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 % (m+1) | 差值与黄金分割比 | 所有堆异或 |
| 必败条件 | n是m+1的倍数 | a == floor((b-a)*φ) | 异或和为0 |
| 代码复杂度 | O(1) | O(1) | O(堆数) |
这张表可以帮你快速定位题目类型，但比表格更重要的一件事，是判断“这题到底属于哪一类”。我的经验是：先看有几堆石子，再看取法限制。如果只有一堆且有上限，巴什；两堆且可以同取相同数量，威佐夫；多堆且单堆随便取，尼姆。如果取法里有奇怪的限制，那大概率要上SG函数。
6.2 数据范围大时最容易翻的跟头
竞赛题的数据范围经常是n ≤ 10^18，m ≤ 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。把这些构造代码提前准备好，能省很多时间。
