1. 从“背结论”到“推结论”博弈论在竞赛中的真实定位很多人第一次接触博弈论是在竞赛题库里刷到一堆“取石子”“拿硬币”“切巧克力”的题。当时我的做法很粗暴把几种经典模型巴什博弈、威佐夫博弈、尼姆博弈的必胜条件背下来看到类似的题就往公式上套。短期确实能过题但一旦题目稍微变形——比如石子堆数变了、取子规则加了限制、胜负判定改成“取到最后一个输”——立刻就懵了。后来我才意识到博弈论题目的核心不是记忆而是状态与胜负关系的推导。所有公平组合游戏Impartial Combinatorial Game的底层逻辑都可以归结为一句话当前局面是必胜态还是必败态取决于它能否转移到某个必败态。这个定义看起来简单但它能推出后面所有模型包括那些看起来毫无规律的取子游戏。这篇文章我打算把博弈论从零到能打区域赛的完整知识链路梳理一遍。不是那种“结论代码”的速查表而是把每个结论背后的推导过程、为什么这样定义、怎么从定义一步步算出公式全部摊开讲清楚。适合两类人一是刚学博弈论、被各种公式绕晕的选手二是打过一些题但遇到变形就不会做的选手。如果你属于后者大概率是因为跳过了推导直接背结论。全文会覆盖必胜态/必败态的严格定义与证明方法、巴什博弈的完整推导、威佐夫博弈的贝蒂定理证明思路、尼姆博弈与SG定理的来龙去脉、反尼姆博弈的坑点、以及SG函数在非取子类游戏如分割游戏、图上游戏中的应用。每个模型我都会给出“为什么是这样”的分析而不是只丢一个公式。2. 必胜态与必败态整个博弈论体系的公理基础2.1 两个定义撑起所有公平组合游戏在公平组合游戏中两个玩家轮流操作操作规则完全对称即不存在某个操作只有一方能做无法操作的一方判负。这是最常见的约定后面讨论的模型默认都基于这个前提。在这个框架下我们定义必败态P-positionPrevious player wins当前玩家无论怎么操作都会把局面交给对手一个必胜态。换句话说当前玩家在这个局面下没有获胜策略。必胜态N-positionNext player wins当前玩家存在至少一种操作能把局面交给对手一个必败态。这两个定义是递归的。终止局面无法操作的局面是必败态因为轮到谁谁就输了。然后所有能一步到达终止局面的状态是必胜态所有只能到达必胜态的状态是必败态以此类推。注意这里的“必胜/必败”是针对“当前轮到操作的玩家”而言的。同一个局面如果换一个玩家来描述胜负属性不变因为规则对称。2.2 为什么这个定义能推出所有结论很多人会问凭什么说“能到达必败态就是必胜态”这不是循环定义吗其实不是。这是一个有向无环图上的递归定义。游戏的状态转移构成一个有向无环图因为游戏必须在有限步内结束不能无限循环终止节点是出度为0的节点。我们在这个DAG上做如下标记所有出度为0的节点标记为P。如果一个节点的所有后继都是N则标记为P。如果一个节点存在至少一个后继是P则标记为N。这个标记过程是良定义的因为DAG可以拓扑排序从终止节点倒推。标记完成后N节点就是必胜态P节点就是必败态。证明很简单如果当前是N当前玩家走到那个P后继对手面对P根据定义对手必败如果当前是P当前玩家无论走到哪个后继那个后继都是N对手面对N对手有必胜策略。所以整个博弈论的核心任务就变成了给定一个游戏的状态转移规则判断初始状态是N还是P。对于状态空间小的问题直接DP递推即可对于状态空间大的问题需要找规律或数学公式。2.3 从定义出发的三种解题路径在实际竞赛中判断N/P有三条路暴力DP打表状态数在可接受范围内比如10^6以内直接按拓扑序递推。这是最稳的方法也是找规律的前提。找规律/数学公式打表后观察N/P的分布规律猜测公式再用数学归纳法证明。巴什博弈、威佐夫博弈都是这条路。SG定理分解对于多个独立子游戏组合的局面用SG函数把每个子游戏映射成一个数再用异或判断。尼姆博弈及其变种走这条路。三条路不是互斥的。很多时候先用DP打表再找规律最后用SG定理统一解释。下面逐个展开。3. 巴什博弈从打表到公式的完整推导链3.1 问题描述与朴素DP巴什博弈Bash Game是最简单的取子游戏有一堆n个石子两人轮流取每次至少取1个至多取m个取到最后一个石子的人获胜。按照第2节的定义我们可以直接写DP状态剩余石子数i。终止i0是必败态轮到谁谁输因为没石子可取。转移从i可以走到i-1, i-2, ..., i-m前提是i-k 0。判断如果存在k使得i-k是必败态则i是必胜态否则i是必败态。用代码写出来就是def bash_dp(n, m): # dp[i] True 表示剩余i个石子时当前玩家必胜 dp [False] * (n 1) for i in range(1, n 1): for k in range(1, min(i, m) 1): if not dp[i - k]: dp[i] True break return dp跑一下n15, m3的结果i0123456789101112131415dpPNNNPNNNPNNNPNNN规律非常明显i是(m1)的倍数时是必败态否则是必胜态。3.2 为什么是(m1)的倍数构造性证明打表看出规律后需要证明。证明分两步第一步证明(m1)的倍数是必败态。假设当前剩余石子是k(m1)。无论当前玩家取x个1 x m对手都可以取(m1-x)个使得这一轮总共取了(m1)个剩余石子变成(k-1)(m1)。对手总能这样做直到剩余0个此时当前玩家面对0个必败。这里的关键是对手的回应策略是“补足m1”。因为x在1到m之间所以m1-x也在1到m之间是对手的合法操作。这个策略能一直执行下去所以k(m1)是必败态。第二步证明非(m1)倍数的是必胜态。假设当前剩余石子是k(m1)r其中1 r m。当前玩家取r个剩余k(m1)个交给对手一个必败态。所以当前玩家必胜。两步合起来结论成立。这个证明是构造性的不仅证明了结论还给出了必胜策略每次取的石子数 当前石子数 mod (m1)如果余数不为0如果余数为0则无论怎么取都会输。3.3 变形与坑点取到最后一个输巴什博弈最常见的变形是“取到最后一个石子的人输”Misère版本。这时候结论会变。打表看看n15, m3, 取到最后一个输的情况i0123456789101112131415dpNPNNNPNNNPNNNPNN注意i0变成了必胜态因为轮到谁谁“赢”规则反了。规律变成i mod (m1) 1时是必败态其余是必胜态除了i0特殊。为什么因为当剩余1个时当前玩家必须取1个取完对手面对0个按照“取到最后一个输”的规则对手输了所以当前玩家赢了等等这里要仔细。“取到最后一个输”的意思是谁取走最后一个石子谁输。所以如果剩余1个当前玩家取走它当前玩家就输了。所以剩余1个是必败态。剩余0个呢游戏已经结束上一手取走最后一个的人输了所以面对0个的玩家是赢了。所以0是必胜态。从1开始推1是P2可以走到1取1个所以2是N3可以走到1取2个或2所以3是N4可以走到1取3个所以4是N5只能走到2,3,4取1,2,3个全是N所以5是P。规律确实是i mod (m1) 1时P。实操心得Misère版本的巴什博弈在竞赛中出现的频率不低但很多人只背了标准版的公式遇到Misère就翻车。记住一个原则Misère版本通常只需要把标准版的结论“平移”一下但平移的方式因游戏而异不能无脑套。最稳的方法是重新打表找规律。4. 威佐夫博弈贝蒂定理与黄金分割的登场4.1 两堆石子的新局面威佐夫博弈Wythoff Game是两堆石子的取子游戏有两堆石子数量分别为a和b两人轮流取有两种操作方式从其中一堆取任意多个至少1个。从两堆同时取相同数量的石子至少1个。取到最后一个石子的人获胜。这个游戏的状态是二维的(a, b)假设a b。打表找必败态ab必败态00P01N11N12P22N35P47P610P813P915P必败态序列(0,0), (1,2), (3,5), (4,7), (6,10), (8,13), (9,15), ...观察规律每个必败态的差值b-a依次是0, 1, 2, 3, 4, 5, 6... 而且每个正整数恰好出现在一个必败态中作为a或b。4.2 贝蒂定理为什么必败态与黄金分割有关设第k个必败态从k0开始为(a_k, b_k)其中a_k b_kk1。根据观察b_k - a_k k。而且a_k是前面所有必败态中未出现的最小正整数。这个序列有一个闭式解a_k floor(k * φ)b_k floor(k * φ^2)其中φ (1√5)/2 ≈ 1.618是黄金分割比。为什么这要用到贝蒂定理Beattys Theorem如果两个正无理数α和β满足1/α 1/β 1那么序列{floor(nα)}和{floor(nβ)}恰好划分正整数集即每个正整数恰好出现在其中一个序列中。取α φβ φ^2验证1/φ 1/φ^2 1因为φ^2 φ1所以1/φ 1/φ^2 (φ1)/φ^2 φ^2/φ^2 1。所以{floor(kφ)}和{floor(kφ^2)}划分正整数集。而威佐夫博弈的必败态恰好满足a_k floor(kφ)b_k a_k k floor(kφ) k floor(kφ k) floor(k(φ1)) floor(kφ^2)。所以必败态就是这两个序列配对。这个证明的美妙之处在于它把博弈论的必败态分布和数论中的无理数划分联系起来了。竞赛中遇到威佐夫博弈直接判断如果a floor((b-a) * φ)则是必败态否则是必胜态。4.3 精度问题竞赛中的实现细节用公式判断时φ是无理数浮点运算会有精度问题。当a和b很大时比如10^18double的精度不够。解决方案用整数运算模拟。设d b - a需要判断a是否等于floor(d * φ)。由于φ (1√5)/2可以转化为判断a是否满足某个整数不等式。具体做法计算d * (1√5)/2但用整数运算。设x floor(d * (1√5)/2)可以通过以下方式精确计算import math def wythoff(a, b): if a b: a, b b, a d b - a # 用高精度计算 floor(d * (1sqrt(5))/2) # 方法用整数平方根 # floor(d * (1sqrt(5))/2) floor((d d*sqrt(5))/2) # 先算 floor(d*sqrt(5))再处理 # 更稳的方法用decimal或直接比较 phi (1 math.sqrt(5)) / 2 return a int(d * phi)对于10^18级别的数据double的精度大约15-16位十进制可能出错。更稳的方法是用整数运算判断a是否等于floor(d * φ)。由于φ满足φ^2 φ 1可以推导出判断条件a floor(d * φ) 等价于 a d * φ a1即 a/d φ (a1)/d。由于φ是无理数可以转化为整数比较a^2 a*d - d^2 的符号实际上有更直接的结论必败态当且仅当 a floor(d * φ)等价于 a floor((d * (1√5))/2)。在C中可以用long double80位扩展精度约18-19位十进制来算对于10^18的数据基本够用。如果还不放心可以用整数二分或直接推导整数条件。实操心得威佐夫博弈的精度坑是经典问题。我见过有人在区域赛因为double精度不够WA了3发。建议直接用long double或者记住一个整数判断法设d b-a则必败态当且仅当 a (long long)(d * 1.6180339887498948482)。这个常数写够20位配合long double10^18以内不会错。5. 尼姆博弈与SG定理从具体游戏到通用框架5.1 尼姆博弈异或和的魔力尼姆博弈Nim Game是博弈论中最核心的模型有n堆石子每堆数量为a_i两人轮流取每次可以从任意一堆中取任意多个至少1个取到最后一个石子的人获胜。结论如果a_1 xor a_2 xor ... xor a_n 0则必败态否则必胜态。这个结论的证明分两步第一步异或和为0时任何操作都会使异或和非0。假设当前异或和为0。从某一堆取走x个石子x1该堆从a变成a a-x a。新的异或和 0 xor a xor a a xor a。由于a a所以a xor a ! 0因为两个不同的数异或不可能为0。所以操作后异或和非0。第二步异或和非0时存在操作使异或和变为0。设当前异或和为S ! 0。找到S的最高位1设该位为第k位。必然存在某一堆a_i其第k位也是1否则S的第k位不可能是1。令a_i a_i xor S。由于a_i的第k位是1S的第k位是1所以a_i的第k位是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。两步合起来结论成立。这个证明是构造性的给出了必胜策略每次找到异或和的最高位选一堆该位为1的石子把它变成a_i xor S。5.2 SG函数把任意游戏映射成尼姆堆尼姆博弈的结论很漂亮但它只适用于“从一堆取任意多个”这种操作。如果游戏规则变了比如每次只能取1或2个或者游戏是“分割”而不是“取子”尼姆博弈的结论就不直接适用了。SG函数Sprague-Grundy函数解决了这个问题。它的核心思想是任何公平组合游戏的状态都可以映射成一个非负整数使得这个状态等价于一个大小为该整数的尼姆堆。定义对于一个状态xSG(x) mex{SG(y) | y是x的后继}其中mex是最小非负整数Minimum Excluded即最小的不在集合中的非负整数。有了SG函数多个独立子游戏组合的局面其SG值等于各子游戏SG值的异或和。如果异或和为0则必败否则必胜。为什么因为SG函数的定义保证了如果SG(x) k则x可以到达所有SG值为0,1,...,k-1的后继由mex定义保证存在且不能到达SG值为k的后继。这与尼姆堆大小为k的行为完全一致从大小为k的堆可以取到任意小于k的大小但不能保持k不变。所以SG函数把任意游戏“翻译”成了尼姆博弈。尼姆博弈的异或结论可以直接套用。5.3 SG函数的计算从打表到记忆化搜索计算SG函数的标准方法是记忆化搜索def sg(x, memo, moves): if x in memo: return memo[x] reachable set() for m in moves: if x m: reachable.add(sg(x - m, memo, moves)) g 0 while g in reachable: g 1 memo[x] g return g对于状态空间大的问题需要找SG函数的规律。比如“每次取1到m个”的取子游戏SG(x) x mod (m1)。这个规律可以用归纳法证明。实操心得SG函数的打表找规律是竞赛中的常规操作。我通常先写一个暴力SG打印前100个值然后观察周期性。大部分取子类游戏的SG函数都是周期性的找到周期后就能O(1)计算。注意周期可能不是从0开始的前面可能有一段“前缀”需要单独处理。6. 反尼姆博弈规则反转后的坑点6.1 取到最后一个输的尼姆博弈反尼姆博弈Misère Nim的规则是取到最后一个石子的人输。其他规则和尼姆博弈一样。结论比标准尼姆复杂如果所有堆的大小都是1则必败态当且仅当堆数n是奇数因为每堆1个轮流取取到最后一个的输所以奇数堆时先手被迫取最后一个。如果存在至少一堆大小大于1则必败态当且仅当异或和为0。为什么分情况讨论情况一所有堆都是1。游戏变成n个1每次只能取1个。总共取n次第n次取的人输。所以n为奇数时先手输n为偶数时先手赢。情况二至少有一堆大于1。此时结论和标准尼姆一样异或和为0则必败。证明思路是当异或和为0且至少有一堆大于1时先手无论怎么取都会破坏异或和为0的状态对手可以恢复。而且对手可以控制游戏不进入“所有堆都是1”的必败分支。具体证明略复杂但结论是可靠的。6.2 反尼姆的常见错误很多人以为反尼姆就是把标准尼姆的结论反过来这是错的。反尼姆的结论是分情况的不能简单反转。我见过一个典型的错误有人写反尼姆的判断时直接判断异或和是否为0忽略了“所有堆都是1”的特殊情况。结果遇到n1, a[1]的数据时异或和为1按标准尼姆是必胜但反尼姆下先手必须取1个取完对手面对0个对手输了等等取到最后一个输先手取走最后一个先手输了。所以n1, a[1]是必败态。但异或和为1按标准尼姆是必胜。所以确实不能简单套。正确的判断逻辑def misere_nim(piles): xor_sum 0 all_one True for p in piles: xor_sum ^ p if p 1: all_one False if all_one: return len(piles) % 2 0 # 偶数堆必胜 else: return xor_sum ! 0 # 异或和非0必胜注意反尼姆的结论只适用于“取到最后一个输”的尼姆博弈。如果游戏还有其他限制比如每次最多取m个结论会变需要重新推导。7. SG定理的进阶应用分割游戏与图上游戏7.1 分割游戏SG函数的加法性质有些游戏不是“取子”而是“分割”。比如有一张n*m的纸每次可以沿格线剪开剪成两块谁不能剪谁输。这种游戏的状态是一个矩形操作是把它分成两个矩形。对于分割游戏SG函数有一个重要性质如果一次操作把状态x分成y和z两个独立子游戏则SG(x) mex{SG(y) xor SG(z)}。这是因为分割后的两个子游戏是独立的可以分别计算SG值再异或。这个性质大大扩展了SG定理的适用范围。很多看起来复杂的游戏只要能分解成独立子游戏就能用SG定理处理。7.2 图上游戏SG函数在有向图上的计算更一般地游戏的状态转移可以构成一个有向无环图。每个节点是一个状态每条边是一次操作。SG函数在这个图上定义SG(v) mex{SG(u) | u是v的后继}如果图有环游戏可能无限进行需要特殊处理通常约定不能重复经过同一状态或者游戏在有限步内强制结束。对于图上游戏计算SG函数的方法和取子游戏一样记忆化搜索或拓扑排序递推。如果图很大需要找规律。7.3 多子游戏组合异或和的直观理解为什么多个独立子游戏的SG值要异或直观理解每个子游戏相当于一个尼姆堆堆的大小就是SG值。尼姆博弈的结论是异或和为0则必败所以多个子游戏组合的胜负判断就是SG值异或和是否为0。这个直观理解在竞赛中非常有用。遇到一个复杂游戏先看能不能分解成独立子游戏如果能分别算SG值再异或。实操心得分解子游戏时要注意“独立性”的定义。两个子游戏必须互不影响即在一个子游戏中的操作不能改变另一个子游戏的状态。如果操作会同时影响多个子游戏就不能简单分解需要把整个局面作为一个状态来算SG。8. 从打表到证明博弈论题目的通用解题流程8.1 第一步判断游戏类型拿到一道博弈论题目先判断它属于哪类单堆取子每次取1到m个巴什博弈。两堆取子可以取一堆任意个或两堆相同个威佐夫博弈。多堆取子每次取一堆任意个尼姆博弈。多堆取子取到最后一个输反尼姆博弈。其他规则可能需要SG函数或找规律。8.2 第二步小数据打表如果无法直接套用已知模型先写暴力DP或暴力SG打印小数据的结果。打表时注意状态表示要清晰比如(a, b)表示两堆数量。转移要完整不要漏掉任何合法操作。打印格式要便于观察规律比如按a排序或者按差值排序。8.3 第三步观察规律并猜测公式打表后观察N/P的分布。常见规律周期性每隔k个状态重复一次。线性关系P态满足某个线性方程。与数论函数相关比如floor、mod、异或。8.4 第四步证明猜测猜测需要证明才能放心使用。证明方法数学归纳法证明P态满足某条件N态满足另一条件。构造性证明给出必胜策略证明策略可行。反证法假设存在不满足条件的P态推出矛盾。8.5 第五步实现并测试证明后实现代码注意边界条件和精度问题。测试时至少覆盖最小数据n0, n1。边界数据nm, nm1。大数据验证公式是否溢出或精度不够。实操心得博弈论题目的测试数据往往很刁钻尤其是边界情况。我习惯在实现后手动构造几组边界数据比如全1、全m、nm1等确保代码不会在这些情况下出错。9. 竞赛中的博弈论实战经验与避坑清单9.1 常见坑点汇总坑点表现解决方案精度问题威佐夫博弈用double判断大数时出错用long double或整数判断Misère版本直接套标准版公式导致错误重新打表找规律反尼姆特殊情况忽略全1堆的情况单独判断全1堆SG函数周期误以为周期从0开始检查前缀单独处理子游戏独立性错误分解不独立的子游戏确认操作不影响其他子游戏状态空间溢出DP数组开太小估算状态数必要时用map9.2 时间分配建议博弈论题目在区域赛中通常属于“中等难度”题。如果一眼能看出是经典模型直接套公式5分钟内解决。如果需要打表找规律预留20-30分钟。如果打表后找不到规律考虑是否需要用SG函数或更复杂的数学工具。9.3 训练建议想提高博弈论水平建议按以下顺序练习先把巴什、威佐夫、尼姆、反尼姆四个经典模型的手推过程完整写一遍不查资料。刷20道经典模型的直接应用题确保公式记牢。刷10道变形题Misère版本、多堆变种、取子规则变化练习打表找规律。刷5道SG函数应用题分割游戏、图上游戏练习SG函数的计算和分解。刷5道综合题多个子游戏组合、需要证明的题练习完整解题流程。9.4 个人体会我刚开始学博弈论时最大的误区是“背结论”。后来发现背下来的结论只能解决原题稍微变形就不会。真正有用的是推导能力给定一个新游戏能自己打表、找规律、证明、实现。这个能力不是靠背题能练出来的必须亲手推几个模型把“为什么”搞清楚。另外博弈论和数论、组合数学的联系非常紧密。威佐夫博弈用到贝蒂定理尼姆博弈用到异或性质SG函数用到mex和DAG。如果这些基础知识不牢博弈论也很难学好。建议在学博弈论的同时补一下数论和组合数学的基础。最后博弈论题目的代码通常很短但思维量很大。竞赛中遇到博弈论题不要急着写代码先在纸上推一推把规律找出来再写。磨刀不误砍柴工这个习惯能帮你省下大量调试时间。