两个玩家轮流做决策，谁先无法操作谁就输——不需要真的把每一种走法都试一遍，几个简单的规律就能判断谁有必胜策略。
这里说的"博弈论"，特指一类组合游戏：两个玩家轮流操作，双方都采取最优策略（不会犯错），游戏没有随机成分（不像掷骰子），信息完全公开（双方都清楚当前局面）。这类问题通常问的是：先手还是后手有必胜策略？不需要真的模拟每一种可能的走法组合，往往能找到一个简单的判断规律。
把游戏的每一种局面分成两类：
| 类别 | 定义 |
|---|---|
| 必败态（P 态） | 轮到你走的时候，你必输——要么已经无法操作（直接判负），要么不管怎么走，都会走到一个必胜态（留给对手一个好局面） |
| 必胜态（N 态） | 轮到你走的时候，你有必胜策略——至少存在一种走法，能走到一个必败态（把烂摊子丢给对手） |
Nim 游戏：有若干堆石子，两人轮流操作，每次可以选任意一堆，从中拿走任意数量（至少 1 个，可以拿走整堆）。轮到某个人时所有堆都是空的，这个人就输了。Nim 游戏有一个非常简洁的结论：
先手必胜 ⟺ 所有石堆数量的异或和（XOR）不等于 0
换句话说：如果所有堆的石子数异或起来结果是 0，当前局面是必败态（轮到谁走谁输，只要对手不失误）；只要异或和不是 0，当前局面就是必胜态。
用两组石堆验证这个结论——[1, 2, 3] 和 [1, 2, 4]：
1 ⊕ 2 ⊕ 3 = 0——先手无论怎么拿，都会把局面变成异或和不为 0 的状态（必胜态），留给对手；对手再用必胜策略把局面变回异或和为 0，如此反复，先手必输。1 ⊕ 2 ⊕ 4 = 7 ≠ 0，先手必胜。必胜走法：对每一堆 i，计算 目标值 = 总异或和 ⊕ 该堆数量，如果目标值小于该堆当前数量，就把这一堆拿到只剩目标值那么多。这里堆 3（数量 4）：目标值 = 7 ⊕ 4 = 3，3 < 4，把堆 3 从 4 拿到 3（拿走 1 个）。拿完之后局面变成 [1,2,3]——正是上面验证过的必败态，先手把烂摊子丢给了对手！Nim 游戏只是众多组合游戏中的一种。SG 函数（Sprague-Grundy 函数）能把"必胜态/必败态"这套二元判断，推广成一个更精细的数值，从而处理更一般的游戏，甚至能把多个独立的子游戏组合在一起分析。
定义 SG(state)：从当前局面出发，能到达的所有下一个局面的 SG 值，取最小的没有出现过的非负整数（这个操作叫 mex，minimum excludant）。SG(state)=0 当且仅当 state 是必败态——这正好和 Nim 游戏"异或和为 0 是必败态"的结论吻合，因为单堆 Nim 游戏里 SG(n) = n（能拿到 0~n-1 中的任意数量，mex 就是 n 本身）。
以"每次最多拿 3 个"的单堆取石子游戏为例（不能不拿，也不能一次拿超过 3 个），计算 SG(0) 到 SG(4)：
| n（剩余石子数） | 能到达的局面 | 能到达局面的 SG 值 | SG(n) = mex{...} |
|---|---|---|---|
| 0 | 无（游戏结束） | {} | 0 |
| 1 | 拿1→0 | {0} | 1 |
| 2 | 拿1→1，拿2→0 | {1, 0} | 2 |
| 3 | 拿1→2，拿2→1，拿3→0 | {2, 1, 0} | 3 |
| 4 | 拿1→3，拿2→2，拿3→1 | {3, 2, 1} | 0 |
SG(4)=0：能到达的局面是 {3,2,1}，这几个数里没有出现 0，所以 mex=0——这说明剩 4 个石子时，当前操作的人是必败的（不管拿1、2还是3个，都会把局面让给一个 SG 值不为 0 的必胜态）。规律是 SG(n) = n mod 4，之后会不断循环。| 1 | // Nim 游戏：直接异或所有堆，判断先手是否必胜 |
| 2 | bool NimFirstWins(const vector<int>& piles) |
| 3 | { |
| 4 | int x = 0; |
| 5 | for (int p : piles) x ^= p; // ★ 全部异或起来 |
| 6 | return x != 0; |
| 7 | } |
| 8 | |
| 9 | // 通用 SG 函数：以"每次最多拿 k 个"的单堆游戏为例 |
| 10 | int sg[MAXN]; |
| 11 | void ComputeSG(int n, int k) |
| 12 | { |
| 13 | for (int i = 0; i <= n; i++) |
| 14 | { |
| 15 | bool vis[MAXN] = {}; // 记录"能到达的局面"里出现过哪些 SG 值 |
| 16 | for (int take = 1; take <= k && take <= i; take++) |
| 17 | vis[ sg[i - take] ] = true; |
| 18 | int m = 0; |
| 19 | while (vis[m]) m++; // ★ mex：找最小的没出现过的非负整数 |
| 20 | sg[i] = m; |
| 21 | } |
| 22 | } |
sg[i] 之后，如果整个游戏由多个独立部分组成，把它们的 sg 值异或起来，结果为 0 就是必败态，否则是必胜态——这一步和 NimFirstWins 里的异或操作是同一个原理，Nim 游戏只是"每堆的 SG 值等于堆里的石子数"这个特殊情形。{0, 1, 3}，mex 不是 4，而是 2（因为 2 没有出现过，是最小的缺失值）。跳过 2 直接从 {0,1,3} 推出 mex=4 是常见的计算错误。