组合游戏博弈论深入解析：Sprague-Grundy 定理

在上一篇文章中，我们已经探讨了如何使用 Grundy 数（也称为 Nim 和）来分析简单的 impartial games（公平组合游戏）。我们了解到，通过计算 Grundy 数，我们可以在不实际进行游戏的情况下预测游戏的获胜者。这就像拥有了预知未来的水晶球一样神奇。但是，现实中的游戏往往比单一的 Nim 游戏要复杂得多。如果我们面对的不是一堆石子，而是多个独立的游戏同时进行呢？

这正是 Sprague-Grundy 定理大显身手的地方。在本篇文章中，我们将深入探讨这一核心定理，看看它是如何将复杂的组合游戏拆解并化简的。我们将通过详细的步骤分析、实际的代码示例以及性能优化的探讨，带你彻底掌握这一组合游戏博弈论的基石。

什么是 Sprague-Grundy 定理？

假设我们现在有一个复杂的组合游戏，它实际上是由多个独立的子游戏组成的。例如，桌面上有三堆不同的石子，或者棋盘上有几个互不干扰的区域。Sprague-Grundy 定理告诉我们，每一个这样的子游戏等价于一个特定大小的 Nim 堆（即一个单堆 Nim 游戏）。

定理的核心陈述：

如果一个组合游戏由多个子游戏组成，那么整个游戏的 Grundy 数（或称 Nim 和）等于所有子游戏 Grundy 数的异或和（XOR Sum）。

• 如果异或和不为 0： 当前行动的玩家（先手）处于必胜位置，只要他不犯错，就一定能赢。

n* 如果异或和为 0： 当前行动的玩家处于必败位置，无论他怎么做，只要对手采取最优策略，他必输无疑。

这个定理的厉害之处在于，它将“组合游戏”完全转化为了我们熟悉的“Nim 游戏”。只要我们能算出每个独立部分的 Grundy 数，剩下的就是简单的二进制异或运算了。

Sprague-Grundy 定理的应用流程

在解决实际问题时，我们可以遵循一套标准化的流程。这不仅仅是理论推导，更是我们在编写算法解题时的核心逻辑。

#### 第一步：拆解游戏

这是最关键的一步。我们需要观察游戏规则，判断这个游戏是否由多个独立的子游戏组成。如果是，我们要将其清晰地拆分开来。

• 例子： 在经典的 Nim 游戏中，每一堆石子就是一个独立的子游戏。
• 例子： 在棋类游戏中，如果棋盘被分割成互不影响的部分，那么每一部分就是一个子游戏。

#### 第二步：计算子游戏的 Grundy 数

针对每一个独立的子游戏，我们需要计算其在当前状态下的 Grundy 数。这一步通常涉及动态规划（DP）和 Mex（Minimum Excluded Set，最小未包含集）运算。

• Mex 算法： 一个集合的 Mex 是指不属于该集合的最小非负整数。例如，Mex({0, 1, 3}) = 2。

#### 第三步：计算全局异或和

将所有计算出的子游戏 Grundy 数进行按位异或（XOR）。这里需要注意，异或运算满足交换律和结合律，所以顺序不影响结果。

#### 第四步：判断胜负

根据上一步的异或和结果进行判断：

• 异或和 ≠ 0： 先手必胜。你的策略是走出一步棋，使得剩下的局面异或和变为 0，把“烂摊子”留给对手。
• 异或和 = 0： 先手必败。无论你怎么走，都会破坏这个平衡，让对手获得必胜局面。

实战演练：一个具体的游戏示例

让我们通过一个稍微修改过的 Nim 游戏来实战一下。

游戏规则：

• 游戏开始时有 3 堆石子，数量分别为 3、4 和 5。
• 在每一回合中，玩家可以从任意一堆中拿取石子，但每次最多只能拿 3 颗（至少拿 1 颗）。
• 拿到最后一颗石子的玩家获胜。
• 假设双方都采取最优策略，问：先手会赢吗？

#### 分析过程

1. 拆解子游戏：

显然，第 1 堆、第 2 堆和第 3 堆是三个独立的子游戏。

2. 计算 Grundy 数：

因为每堆拿走的规则是一样的（1, 2, 或 3 颗），我们可以先计算从 0 到 5 个石子的 Grundy 数。假设 $G(n)$ 是 $n$ 个石子的 Grundy 数。

• $G(0) = 0$ (终局)
• $G(1) = mex({G(0)}) = mex({0}) = 1$
• $G(2) = mex({G(1), G(0)}) = mex({1, 0}) = 2$
• $G(3) = mex({G(2), G(1), G(0)}) = mex({2, 1, 0}) = 3$
• $G(4) = mex({G(3), G(2), G(1)}) = mex({3, 2, 1}) = 0$ (这就是关键！不能到达 0，所以回到 0)
• $G(5) = mex({G(4), G(3), G(2)}) = mex({0, 3, 2}) = 1$

所以，我们得到：

• 第 1 堆 (3 颗) 的 Grundy 数为 3。
• 第 2 堆 (4 颗) 的 Grundy 数为 0。
• 第 3 堆 (5 颗) 的 Grundy 数为 1。

3. 计算全局异或和：

$$Total = G(3) \oplus G(4) \oplus G(5)$$

$$Total = 3 \oplus 0 \oplus 1$$

$$Total = 2$$

4. 结论：

因为异或和 $2

eq 0$，所以先手玩家必胜。先手只需要通过一步操作，使得剩下的异或和变为 0 即可。

代码实现与深度解析

理论讲完了，让我们用 C++ 来实现这个逻辑。我们会编写一个程序，不仅能判断输赢，还能计算出每一堆石子对应的 Grundy 数。

#### 1. 核心辅助函数：Mex 计算

首先，我们需要一个工具来计算 Mex。这是计算 Grundy 数的基础。

// 计算集合中所有值的 Mex (Minimum Excluded Value)
// Mex 是不属于该集合的最小非负整数
int calculateMex(unordered_set Set) {
    int Mex = 0;
    
    // 只要 Mex 存在于集合中，就尝试下一个整数
    while (Set.find(Mex) != Set.end())
        Mex++;
        
    return Mex;
}

#### 2. 动态规划计算 Grundy 数

对于受限 Nim（比如只能拿 1-3 颗），我们可以使用递推公式。这是一个自底向上的过程。

// 计算 n 个石子位置的 Grundy 数
// pilesSize: 当前这堆石子的数量
// moves: 允许的移动步长数组，例如 {1, 2, 3}
// limit: 允许拿取的最大数量
int calculateGrundy(int n, int Grundy[], int limit) {
    // 初始化基本情况
    Grundy[0] = 0; // 0 个石子是必败点，Grundy 为 0
    Grundy[1] = 1; // 拿走 1 个变成 0
    
    // 如果 n 很小，直接返回已计算好的值
    if (n <= 1) return Grundy[n];

    // 遍历计算从 2 到 n 的每个状态
    for (int i = 2; i <= n; i++) {
        unordered_set Set; // 存储当前状态可达的所有 Grundy 数
        
        // 尝试所有可能的拿取数量 (1 到 limit)
        for (int j = 1; j = 0) {
                Set.insert(Grundy[i - j]);
            }
        }
        
        // 计算 Mex 并存入数组
        Grundy[i] = calculateMex(Set);
    }
    
    return Grundy[n];
}

#### 3. 完整的判断逻辑

接下来，我们将所有部分整合起来。我们将初始化 Grundy 数组，计算异或和，并输出结果。

#include 
#include 
#include 

using namespace std;

// 定义玩家常量，提高代码可读性
#define PLAYER1 1
#define PLAYER2 2

// 最大可能的堆大小，用于 DP 数组初始化
const int MAX_PILE_SIZE = 100005;

int main() {
    // 示例输入：3 堆石子，数量分别为 3, 4, 5
    int piles[] = {3, 4, 5};
    int n = sizeof(piles) / sizeof(piles[0]);
    int maxRemove = 3; // 每次最多拿 3 颗

    // 初始化 Grundy 数组，-1 表示未计算
    int Grundy[MAX_PILE_SIZE];
    memset(Grundy, -1, sizeof(Grundy));
    
    // 找出最大的堆的大小，作为 DP 计算的上界
    int maxPile = 0;
    for (int i = 0; i  maxPile) maxPile = piles[i];
    }

    // 预处理计算所有可能用到的 Grundy 数
    // 这样如果多次查询，效率极高
    calculateGrundy(maxPile, Grundy, maxRemove);

    // 计算全局异或和
    int xorSum = Grundy[piles[0]];
    for (int i = 1; i < n; i++) {
        xorSum = xorSum ^ Grundy[piles[i]];
    }

    // 判断并输出结果
    cout << "--- 游戏分析结果 ---" << endl;
    for (int i = 0; i < n; i++) {
        cout << "堆 " << i + 1 << " (石子数: " << piles[i] << ") 的 Grundy 数是: " << Grundy[piles[i]] << endl;
    }
    cout << "全局异或和: " << xorSum << endl;

    if (xorSum != 0) {
        cout << "结论: 因为异或和不为 0，先手玩家 将获胜。" << endl;
    } else {
        cout << "结论: 因为异或和为 0，后手玩家 将获胜。" << endl;
    }

    return 0;
}

常见错误与性能优化建议

在编写这类博弈算法时，作为经验丰富的开发者，我们要注意一些潜在的坑点。

#### 1. 状态空间的初始化

如果你使用全局数组来记忆化 Grundy 数，务必确保在程序开始时正确初始化。对于像 $10^6$ 这样的大数据范围，使用 INLINECODEf6c16fb5 代替原生数组可能更安全，或者使用 INLINECODE97e87dea 快速清零。不过，在上述代码中，我们因为需要区分“未计算”的状态，所以用 -1 初始化。

#### 2. 递归深度与栈溢出

上面的 calculateGrundy 写法是迭代的，这是推荐的做法。如果你将其改写为递归形式（不带记忆化），对于大数字（如 $N=10000$），程序会瞬间崩溃或超时。永远不要在没有记忆化的情况下进行博弈状态递归。

#### 3. 优化 Mex 计算

计算 Mex 是整个算法中最耗时的部分（对于每个状态都要遍历集合）。

• 布尔数组优化： 如果规则允许移动的状态数很少（例如只能拿 1, 2, 3），那么 INLINECODE76b9098d 中最多也就几个元素。但是如果规则复杂，Mex 可能很大。此时我们可以维护一个全局的布尔数组 INLINECODEed79a4e7，在计算完一个 INLINECODEc9fb2a9f 后，不仅存入 DP 表，还更新 INLINECODE74e23eee 状态。对于稠密图，这能将复杂度从 $O(N^2)$ 降低很多。

#### 4. 不要盲目计算全部状态

如果 $N$ 非常大（比如 $10^9$），你就不能开数组了。这时你需要寻找 Grundy 数的数学规律（通常是循环的周期性，比如 0, 1, 2, 3, 0, 1, 2, 3…）。这就是所谓的“SG 找规律”。

实际应用场景扩展

Sprague-Grundy 定理不仅仅用于拿石子游戏。

• 棋类游戏拆分： 像围棋、五子棋甚至国际象棋的某些残局，如果棋盘被切断成互不干扰的部分，每一部分就是一个子游戏。
• 图博弈： 给定一张有向图，棋子放在某个节点上，移动是指沿边走一步。这种游戏也可以用 SG 函数解决，每个节点的 SG 值等于其所有后继节点 SG 值的 Mex。
• 删边游戏： 两人在图上轮流删边，删掉不连通图的一边的人输。这类问题也可以转化为 SG 函数求解。

总结

在这篇文章中，我们深入学习了 Sprague-Grundy 定理。这是组合游戏博弈论中最强大的工具之一。通过这四个步骤——拆解、计算 Grundy 数、计算异或和、判断胜负——我们可以解决几乎所有看似复杂的 impartial game。

关键在于将复杂问题分解为子问题，并利用 Mex 概念量化每个状态的“胜负价值”。希望这些代码示例和优化技巧能帮助你在算法竞赛或实际项目中游刃有余。在下一篇文章中，我们将进一步探讨如何利用 SG 定理解决更具挑战性的题目。