博弈论算法精讲：从公平组合游戏到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函数递归定义：
- 终止状态SG=0
- SG(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定理的威力
对于组合游戏G=G₁+G₂+...+Gₙ：
SG(G) = SG(G₁) ⊕ SG(G₂) ⊕ ... ⊕ SG(Gₙ)其中⊕表示异或运算。当且仅当SG(G)≠0时先手有必胜策略。
4. 经典博弈模型实战
4.1 Nim游戏变种
标准Nim：
- 各堆石子数异或和为0时先手必败
- 否则先手可通过调整使异或和为0
Bash博弈（限定每次取1-m个）：
- 当(m+1)整除总数时先手必败
- 策略：保持每次取完后剩余数为(m+1)的倍数
Wythoff博弈（两堆石子）：
- 必败态为(⌊kφ⌋, ⌊kφ²⌋)，其中φ=(1+√5)/2
- 涉及黄金分割的奇妙数学性质
4.2 斐波那契博弈
- 每次取数不超过前一次的2倍
- 当石子数为斐波那契数时先手必败
- 齐肯多夫定理的应用典范
5. 竞赛高级技巧
5.1 游戏分解策略
复杂游戏往往能分解为独立子游戏：
- 识别游戏中的独立组件
- 计算各组件SG值
- 异或合并得到总SG值
例题：有n堆石子，每次可选择：
- 取任意数量石子
- 将一堆分成两堆非空石子 解法：SG(x)=x%4==3?x+1:x%4==0?x-1:x
5.2 非典型博弈处理
Anti-SG游戏（走最后一步者输）：
- SJ定理：当所有子游戏SG=0时游戏结束
- 必胜条件：总SG≠0且存在某子游戏SG>1
Every-SG游戏：
- 必须操作所有可操作的子游戏
- 需同时考虑SG值和最长/最短游戏时间
6. 实战代码模板
6.1 Nim游戏判定
bool isNimWin(vector<int>& piles) { int res = 0; for(int x : piles) res ^= x; return res != 0; }6.2 SG函数记忆化搜索
unordered_map<int,int> sg; int getSG(int x) { if(sg.count(x)) return sg[x]; unordered_set<int> 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%3==0时先手必败
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中的博弈论题目时，你就能快速识别游戏类型，建立数学模型，并设计出高效的制胜策略。记住多练习典型题目，培养对游戏特征的敏感度，这才是竞赛取胜的关键。