1. 博弈论在算法竞赛中的定位与整体设计思路1.1 为什么博弈论是竞赛中的“思维分水岭”在算法竞赛里博弈论题目有个很明显的特征代码量往往极短但思维难度极高。很多选手第一次遇到博弈题时会本能地想去模拟、去搜索、去暴力枚举所有状态结果要么超时要么根本写不出正确的状态转移。原因在于博弈论考察的不是你写代码的能力而是你逆向推理和寻找不变量的能力。我个人的体会是博弈论是竞赛中少有的“想清楚了就十行代码想不清楚就零分”的题型。它不像数据结构题那样可以靠模板堆出来也不像动态规划那样有相对固定的套路。博弈论的核心在于你必须站在对手的角度思考并且假设对手和你一样聪明。这个假设是很多初学者最容易忽略的地方——题目里说的“双方都采取最优策略”意味着你不能指望对手犯错。从知识体系上看竞赛中的博弈论大致可以分为几个层次最基础的是巴什博弈和威佐夫博弈这类有闭式解的经典模型往上是Nim博弈及其变种涉及异或运算和SG函数再往上是SG定理和公平组合游戏的一般理论最后是一些需要结合其他算法如DP、二分图匹配、数学推导的综合性博弈问题。这条主线非常清晰只要按顺序吃透绝大多数竞赛博弈题都能找到切入点。1.2 公平组合游戏的核心框架竞赛中绝大多数博弈问题都属于公平组合游戏Impartial Combinatorial Game。所谓“公平”指的是双方可用的操作集合完全相同不区分先后手有不同规则的情况。比如取石子游戏双方都能取石子规则一样这就是公平的而像象棋这种红方和黑方走法不同的就不是公平组合游戏。公平组合游戏有几个关键性质理解这些性质是后续所有推导的基础有限性游戏必须在有限步内结束不能出现无限循环。这保证了游戏一定会分出胜负不会平局。无随机性不存在掷骰子这类随机因素结果是确定的。完全信息双方都能看到当前的全部局面。正常规则通常约定无法行动的一方判负也有反规则的情况但竞赛中较少。在这个框架下每个局面只有两种状态必胜态N-positionNext player wins和必败态P-positionPrevious player wins。判断标准很简单如果当前局面存在一个操作能到达必败态那当前就是必胜态如果所有操作都只能到达必胜态那当前就是必败态。这个递归定义是整个博弈论的基石。注意这个递归定义看起来简单但直接用它来搜索会面临状态爆炸的问题。所以我们需要找到规律用数学方法直接判断而不是真的去递归。1.3 从暴力搜索到数学规律的思维跃迁我见过很多选手包括我自己早期遇到博弈题的第一反应是写一个记忆化搜索把所有状态都算出来。对于小数据范围这确实可行但竞赛题的数据范围往往大到无法枚举。这时候就需要从暴力搜索的结果中观察规律归纳出闭式解或者利用SG函数来降维。举个例子巴什博弈中如果每次可以取1到m个石子总共n个石子那么必败态就是n能被(m1)整除的时候。这个结论如果靠搜索n小的时候能看出来但n很大的时候就必须靠数学证明。证明过程其实不复杂如果n是(m1)的倍数无论先手取多少个设为k个1≤k≤m后手都可以取(m1-k)个使得剩下的石子数仍然是(m1)的倍数最终先手面对0个石子先手输。反过来如果n不是(m1)的倍数先手取n mod (m1)个就能把局面变成(m1)的倍数之后先手就扮演了上面“后手”的角色必胜。这个证明体现了一个非常重要的思想策略偷取和配对策略。你在证明中构造了一种应对方式使得无论对手怎么走你都能把局面拉回到一个“安全”的状态。这种构造性证明在博弈论中非常常见也是解题的关键。2. 经典博弈模型的核心细节与实操要点2.1 巴什博弈最简单的减法游戏巴什博弈Bash Game的规则是一堆n个物品两人轮流取每次至少取1个最多取m个取到最后一个物品的人获胜。这个模型简单到几乎不需要代码但它是理解博弈论思维方式的最佳入口。结论很直接当n % (m1) 0时先手必败否则先手必胜。代码实现只需要一行判断def bash_game(n, m): return 先手必胜 if n % (m 1) ! 0 else 先手必败但我想强调的是这个结论背后的推导过程比结论本身重要得多。很多变种题比如“取到最后一个输”的反规则版本或者“每次取的数量必须是质数”的变种都需要你重新推导而不是套公式。对于反规则版本取到最后一个输结论会变成当(n-1) % (m1) 0时先手必败。推导思路是谁被迫取到最后一个谁就输所以实际上是谁面对1个物品谁就输。把问题转化成“谁取到第n-1个谁赢”就回到了标准巴什博弈。实操心得遇到巴什博弈的变种先别急着套公式。把n比较小的情况n1,2,3,4,5...手动推一遍画出必胜/必败的表格规律往往一眼就能看出来。我习惯在草稿纸上画一个表格左边是n右边是状态推个十来行规律就出来了。2.2 威佐夫博弈两堆物品的黄金分割威佐夫博弈Wythoff Game的规则是有两堆物品分别有a个和b个假设a≤b两人轮流操作每次可以从一堆中取任意多个或者从两堆中同时取相同多个。取到最后一个物品的人获胜。这个博弈的必败态有一个非常优美的数学结构必败态是(⌊kφ⌋, ⌊kφ²⌋)其中φ(1√5)/2是黄金分割比k0,1,2,...。前几个必败态是(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)...判断方法对于给定的(a,b)令k b - a如果a ⌊kφ⌋则先手必败否则先手必胜。import math def wythoff_game(a, b): if a b: a, b b, a k b - a phi (1 math.sqrt(5)) / 2 if a int(k * phi): return 先手必败 return 先手必胜这里有个精度问题需要注意当k比较大时浮点运算可能会有误差。稳妥的做法是用整数运算来验证或者用math.floor配合一个小的epsilon。我在实际比赛中遇到过因为精度问题导致判断错误的情况后来养成了用整数方法验证的习惯。威佐夫博弈的证明思路是首先证明必败态之间不会互相到达即从一个必败态出发无论怎么走都到不了另一个必败态然后证明任何非必败态都可以一步到达某个必败态。这两点结合起来就证明了必败态的充要性。具体证明涉及Beatty定理这里不展开但理解这个证明框架对做其他博弈题很有帮助。2.3 Nim博弈异或运算的魔力Nim博弈是竞赛中最重要、最常见的博弈模型。规则是有n堆物品每堆有a_i个两人轮流从任意一堆中取任意多个至少取1个取到最后一个物品的人获胜。结论极其简洁如果a_1 XOR a_2 XOR ... XOR a_n 0则先手必败否则先手必胜。def nim_game(piles): xor_sum 0 for p in piles: xor_sum ^ p return 先手必败 if xor_sum 0 else 先手必胜这个结论的证明是博弈论中最经典的证明之一值得完整理解引理1如果异或和不为0则存在一种操作使得异或和变为0。证明设异或和为SS的最高位为第k位。必然存在某一堆a_i其第k位为1。令a_i a_i XOR S则a_i a_i因为最高位从1变成了0所以从第i堆取走a_i - a_i个物品是合法操作。操作后新的异或和为S XOR a_i XOR a_i S XOR a_i XOR (a_i XOR S) 0。引理2如果异或和为0则任何操作都会使异或和不为0。证明从第i堆取走一些物品a_i变为a_i且a_i a_i所以a_i ≠ a_i。新的异或和为0 XOR a_i XOR a_i a_i XOR a_i ≠ 0。结合这两个引理再注意到终局所有堆为空的异或和为0就可以归纳证明异或和为0的局面是必败态异或和不为0的局面是必胜态。注意Nim博弈的结论虽然简单但它的应用远不止“取石子”。很多问题可以转化为Nim模型比如“阶梯Nim”、“树上Nim”等。转化的关键是找到什么是“堆”什么是“操作”。2.4 阶梯Nim与变种从一维到多维的扩展阶梯NimStaircase Nim是Nim的一个重要变种物品放在阶梯上每次可以从某一级阶梯取任意多个物品放到下一级阶梯取到地面第0级的物品视为被取走。取到最后一个物品的人获胜。结论是只需要考虑奇数级阶梯上的物品数量做异或和。如果异或和为0先手必败否则先手必胜。这个结论的推导思路很巧妙偶数级阶梯上的物品可以被对手“镜像”操作。如果你从偶数级取物品到奇数级对手可以把同样多的物品从那个奇数级取到下一级偶数级相当于你的操作被抵消了。所以偶数级阶梯上的物品不影响胜负只有奇数级阶梯上的物品才是关键。def staircase_nim(stairs): # stairs[0]是地面stairs[1]是第一级以此类推 xor_sum 0 for i in range(1, len(stairs), 2): # 只考虑奇数级 xor_sum ^ stairs[i] return 先手必败 if xor_sum 0 else 先手必胜阶梯Nim的变种很多比如“每次可以取任意多个放到下一级也可以直接取走”的版本或者“阶梯是环形的”版本。处理这些变种的关键是找到“哪些部分是冗余的”把问题化简回标准Nim。3. SG函数与SG定理的完整实操解析3.1 从Nim到SG函数游戏图的统一语言Nim博弈虽然强大但它只能处理“取石子”这一类问题。对于更一般的公平组合游戏比如“每次可以取1个或3个石子”、“可以取任意多个但必须取质数个”这类规则Nim的异或结论就不适用了。这时候就需要SG函数出场。SG函数Sprague-Grundy函数的定义是对于一个局面xSG(x) mex{SG(y) | y是x能到达的局面}其中mex是最小非负整数Minimum Excluded。比如如果x能到达的局面的SG值集合是{0,1,3}那么SG(x)2。SG函数的直观理解是它把每个局面映射成一个非负整数这个整数等价于“一堆大小为SG(x)的Nim堆”。也就是说一个SG值为k的局面等价于一个大小为k的Nim堆。计算SG函数的基本方法是记忆化搜索或动态规划。对于状态空间不大的问题可以直接递归计算def compute_sg(state, memo, moves): if state in memo: return memo[state] reachable set() for next_state in moves(state): reachable.add(compute_sg(next_state, memo, moves)) g 0 while g in reachable: g 1 memo[state] g return g实操心得计算SG函数时mex操作可以用一个布尔数组来加速。如果状态空间很大可以考虑用时间戳来避免每次清空数组。我通常用一个vis数组配合一个递增的tag变量这样每次只需要比较vis[g] ! tag即可省去了清空的开销。3.2 SG定理多个子游戏的组合SG定理是公平组合游戏理论的核心如果一个游戏可以分解为多个独立的子游戏那么整个游戏的SG值等于各个子游戏SG值的异或和。这个定理的证明思路和Nim博弈的证明几乎一模一样只是把“堆的大小”换成了“SG值”。因为SG函数的定义保证了SG值为k的局面其行为等价于一个大小为k的Nim堆。所以多个子游戏组合起来就等价于多个Nim堆的组合自然适用异或规则。SG定理的威力在于它允许我们把一个复杂的游戏拆解成多个简单的子游戏分别计算SG值然后异或起来。比如“有n堆石子每次可以从一堆中取1到m个”这个游戏每一堆是一个子游戏其SG值就是该堆石子数对(m1)取模。整个游戏的SG值就是所有堆SG值的异或和。def sg_theorem(subgames_sg): xor_sum 0 for sg in subgames_sg: xor_sum ^ sg return 先手必败 if xor_sum 0 else 先手必胜3.3 SG函数的打表技巧与规律发现在实际竞赛中很多博弈题的SG函数有周期性规律。比如“每次可以取1到3个石子”的SG函数就是0,1,2,3,0,1,2,3,...循环。对于这类问题我们可以先打表算出前几十个SG值观察规律然后用数学方法证明。打表的方法很简单从小到大计算每个状态的SG值因为计算SG(x)需要知道所有x能到达的状态的SG值而这些状态通常比x小对于取石子类游戏。def sg_table(n, max_take): sg [0] * (n 1) for i in range(1, n 1): reachable set() for take in range(1, min(i, max_take) 1): reachable.add(sg[i - take]) g 0 while g in reachable: g 1 sg[i] g return sg # 打印前30个SG值 print(sg_table(30, 3)) # 输出: [0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, ...]打表之后如果发现周期为T就可以用sg[i] sg[i % T]来快速计算。但要注意有些游戏的SG函数周期不是从第一项开始的可能有一个“前导段”。比如SG值可能是0,1,2,1,2,1,2,...这种前几项不参与循环。这时候需要仔细确定循环的起点和周期。注意打表找规律虽然好用但一定要验证规律的正确性。我见过有人打表到20项就急着下结论结果周期其实是30导致WA。稳妥的做法是至少打到100项以上并且用不同的参数多试几组。3.4 反Nim博弈与SG定理的边界反Nim博弈Misère Nim的规则是取到最后一个物品的人输。这个变种看起来只是改了一个字但结论完全不同。反Nim的结论是如果所有堆的大小都是1则当堆数为奇数时先手必败偶数时先手必胜如果至少有一堆大小大于1则按照标准Nim的规则判断异或和为0则先手必败。这个结论的推导需要分情况讨论。当所有堆都是1时游戏退化成“轮流取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 先手必败 if len(piles) % 2 1 else 先手必胜 else: return 先手必败 if xor_sum 0 else 先手必胜反Nim提醒我们SG定理适用于正常规则的公平组合游戏对于反规则的游戏不能直接套用SG定理需要单独分析。这是很多选手容易踩的坑。4. 常见问题与排查技巧实录4.1 博弈题常见错误类型与排查表在做博弈题的过程中我总结了几类高频错误整理成下面这个排查表方便快速定位问题错误类型典型表现排查方法预防措施边界条件遗漏小数据WA大数据AC手动测试n0,1,2等边界写代码前先列边界情况规律找错打表前几项对后面错多打几项验证周期至少打100项再下结论SG函数计算错误组合游戏结果不对单独验证每个子游戏的SG值用暴力搜索对拍精度问题威佐夫博弈偶尔WA用整数运算替代浮点加epsilon或整数验证反规则套用SG定理反Nim类题目WA检查游戏是否为正常规则反规则单独分析状态定义不清搜索空间爆炸重新定义状态找不变量先数学分析再写代码4.2 对拍博弈题最可靠的验证手段博弈题因为代码短很容易写出“看起来对”的代码但实际上逻辑有漏洞。这时候对拍是最有效的验证方法。具体做法是写一个暴力搜索的版本对于小数据范围再写一个优化版本随机生成小数据比较两个版本的输出。暴力搜索的框架通常是这样的def brute_force(state, memo): if state in memo: return memo[state] # 如果无法行动当前玩家输 if is_terminal(state): memo[state] False # False表示当前玩家必败 return False for next_state in get_moves(state): if not brute_force(next_state, memo): memo[state] True return True memo[state] False return False这个暴力搜索直接根据必胜/必败态的定义来写虽然效率低但逻辑绝对正确。用它来验证你的优化版本可以快速发现规律找错、边界遗漏等问题。实操心得对拍的时候数据生成器要覆盖各种情况包括n0、n1、所有堆都是1、只有一堆等特殊局面。我一般会写一个随机生成器随机生成10组小数据跑个几百轮基本能覆盖大部分情况。4.3 从搜索到规律的思维转换技巧很多选手卡在“知道要打表找规律但不知道怎么找”这一步。我的经验是打表之后先看SG值序列的差分再看周期性最后看是否和某个已知数列如斐波那契、卡特兰数有关。具体步骤打印前50到100个SG值。观察是否有明显的周期。如果有确定周期T和起始位置。如果没有明显周期看SG值是否只取少数几个值比如只有0和1这可能意味着游戏等价于某个简单的Nim变种。如果SG值增长很快可能和二进制表示有关尝试找异或规律。最后用数学归纳法证明你找到的规律。我遇到过一个题SG值序列是0,1,0,2,0,1,0,3,0,1,0,2,...这个序列的规律是SG(i)等于i的二进制表示中最低位1的位置也就是i的lowbit的指数。这种规律如果不打表很难发现但打表之后一眼就能看出来。4.4 博弈论与其他算法的结合场景竞赛中的博弈题很少是纯粹的博弈论往往需要和其他算法结合。常见的结合方式有博弈DP状态空间较大需要用DP来计算SG值。比如“每次可以取斐波那契数个石子”的博弈SG值需要用DP打表。博弈二分图匹配某些游戏可以转化为二分图上的匹配问题用匈牙利算法或最大流求解。博弈数学推导需要先推导出闭式解再用快速幂等技巧计算。比如“每次可以取2的幂次个石子”的博弈SG值就是i的二进制表示中1的个数。博弈树形结构在树上进行博弈需要结合树的遍历和SG函数。比如“树上删边游戏”每个节点的SG值等于其子节点SG值1的异或和。这些结合题目的难点在于你需要先识别出博弈的部分然后选择合适的工具来计算SG值或判断胜负。我的建议是先把纯博弈的部分吃透再逐步接触这些综合题。5. 博弈论学习路径与实战建议5.1 从入门到进阶的刷题顺序如果你刚开始接触博弈论我建议按照以下顺序刷题巴什博弈找3到5道基础题理解必胜/必败态的推导。威佐夫博弈找2到3道题熟悉黄金分割的判断方法。Nim博弈找5到8道题包括标准Nim和各种变种阶梯Nim、反Nim等。SG函数找5到10道题从简单的取石子游戏开始逐步过渡到需要打表找规律的题目。综合题找3到5道结合DP或数学推导的博弈题锻炼综合能力。每道题做完之后不要只看AC代码要自己把证明过程写一遍。博弈论的核心是思维代码只是最后一步。5.2 比赛中的博弈题应对策略在比赛中遇到博弈题我的策略是先判断类型是经典模型还是需要推导的新模型如果是经典模型直接套结论如果是新模型先手动推小数据。手动推演在草稿纸上列出n0到10的所有状态标记必胜/必败观察规律。尝试打表如果手动推演看不出规律写一个暴力搜索程序打表打印SG值序列。验证规律找到规律后用暴力搜索对拍验证确保规律在小数据范围内正确。注意边界特别关注n0、n1、所有堆为1等特殊情况。注意比赛时间有限如果一道博弈题想了20分钟还没有思路建议先跳过做其他题。博弈题有时候需要灵感卡住了硬想效率很低。5.3 我踩过的那些坑最后分享几个我在博弈题上踩过的坑希望能帮你少走弯路坑一忽略“双方都采取最优策略”的前提。有一次我做一道题觉得先手可以故意走一步“坏棋”来诱导对手犯错结果WA了。后来才意识到题目假设对手也是最优策略不会犯错。所以你的策略必须建立在“对手永远做出最优选择”的基础上。坑二SG函数打表时忘记考虑所有可能的操作。有一次我写SG函数只考虑了取1到m个石子但题目还允许“取走一堆中的全部石子”这个操作我漏掉了导致SG值算错。后来养成了习惯写SG函数之前先把所有合法操作列出来确保没有遗漏。坑三威佐夫博弈的精度问题。前面提到过k比较大时浮点运算会有误差。我后来改用整数方法先计算kb-a然后计算int(k * 1.618033988749895)再和a比较。如果相差在1以内再用精确方法验证。这样基本不会出错。坑四反Nim的边界条件。反Nim中如果所有堆都是1结论和标准Nim完全不同。我有一次忘记判断这个情况直接套了标准Nim的异或规则结果WA。后来每次做反Nim题第一件事就是检查是否所有堆都是1。坑五SG定理的适用条件。SG定理只适用于正常规则的公平组合游戏。如果游戏是反规则取到最后一个输或者不是公平的双方操作不同就不能直接套用SG定理。我有一次在一道反规则游戏上套了SG定理结果怎么都对不上后来才发现问题所在。这些坑看起来都是小问题但在比赛中往往就是AC和WA的区别。博弈论题目代码短一旦逻辑有漏洞很难通过调试发现所以前期的数学分析和验证尤为重要。