1. 为什么博弈论是算法竞赛里最“反直觉”的一类题刚接触算法竞赛那会儿我对博弈论题目的印象就两个字玄学。明明规则简单到用一句话就能说清——两个人轮流取石子谁取到最后一个谁赢——但真到写代码的时候要么是状态推不出来要么是推出来了却不知道怎么优化要么是看了题解之后恍然大悟、过两天再遇到同类题又完全没思路。后来打得多了才慢慢意识到博弈论不是靠灵光一现它背后有一套非常严密的数学结构只要把这套结构吃透绝大多数竞赛博弈题都能归到有限的几个模型里。这篇总结就是把我这些年刷博弈论题踩过的坑、总结出的模型、以及每个结论背后的证明推导完整地梳理一遍。核心关键词包括Nim博弈、SG函数、Sprague-Grundy定理、P/N状态、反Nim、威佐夫博弈、巴什博弈等。内容会从最基础的必胜必败态定义讲起一路推到SG定理的完整证明再到各种变形题的拆解思路。适合已经会写基础搜索、但对博弈论一直似懂非懂的竞赛选手也适合想系统补一下这部分知识的朋友。我不会只丢结论给你每个结论我都会尽量把“为什么是这样”讲清楚因为博弈论这东西你不理解证明遇到变形题就是抓瞎。2. 从零建立博弈论的核心概念体系2.1 公平组合游戏的定义与适用范围博弈论题目在算法竞赛里绝大多数属于公平组合游戏Impartial Combinatorial Game简称ICG。这个名词听起来唬人但拆开看就三个条件第一两个玩家轮流操作操作规则完全一样不存在“你能这么走但我不能”的情况第二游戏状态有限不存在无限循环或者循环可以被判定为平局第三无法操作的一方判负也就是通常说的“不能走的人输”。为什么先强调这个定义因为很多新手拿到一道博弈题上来就开始推状态结果推了半天发现这游戏根本不是公平组合游戏——比如有的题里两个玩家能做的事不一样那就不适用Nim和SG那一套得用别的方法比如对抗搜索或者策略分析。所以判断一道题能不能用SG定理第一步就是确认它是不是ICG。我个人的经验是只要题目里出现“两个人轮流”“规则相同”“不能操作者输”这三个特征基本就可以往ICG方向靠。2.2 P状态与N状态博弈论的最小分析单元任何ICG的每个状态都可以被标记为两种之一P状态Previous player wins即先手必败和N状态Next player wins即先手必胜。这两个概念是整个博弈论分析的基石。判定规则非常简洁如果一个状态没有任何合法操作终端状态那当前玩家无法行动判负所以它是P状态。如果一个状态存在至少一个合法操作能到达P状态那当前玩家就可以走到那个P状态让对手面对必败局面所以它是N状态。如果一个状态的所有合法操作都只能到达N状态那无论怎么走都会把必胜局面交给对手所以它是P状态。这三条规则其实是递归定义的从终端状态往回推可以确定所有状态的P/N属性。我习惯把它理解成“P状态是坑谁面对谁输N状态是安全区谁面对谁赢”。这个理解虽然粗糙但在做题时非常管用——你只需要判断当前状态能不能一步走到一个“坑”里就行。注意P/N状态的递归判定在状态空间小的时候可以直接用记忆化搜索实现但状态空间一大就必须找规律或者用SG定理。这是后面所有内容要解决的问题。2.3 用P/N状态分析一个最简单的例子拿最经典的取石子游戏举例一堆n个石子每次可以取1到3个取到最后一个的人赢。我们来手动推一下P/N状态。n0时无法操作P状态。n1,2,3时可以一次取完走到n0这个P状态所以都是N状态。n4时无论取1、2还是3都会分别到达n3,2,1全是N状态所以n4是P状态。n5,6,7时可以分别取到n4所以是N状态。n8时又只能到达N状态所以是P状态。规律很明显n是4的倍数时是P状态否则是N状态。这个规律背后的逻辑是“每轮两人合计可以控制取走4个”先手面对4的倍数时无论他取几个后手都能补到4最终先手面对0个石子输掉。这就是巴什博弈的核心思想后面还会详细展开。3. Nim博弈从结论到证明的完整推导3.1 Nim博弈的规则与结论Nim博弈是ICG里最经典、最重要的模型。规则是有若干堆石子每堆有若干个两人轮流从任意一堆中取走任意正数个石子至少取一个取到最后一个石子的人赢。结论非常简洁把所有堆的石子数做异或运算XOR如果结果非零先手必胜如果结果为零先手必败。我第一次看到这个结论的时候是完全懵的——为什么是异或异或这个运算跟取石子有什么关系后来看了证明才明白这个结论不是拍脑袋想出来的而是严格从P/N状态推导出来的。下面我把证明完整走一遍。3.2 Nim博弈结论的严格证明设所有堆石子数的异或和为S。我们证明两个命题命题一S0的状态是P状态。首先终端状态所有堆都是0显然S0且是P状态。现在假设某个S0的状态存在合法操作玩家从第i堆取走k个石子使第i堆从a_i变成a_i‘a_i’ a_i。由于操作前S0即a_1 XOR a_2 XOR ... XOR a_n 0操作后异或和变为S‘ S XOR a_i XOR a_i’ a_i XOR a_i‘。因为a_i ≠ a_i’所以a_i XOR a_i‘ ≠ 0即S’ ≠ 0。这说明从S0的状态出发任何操作都会到达S≠0的状态。命题二S≠0的状态是N状态。我们需要证明从任意S≠0的状态都存在一个合法操作能到达S0的状态。设S的最高位最左边的1在第p位。因为S≠0所以至少存在一堆石子a_i它的第p位也是1否则所有堆的第p位都是0异或结果的第p位不可能是1。我们令a_i‘ a_i XOR S。由于a_i的第p位是1S的第p位也是1异或后第p位变成0而更高位不变所以a_i’ a_i这是一个合法操作从第i堆取走a_i - a_i‘个石子。操作后新的异或和 S XOR a_i XOR a_i’ S XOR a_i XOR (a_i XOR S) 0。两个命题合起来就证明了S0是P状态S≠0是N状态。这个证明的精妙之处在于它同时给出了“怎么走”的构造方法——找到异或和最高位对应的那堆把它变成a_i XOR S即可。3.3 Nim博弈的代码实现与实操细节代码实现极其简单但有几个细节容易翻车// Nim博弈核心代码 int xorSum 0; for (int i 0; i n; i) { xorSum ^ piles[i]; } if (xorSum ! 0) { // 先手必胜 } else { // 先手必败 }实操心得很多人会问“如果先手必胜第一步该怎么走”。根据上面的证明找到异或和S的最高位p然后找一堆第p位为1的石子把它变成a_i XOR S。这个操作在需要输出方案的题目里经常考别忘了。还有一个常见坑石子数可能是0的堆。0对异或和没有影响所以可以忽略但读入的时候别因为0导致数组越界或者逻辑错误。4. SG函数与Sprague-Grundy定理博弈论的“万能钥匙”4.1 为什么需要SG函数Nim博弈解决的是“多堆独立石子”的问题但实际竞赛题里游戏往往不是简单的取石子——可能是棋盘上移动棋子、可能是拆分游戏、可能是各种奇怪的规则。这时候就需要一个更通用的工具把任意ICG映射成Nim博弈这就是SG函数和Sprague-Grundy定理的作用。SG函数的核心思想是给每个状态赋一个非负整数值叫做SG值使得这个值在博弈意义上等价于一堆大小为SG值的Nim石子。如果多个独立子游戏组合在一起总SG值就是各子游戏SG值的异或和。这样任意ICG都可以转化为Nim博弈来判定。4.2 SG函数的定义与计算方法对于一个状态x它的SG值定义为mex{SG(y) | y是x能一步到达的状态}其中mex表示“最小的不在集合中的非负整数”。举个例子如果状态x能到达的状态SG值分别是{0, 1, 3}那么SG(x) mex{0,1,3} 2。如果x是终端状态没有后继SG(x) mex{空集} 0。计算SG值通常用记忆化搜索int sg[MAXN]; bool visited[MAXN]; int computeSG(int state) { if (sg[state] ! -1) return sg[state]; setint reachable; for (每个从state能到达的状态next) { reachable.insert(computeSG(next)); } int g 0; while (reachable.count(g)) g; return sg[state] g; }注意SG值的计算复杂度取决于状态数和每个状态的转移数。如果状态空间太大就需要找SG值的规律通常是周期性的而不是暴力计算。4.3 Sprague-Grundy定理的完整证明SG定理的内容是如果一个游戏由k个独立的子游戏组成每个子游戏的SG值分别是g_1, g_2, ..., g_k那么总游戏的SG值等于g_1 XOR g_2 XOR ... XOR g_k。当且仅当总SG值非零时先手必胜。证明分两步和Nim博弈的证明结构完全一样第一步证明总SG0时是P状态。假设总SG0玩家对第i个子游戏操作使其SG从g_i变为g_i‘g_i’ ≠ g_i。新的总SG 0 XOR g_i XOR g_i‘ g_i XOR g_i’ ≠ 0。所以从总SG0出发任何操作都会到达总SG≠0。第二步证明总SG≠0时是N状态。设总SGS≠0最高位为p。存在某个g_i的第p位为1。令g_i‘ g_i XOR S则g_i’ g_i。由于SG函数的定义g_i‘一定在状态i的某个后继状态的SG值集合中这是SG函数mex性质保证的所以存在一个合法操作把第i个子游戏变成SG值为g_i’的状态。操作后总SG S XOR g_i XOR g_i‘ 0。这个证明的关键在于SG函数的mex定义保证了“任何小于当前SG值的非负整数都能被某个后继状态达到”这正是Nim博弈里“可以取任意数量石子”的推广。4.4 SG定理在组合游戏中的实战应用SG定理最强大的地方在于它允许我们把一个复杂游戏拆成多个独立部分分别计算SG值然后异或起来。比如经典的“Nim游戏变种每次可以取1到k个石子”单堆的SG值就是石子数mod (k1)多堆异或即可。再比如“棋子移动游戏”棋盘上有若干棋子每次可以把一个棋子向左移动若干格不能移动者输。每个棋子是独立的子游戏分别算SG值再异或。这种拆分思想是SG定理的精髓也是竞赛题最常考的形式。实操心得判断一个游戏能不能用SG定理关键看子游戏之间是否真正独立——即对一个子游戏的操作不影响其他子游戏的SG值。如果存在相互影响就不能简单异或需要把相互影响的部分合并成一个子游戏来处理。5. 经典博弈模型拆解与变形题分析5.1 巴什博弈最简单的“控制周期”模型巴什博弈的规则是一堆n个石子每次取1到m个取到最后一个者赢。结论是n mod (m1) ≠ 0时先手必胜否则先手必败。证明思路是“周期控制”如果n是(m1)的倍数无论先手取k个后手取(m1-k)个每轮合计取走m1个最终先手面对0个。如果n不是(m1)的倍数先手先取n mod (m1)个把局面变成(m1)的倍数交给后手然后模仿后手的操作保持周期。巴什博弈的变形很多比如“取到最后一个者输”反巴什这时候结论变成n mod (m1) ≠ 1时先手必胜。推导方法是把“取到最后一个输”转化为“取到倒数第二个赢”相当于石子数减1的普通巴什。5.2 威佐夫博弈两堆石子的黄金分割威佐夫博弈的规则是两堆石子每次可以从一堆取任意个或者从两堆取相同个取到最后一个者赢。结论涉及黄金分割比设两堆中较少的是a较多的是b令k b - a如果a floor(k × (1√5)/2)则先手必败否则先手必胜。这个结论的证明需要用到Beatty定理竞赛中一般直接记结论。但理解它的几何意义很有帮助必败态(a_k, b_k)满足a_k floor(k×φ)b_k a_k k其中φ是黄金分割比。这些点构成了一条斜率约为1.618的直线上的整数点。实操心得威佐夫博弈的精度问题是个大坑。计算k×φ时浮点误差可能导致判定错误建议用整数运算或者高精度。我一般用long double并把φ写成(1.0sqrt(5.0))/2实测在k不太大时没问题但k超过10^9就要小心。5.3 反Nim博弈结论反转的经典案例反Nim博弈的规则和Nim一样但取到最后一个石子的人输。结论比普通Nim复杂如果所有堆都是1则堆数为奇数时先手必败偶数时先手必胜。如果至少有一堆大于1则异或和非零时先手必胜异或和为零时先手必败。为什么会有这个区别因为当所有堆都是1时游戏变成了“轮流取一个”胜负完全由堆数奇偶决定。而当有堆大于1时玩家可以通过控制局面避免被迫取最后一个此时异或和的判定依然有效。这个结论我第一次看到时觉得很反直觉——为什么全是1的时候规则不一样后来画了几个状态图才明白全是1的时候不存在“取一部分留一部分”的操作空间所有操作都是确定的所以P/N状态退化成奇偶判定。5.4 阶梯Nim与树上博弈的转化技巧阶梯Nim的规则是石子放在阶梯上每次可以把某一阶的石子往下移任意个到下一阶移到地面第0阶的石子出局不能移动者输。结论是只需要考虑奇数阶上的石子做异或和即可。这个结论的证明用到了“配对”思想偶数阶的石子可以被对手“镜像”操作抵消掉。具体来说如果先手移动偶数阶的石子到奇数阶后手可以把同样多的石子从那个奇数阶移到下一个偶数阶保持奇数阶异或和不变。所以偶数阶的石子不影响胜负。树上博弈是另一个常见变形棋子在一棵树上每次可以把一个棋子向根方向移动任意步。每个棋子是独立的子游戏SG值等于该节点到根的距离。多个棋子异或即可。6. 博弈论题目的常见坑与排查技巧6.1 状态定义错误导致的连锁反应博弈论题最容易翻车的地方就是状态定义。我见过太多人包括我自己因为状态定义少考虑了一个维度导致整个SG值算错。比如“取石子翻转硬币”的题状态不仅要记录石子数还要记录硬币朝向再比如“棋盘上多个棋子”的题如果棋子之间有相互限制就不能简单拆分。排查方法拿小规模数据手推P/N状态和代码输出对比。如果对不上先检查状态定义是否完整再检查转移是否遗漏。6.2 SG值周期性的发现与验证很多题的SG值有周期性但周期不一定从0开始也不一定是你猜的那个。我的一般流程是先暴力算前100到200个SG值观察规律如果看不出明显周期就写个程序自动找周期从某个起点开始连续两个周期完全一致。注意找周期时一定要验证多个周期避免巧合。我踩过的坑是只验证了一个周期就下结论结果周期找错了WA到怀疑人生。6.3 边界条件与特殊情况的处理博弈论题的边界条件特别多石子数为0、堆数为1、所有堆都是1、先手第一步无路可走等等。这些情况往往需要单独处理不能指望通用逻辑覆盖。我的习惯是在代码里加一个special_case()函数把所有能想到的特殊情况先判掉再走通用逻辑。虽然看起来笨但能避免很多莫名其妙的WA。6.4 常见问题速查表问题现象可能原因排查方向小数据对但大数据WASG值周期性找错多验证几个周期所有数据都WA状态定义错误手推小规模P/N状态对比部分数据WA边界条件未处理检查0、1等特殊情况超时SG值暴力计算太慢找规律或优化转移反Nim结论用错未区分全1和非全1单独判断全1情况7. 从竞赛到实战博弈论思维的迁移价值博弈论在算法竞赛里是一个相对独立的模块但它培养的思维方式其实很通用。P/N状态的递归判定本质上是一种逆向归纳——从终局倒推判断每个局面的优劣。这种思维在决策分析、策略规划里都有应用。SG定理的拆分思想则是一种模块化分解——把复杂问题拆成独立子问题分别求解再组合。这种思路在系统设计、项目管理里同样常见。我自己在做一些策略类项目的时候就经常用P/N状态的思路来分析“当前局面有没有必胜策略”。虽然实际问题往往比ICG复杂得多存在信息不对称、非零和、连续决策等但把能拆的部分拆开、能判定的部分先判定这个方法论是通用的。最后分享一个我刷博弈论题的小习惯每做完一道题我都会问自己三个问题——这道题的核心模型是什么结论是怎么证明的如果改一个规则结论会怎么变这三个问题能帮我把一道题吃透而不是做完就忘。博弈论这东西模型就那么几个但变形无穷无尽只有理解了证明才能在变形题面前不慌。