博弈论算法精讲：从公平组合游戏到SG函数实战（ACM/OI选手必备）

1. 公平组合游戏ICG入门想象你和朋友玩一个取石子游戏桌上有几堆石子每次可以从一堆里拿走任意数量的石子拿走最后一颗的人获胜。这就是经典的Nim游戏也是公平组合游戏Impartial Combinatorial Games, ICG的典型代表。公平组合游戏必须满足三个核心特征双人轮流游戏由两名玩家交替进行不存在同时行动无差别规则每个玩家在相同局面下的合法操作完全相同有限终止游戏必定在有限步数内结束且不存在平局举个反例围棋就不是ICG因为黑方和白方规则不同。而象棋虽然满足双人轮流但不同棋子的移动规则差异使其也不属于ICG。2. 博弈图与必胜策略2.1 游戏状态的图论模型任何ICG都可以转化为有向无环图DAG每个节点代表一个游戏状态边代表合法的状态转移没有出边的节点是终止状态# 示例3个石子的Nim游戏状态转移 graph { 3: [2, 1, 0], # 可以拿走1/2/3个 2: [1, 0], 1: [0], 0: [] # 终止状态 }2.2 必胜态与必败态判定关键定理终止状态是必败态P-position能转移到必败态的状态是必胜态N-position只能转移到必胜态的状态是必败态以Nim游戏[3,1]为例[0,0]是必败态[1,0]、[0,1]都能一步到[0,0]是必胜态[1,1]只能转移到[1,0]或[0,1]所以是必败态3. SG函数理论精要3.1 Mex运算与SG定义Mex运算最小排斥值mex(S) min\{x | x \in \mathbb{N}, x \notin S\}SG函数递归定义终止状态SG0SG(u) mex{SG(v) | u→v}def calculate_sg(u, graph, memo): if u in memo: return memo[u] if not graph[u]: # 终止状态 return 0 successors [calculate_sg(v, graph, memo) for v in graph[u]] sg 0 while sg in successors: sg 1 memo[u] sg return sg3.2 SG定理的威力对于组合游戏GG₁G₂...GₙSG(G) SG(G₁) ⊕ SG(G₂) ⊕ ... ⊕ SG(Gₙ)其中⊕表示异或运算。当且仅当SG(G)≠0时先手有必胜策略。4. 经典博弈模型实战4.1 Nim游戏变种标准Nim各堆石子数异或和为0时先手必败否则先手可通过调整使异或和为0Bash博弈限定每次取1-m个当(m1)整除总数时先手必败策略保持每次取完后剩余数为(m1)的倍数Wythoff博弈两堆石子必败态为(⌊kφ⌋, ⌊kφ²⌋)其中φ(1√5)/2涉及黄金分割的奇妙数学性质4.2 斐波那契博弈每次取数不超过前一次的2倍当石子数为斐波那契数时先手必败齐肯多夫定理的应用典范5. 竞赛高级技巧5.1 游戏分解策略复杂游戏往往能分解为独立子游戏识别游戏中的独立组件计算各组件SG值异或合并得到总SG值例题有n堆石子每次可选择取任意数量石子将一堆分成两堆非空石子 解法SG(x)x%43?x1:x%40?x-1:x5.2 非典型博弈处理Anti-SG游戏走最后一步者输SJ定理当所有子游戏SG0时游戏结束必胜条件总SG≠0且存在某子游戏SG1Every-SG游戏必须操作所有可操作的子游戏需同时考虑SG值和最长/最短游戏时间6. 实战代码模板6.1 Nim游戏判定bool isNimWin(vectorint piles) { int res 0; for(int x : piles) res ^ x; return res ! 0; }6.2 SG函数记忆化搜索unordered_mapint,int sg; int getSG(int x) { if(sg.count(x)) return sg[x]; unordered_setint s; // 添加所有后继状态的SG值 for(int move : possible_moves(x)) { s.insert(getSG(move)); } // 计算mex int mex 0; while(s.count(mex)) mex; return sg[x] mex; }7. 竞赛题目精析7.1 HDU-1847 Good Luck!题意每次可取2^k个石子判断先手胜负解法SG函数周期性SG(x)x%3当x%30时先手必败7.2 POJ-2311 Cutting Game题意剪格子纸游戏剪出1×1者胜解法二维SG函数memo [[-1]*MAX for _ in range(MAX)] def sg(w, h): if memo[w][h] ! -1: return memo[w][h] moves set() for i in range(2, w-1): moves.add(sg(i,h)^sg(w-i,h)) for j in range(2, h-1): moves.add(sg(w,j)^sg(w,h-j)) mex 0 while mex in moves: mex 1 memo[w][h] mex return mex掌握这些核心概念和技巧后面对ACM/OI中的博弈论题目时你就能快速识别游戏类型建立数学模型并设计出高效的制胜策略。记住多练习典型题目培养对游戏特征的敏感度这才是竞赛取胜的关键。