第 8.5 章：博弈论入门

博弈论题目在竞赛中乍看像"脑筋急转弯"，但背后有一套完整的数学理论。它们在 USACO Gold / Platinum 和国内 NOIP 中都以"两人轮流操作，问先手是否必胜"的形式出现，而几乎所有这类题目都归结为同一个工具：异或（XOR）。

学习目标：

• 理解公平组合游戏的定义
• 掌握必胜 / 必败状态的三条判定定理
• 掌握 Nim 和定理及其完整证明
• 掌握 SG 函数与 Sprague–Grundy 定理，并能打表求解

8.5.0 开篇题：Nim 游戏

问题： 桌上有 N 堆石子，第 i 堆有 aᵢ 颗。Alice 和 Bob 轮流行动，Alice 先手。每一回合，当前玩家任选一堆，从中取走至少 1 颗、至多整堆的石子。取走最后一颗石子的玩家获胜。给定初始局面，问 Alice 是否有必胜策略。

朴素思路：逐堆 DP 会爆炸

最直接的暴力是画出博弈图：把每个局面 (a₁, a₂, ..., aₙ) 看作一个节点，从每个局面连边到它一步能到达的所有局面，然后从终局倒推每个节点是必胜还是必败。

哪怕只对"堆的大小"做记忆化搜索，状态总数也是所有堆大小的乘积级别——O(∏aᵢ)。三堆各 1000 颗就是 10⁹ 个状态，十堆各 10⁹ 颗直接天文数字。逐堆信息不足以判断胜负，我们需要的是一个只看全局的量。这就是第 8.5 章的主角：Nim 和。

8.5.1 公平组合游戏与必败状态

第 8.5 章讨论的都是公平组合游戏（Impartial Game），它满足三个条件：

1. 两个人轮流行动，双方都能看到完整的局面（完全信息）；
2. 在某个局面下能做什么操作只与局面有关，与玩家是谁无关（双方地位完全平等）；
3. 游戏一定会在有限步内结束，且没有平局（通常以"无法行动者输"告终）。

⚠️ 国际象棋、五子棋都不是公平组合游戏——你不能操作对方的棋子。Nim 及其绝大多数变形都是。

把博弈图的每个节点分类：

• 必胜状态（N-position）：当前行动者必胜的局面；
• 必败状态（P-position）：当前行动者必败的局面。

三条定理构成了所有分析的基础：

定理 1： 没有后继状态的状态是必败状态。 （游戏无法进行，当前玩家直接输。）

定理 2： 一个状态是必胜状态，当且仅当它至少存在一个必败的后继状态。 （把必败局面扔给对手，对手就输了。）

定理 3： 一个状态是必败状态，当且仅当它的所有后继状态都是必胜状态。 （无论怎么走，都把必胜局面送给对手。）

若博弈图是有向无环图（公平组合游戏保证如此），按这三条定理沿拓扑序倒推，就能 O(状态数 + 边数) 标出每个状态的胜负——这正是 8.5.0 中"会爆炸"的暴力。理论正确，但我们需要快得多 的判定。

8.5.2 Nim 和定理

定义 Nim 和 = 所有堆大小的按位异或：

$$a_1 \oplus a_2 \oplus \cdots \oplus a_n$$

Nim 和定理（Bouton 定理）： Nim 游戏中，当前局面为必败状态，当且仅当 Nim 和为 0；Nim 和非零则必胜。

完整证明

我们证明以下三条引理（它们恰好对应"必胜/必败"的三条判定定理）：

引理 1（终局）： 没有后继的状态只有全零局面 (0, 0, ..., 0)，此时 Nim 和为 0。

引理 2（非零 → 能走到零）： 若当前 Nim 和为 k ≠ 0，则存在一步合法操作，使操作后 Nim 和变为 0。

证明： 设 k 的二进制最高位 1 在第 d 位。由异或的定义，所有 aᵢ 中第 d 位为 1 的堆有奇数个——奇数 ≥ 1，故至少存在一堆 aᵢ，其第 d 位为 1。对这堆，考察 aᵢ ⊕ k：

• 第 d 位上，aᵢ 和 k 都是 1，故 aᵢ ⊕ k 的第 d 位为 0，而 k 的更高位都是 0、不产生影响，所以 aᵢ ⊕ k < aᵢ（最高变化位从 1 变 0，必然变小）；
• 把 aᵢ 改成 aᵢ′ = aᵢ ⊕ k（取走 aᵢ − aᵢ′ 颗，为正数，合法），新的 Nim 和为

$$(a_1 \oplus \cdots \oplus a_i' \oplus \cdots \oplus a_n) = (a_1 \oplus \cdots \oplus a_n) \oplus k = k \oplus k = 0.$$

引理 3（零 → 只能走到非零）： 若当前 Nim 和为 0，则任何一步合法操作都会使 Nim 和变为非零。

证明： 一次操作只改变某一堆，把 aᵢ 改为 aᵢ′ ≠ aᵢ。若操作前后 Nim 和都是 0，则

$$a_1 \oplus \cdots \oplus a_i \oplus \cdots \oplus a_n = a_1 \oplus \cdots \oplus a_i' \oplus \cdots \oplus a_n$$

两边同时异或除去第 i 堆的其余部分，得 aᵢ = aᵢ′，矛盾。∎

汇总： Nim 和为 0 的局面，每一步都被迫走到非零局面（引理 3），且对手总能再走回零局面（引理 2）；由于游戏有限步结束，最终停在"全零 Nim 和为 0"的终局上的，正是那个一直面对零局面的玩家——他输。所以 Nim 和为 0 ⇔ 必败。

二进制位表的直觉

为什么偏偏是异或？看三堆 (3, 4, 5) 的二进制竖式：

每一列（每个二进制位）上 1 的个数是奇是偶，就是异或那一位的值。Nim 和为 0 意味着每个二进制位上 1 的个数都是偶数——这样的局面非常"对称"，无论先手破坏哪一位的奇偶性，后手都能在同一堆或另一堆把它补回来，最终把对称一路保持到全零。而非零局面里，最高非零位上 1 出现奇数次，先手恰好把那堆削掉高位、一步制造出全局对称——必胜的一手就在那里。

💡 对 (3, 4, 5)：XOR = 2 ≠ 0，先手必胜。按引理 2，k = 2，最高位是 2¹ 位；3 的该位为 1，把 3 改成 3 ⊕ 2 = 1，即从第一堆取走 2 颗，留给对手 (1, 4, 5)，XOR = 0。

8.5.3 SG 函数

Nim 是"每次任取"的特例。当规则变得花哨——比如"每次只能取斐波那契数颗"——直接的胜负判定失效，我们需要更一般的工具。

有向图游戏

有向图游戏：在一张有向无环图上放一枚棋子，双方轮流沿一条有向边移动棋子，无法移动者输。绝大部分公平组合游戏都能转成这个模型（局面 = 节点，操作 = 边）。

mex 与 SG 的定义

mex（minimum excludant，最小排除值）：

$$\operatorname{mex}(S) = \text{不属于 } S \text{ 的最小非负整数}$$

例如 mex({0, 2, 4}) = 1，mex({1, 2}) = 0，mex(∅) = 0。

对状态 x 及其全部后继 y₁, y₂, ..., yₖ，定义 SG 函数：

$$\operatorname{SG}(x) = \operatorname{mex}{\operatorname{SG}(y_1), \operatorname{SG}(y_2), \ldots, \operatorname{SG}(y_k)}$$

无后继状态（终局）的 SG 值 = mex(∅) = 0。

关键性质： SG(x) = 0 ⇔ x 是必败状态。

• 若 SG(x) = 0，说明 0 不在后继 SG 集合里，即不存在必败的后继——所有后继都是必胜的，正是判定定理 3；
• 若 SG(x) > 0，说明后继 SG 集合包含 0..SG(x)−1 的每个值，特别地存在 SG 为 0 的必败后继——正是判定定理 2。

注意 SG 函数比"胜负"记录了更多信息：SG(x) = 3 不仅说明 x 必胜，还说明从 x 一步能到达 SG 为 0、1、2 的状态——这个"能到达哪些等级"的信息正是组合多个游戏时需要的。

两个例子

例 1：Nim 的一堆。 把"一堆 x 颗石子，任取若干"看作有向图游戏：节点 x 连向所有 y < x。归纳易证 SG(x) = x：节点 x 的后继恰好覆盖 SG 值 0, 1, ..., x−1，故 mex = x。

例 2：一堆石子，每次取 1~3 颗。 节点 x 连向 x−1, x−2, x−3：

SG 序列是 0, 1, 2, 3, 0, 1, 2, 3, ... 以 4 为周期循环——这正是经典的"巴什博弈"，x ≡ 0 (mod 4) 时必败，与我们熟知的结论一致。

8.5.4 SG 定理（Sprague–Grundy 定理）

定理： 把 n 个互相独立的有向图游戏放在一起，每回合任选一个游戏走一步，无法行动者输。设各游戏当前状态的 SG 值为 SG(s₁), ..., SG(sₙ)，则：

整个组合游戏先手必胜 ⇔ SG(s₁) ⊕ SG(s₂) ⊕ ⋯ ⊕ SG(sₙ) ≠ 0。

而且，组合游戏的 SG 值恰好等于这个异或和。

证明思路（归纳法）： 设 X = SG(s₁) ⊕ ⋯ ⊕ SG(sₙ)。类比 Nim 和定理的两条引理：

1. 若所有 sᵢ 都无后继，则各 SG 均为 0，X = 0，必败。✓
2. 若 X ≠ 0，仿照引理 2：取最高位，找到某个 SG(sᵢ)，其该位为 1，且 SG(sᵢ) ⊕ X < SG(sᵢ)。由于 sᵢ 的后继 SG 集合包含 0..SG(sᵢ)−1 的每个值，必存在后继 sᵢ′ 恰好满足 SG(sᵢ′) = SG(sᵢ) ⊕ X。走到 sᵢ′ 后新的异或和为 0。✓
3. 若 X = 0，任一步只改变一个 sᵢ 的 SG 值（mex 保证 SG(sᵢ′) ≠ SG(sᵢ)，因为后继集合不含自身值……严格说：若 SG(sᵢ′) = SG(sᵢ)，与异或为零保持不变矛盾，同引理 3），异或和必然变为非零。✓

三条引理与 Nim 和定理的证明逐字对应——SG 定理正是把任意公平组合游戏"折算"成了一堆等价的 Nim 石子：状态 sᵢ 折算成 SG(sᵢ) 颗石子的 Nim 堆。这就是为什么 SG(x) = x 的 Nim 是万物的"度量衡"。

使用 SG 定理的完整流程

1. 把游戏拆成若干独立子游戏（Nim 的各堆天然独立）；
2. 对每个子游戏，预处理出所有状态的 SG 值（通常是打表找规律，或直接 O(值域 × 转移数) 递推）；
3. 把各子游戏当前状态的 SG 值异或起来：非零先手必胜，为零先手必败。

8.5.5 实战题 1：Nim 游戏

题意： 读入 N 堆石子的大小，输出先手（Alice）是否必胜。1 ≤ N ≤ 10⁵，1 ≤ aᵢ ≤ 10⁹。

直接套 Nim 和定理：

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int nimSum = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        nimSum ^= a;
    }
    cout << (nimSum != 0 ? "Alice" : "Bob") << '\n';
    return 0;
}

验证：

• (2, 5, 4)：2 ⊕ 5 ⊕ 4 = 011 ⊕ 101 ⊕ 100 = 010 ≠ 0 → Alice 必胜 ✓（按引理 2 的构造：k = 2，把 3 改成 3 ⊕ 2 = 1，留给对手 (1, 5, 4)，XOR = 0）
• (1, 1, 1)：1 ⊕ 1 ⊕ 1 = 1 ≠ 0 → Alice 必胜 ✓（先手取光一堆，剩下两堆各 1 颗，之后镜像跟随，后手必胜）
• (3, 3)：3 ⊕ 3 = 0 → Bob 必胜 ✓（后手在另一堆镜像先手的每一步）
• (7)：7 ≠ 0 → Alice 必胜 ✓（一次全取）

复杂度 O(N)。

8.5.6 实战题 2：Fibonacci 取石子（SG 打表）

题意（hdu 1848）： 三堆石子，分别有 m、n、p 颗。每次任选一堆，从中取走斐波那契数颗（1, 2, 3, 5, 8, 13, ... 颗，不能不取）。取到最后一颗的赢。问先手是否必胜。1 ≤ m, n, p ≤ 1000。

规则不再是"任取若干"，Nim 定理不能直接用——这正是 SG 函数登场的时刻：

1. 每一堆是一个独立的子游戏；
2. 对"一堆 x 颗、每次取斐波那契数颗"打表算 SG(x)；
3. 三堆 SG 值异或，非零先手必胜。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;

int sg[MAXN + 1];

int main() {
    // 预处理斐波那契数（去掉 1 的重复项: 1, 2, 3, 5, 8, ...）
    vector<int> fib;
    int a = 1, b = 2;
    while (a <= MAXN) {
        fib.push_back(a);
        int c = a + b;
        a = b;
        b = c;
    }

    // SG 打表: sg[x] = mex{ sg[x - f] : f 是斐波那契数且 f <= x }
    vector<int> vis(MAXN + 2);
    for (int x = 1; x <= MAXN; x++) {
        for (int i = 0; i <= x; i++) vis[i] = 0;          // 只需清到可能的最大 SG 值
        for (int f : fib)
            if (f <= x) vis[sg[x - f]] = 1;
        int mex = 0;
        while (vis[mex]) mex++;
        sg[x] = mex;
    }

    int m, n, p;
    while (cin >> m >> n >> p && (m || n || p)) {
        cout << ((sg[m] ^ sg[n] ^ sg[p]) ? "Fibo\n" : "Nacci\n");
    }
    return 0;
}

打表结果核对（x = 1..20）：

x  : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
SG : 1 2 3 0 1 2 3 4 5 0  1  2  3  0  1  2  3  4  5  0

手算验证前几项：

• SG(0) = 0（终局）；
• SG(1) = mex{SG(0)} = mex{0} = 1；
• SG(2) = mex{SG(1), SG(0)} = mex{1, 0} = 2；
• SG(3) = mex{SG(2), SG(1), SG(0)} = mex{2, 1, 0} = 3；
• SG(4)：可取 1、2、3 颗，后继 SG 为 {3, 2, 1}，mex = 0（4 颗是必败点！）；
• SG(5)：可取 1、2、3、5 颗，后继 SG 为 {SG(4), SG(3), SG(2), SG(0)} = {0, 3, 2, 0}，mex = 1。

用独立的暴力博弈 DP（直接判每堆 x 颗先手胜负）交叉验证：x = 4, 10, 14, 20 时 SG 为 0，暴力同样判定这四个规模为先手必败 ✓。

样例核对：

• (1, 2, 3)：SG 异或 = 1 ⊕ 2 ⊕ 3 = 0 → 输出 Nacci（先手必败）✓
• (1, 1, 1)：1 ⊕ 1 ⊕ 1 = 1 → Fibo ✓
• (2, 4, 8)：2 ⊕ 0 ⊕ 4 = 6 → Fibo ✓

打表复杂度 O(MAXN × |fib|)，单组查询 O(1)。

8.5.7 ⚠️ 常见错误

1. 必胜/必败判断写反。 记牢口诀：XOR ≠ 0 先手赢，XOR = 0 先手输。写成"异或为零必胜"是最常见的低级失误——建议写代码前先拿 (3,3) 这类镜像局面对照："两堆一样多，先手必败"，而 3 ⊕ 3 = 0。
2. mex 忘记从 0 开始。 mex 是"最小非负整数"，mex(∅) = 0，mex({1,2}) = 0。若习惯性从 1 开始找，所有 SG 值都会偏小甚至全错。打表时先算 SG(小值) 并和手算对一遍。
3. 打表数组忘记每轮清空 / 清空范围不够。 mex 的候选值最多到"后继个数"，但保险起见清空到 MAXN 或使用带时间戳的写法（每个 x 用一个独立标记）。上面代码按 0..x 清空是足够的，因为 SG(x) ≤ x。
4. Anti-Nim（反常 Nim）不能直接套 SG / Nim 和。 "取最后一颗的人输"的反常规则破坏了公平组合游戏的"无法行动者输"前提（终局的胜负翻转了）。必胜条件需要另行讨论（大致为：异或为 0 且所有堆大小 ≤ 1，或异或非零且存在堆 > 1），SG 定理在这里不适用。见到 misère 规则要停下来重新分析，不要无脑 XOR。
5. 子游戏不独立就异或。 SG 定理要求各子游戏互不影响。若一步操作会同时改变多个"堆"的状态（如分堆游戏把一堆拆成两堆），必须把"分堆后的两个子堆"的 SG 异或作为这一个转移的贡献，再对转移集合取 mex——而不是简单地把所有堆异或完事。

8.5.8 总结

解题流程：识别公平组合游戏 → 拆成独立子游戏 → 打表/递推 SG → 异或判胜负。

8.5.9 练习

🟢 简单

8.5-E1. 裸 Nim N 堆石子，轮流任取一堆的任意正整数颗，取最后一颗的赢。读入 N 与各堆大小，输出 First（先手必胜）或 Second。 数据规模： 1 ≤ N ≤ 10⁵，1 ≤ aᵢ ≤ 10⁹。

🟡 中等

I-M1. 阶梯 Nim N 级台阶，第 i 级上有 aᵢ 颗石子。每次可以把某一台阶上的任意正整数颗石子往下移一级（第 1 级移到地面）。当所有石子都在地面时游戏结束，让对手无法移动的人赢（即移动最后一颗石子到地面的人赢）。判断先手胜负。 数据规模： 1 ≤ N ≤ 10⁵，0 ≤ aᵢ ≤ 10⁹。

🔴 困难

I-H1. Anti-Nim（反常 Nim） N 堆石子，规则同 Nim，但取走最后一颗石子的人输。给出先手必胜的完整判定条件，并证明。 数据规模： 1 ≤ N ≤ 10⁶，1 ≤ aᵢ ≤ 10⁹。

延伸阅读

第 8.5 章只覆盖了公平组合游戏的入门。非公平博弈（Partizan Game，双方操作集不同，如剪纸类博弈）、Anti-Nim 的系统理论、以及 Nim 变体（阶梯 Nim、Moore's Nim、Green Hackenbush 等）超出了本书范围，感兴趣的读者可参考 OI-wiki 博弈论 及其引用资料继续深入。