博弈论研究多个理性决策者之间的策略互动。在算法竞赛中，Nim 游戏、SG 函数和 Sprague-Grundy 定理是核心工具，能判定组合游戏的必胜/必败态。
一、组合游戏基本模型
Mermaid · 渲染中（下方为源码）
graph TD A[组合游戏] --> B[Nim和] B --> C[SG函数] C --> D[Sprague-Grundy]
- 两人轮流操作
- 信息完全公开
- 无法操作者输（Normal Play）
- 有限步内必结束（无平局）
二、必胜态与必败态
- P 态（Previous/必败）：当前玩家必败
- N 态（Next/必胜）：当前玩家必胜
规则：
- 终态（无法操作）→ P 态
- 能到达 P 态 → N 态
- 所有后继都是 N 态 → P 态
三、Nim 游戏
n 堆石子，每堆 aᵢ 个，两人轮流从一堆取任意多个，取完者胜。
Bouton 定理
先手必胜 ⟺ a₁ ⊕ a₂ ⊕ ... ⊕ aₙ ≠ 0
boolean firstPlayerWins(int[] piles) {
int xor = 0;
for (int pile : piles) xor ^= pile;
return xor != 0;
}证明思路
- 终态全 0，异或 = 0（P 态）
- 异或 ≠ 0 时，一定存在一步使异或变为 0
- 异或 = 0 时，任何操作都会使异或变为 ≠ 0