在上一篇文章中，我们探讨了组合博弈论的基础概念以及经典的尼姆游戏。如果你曾思考过这样一个问题："除了尼姆游戏，我们如何用一套通用的数学工具来解决任何看似复杂的公平游戏？"那么这篇文章正是为你准备的。
今天，我们将深入探讨组合博弈论中的核心概念——Grundy 数（Grundy Numbers），也被称为尼姆值。掌握了这个概念，你将拥有一把万能钥匙，能够将各种各样的公平游戏转化为简单的数字比较问题。在开始计算 Grundy 数之前，我们需要先掌握一个被称为 Mex（最小排除值） 的基础工具。让我们从 Mex 开始，一步步揭开博弈论的神秘面纱。
什么是 Mex？
Mex 是 "Minimum excludant" 的缩写，中文意为 "最小排除值"。听起来很高深，其实它的定义非常简单直观：
> 定义：对于一个给定的非负整数集合，Mex 是指不属于该集合的最小非负整数。
#### Mex 的计算示例
让我们看几个简单的例子来直观理解这个概念：
- 如果集合 $S = \{\}$ (空集)，那么 $Mex(S) = 0$。因为 0 是最小的非负整数，且不在空集中。
- 如果集合 $S = \{0\}$，那么 $Mex(S) = 1$。因为 0 在集合中，1 是不在集合中的最小非负整数。
- 如果集合 $S = \{0, 1, 2\}$，那么 $Mex(S) = 3$。
- 如果集合 $S = \{1, 2, 4\}$，那么 $Mex(S) = 0$。注意，0 不在集合中，它是最小的。
为什么 Mex 这么重要？
在博弈论中，Mex 的作用是定义一个状态的 "Grundy 数"（或称 "尼姆值"）。我们计算一个游戏状态的 Grundy 数，本质上是在计算该局面的 "等价尼姆堆大小"。Sprague-Grundy 定理告诉我们，每一个公平游戏状态都等价于一个特定大小的尼姆堆，而这个大小就是由下一步所有可能状态的 Grundy 数的 Mex 决定的。
如何计算 Grundy 数？
计算 Grundy 数的过程本质上是一个基于递归和记忆化搜索的过程。其核心定义如下：
- 终止状态：如果当前局面是一个必败态（即轮到谁谁就输，没有任何可行的移动），那么该状态的 Grundy 数为 0。
- 递归步骤：对于任何其他状态，我们需要找出所有可能的下一步局面（即所有合法的移动），计算出这些下一步局面的 Grundy 数集合。当前状态的 Grundy 数就是这个集合的 Mex。
#### 示例 1：简单的单堆尼姆游戏变种
游戏规则：
游戏开始时有一堆 $n$ 个石子。轮到的玩家可以拿走 任意正数个 石子（从 1 个到全部）。最后行动的玩家获胜。
让我们手动计算几个小的 $n$ 值，看看规律：
- 当 $n = 0$ 时：没有石子可拿，当前玩家无法操作，直接输掉。这是一个必败态。
* $Grundy(0) = 0$
- 当 $n = 1$ 时：玩家只有一个选择，拿走 1 个石子。剩下的局面是 $n=0$（Grundy数为 0）。
* 下一步状态的集合是 $\{0\}$。
* $Mex(\{0\}) = 1$。
* 所以，$Grundy(1) = 1$。
- 当 $n = 2$ 时：玩家可以拿走 1 个或 2 个石子。
* 如果拿 1 个，剩 1 个（Grundy数为 1）。
* 如果拿 2 个，剩 0 个（Grundy数为 0）。
* 下一步状态的 Grundy 数集合是 $\{0, 1\}$。
* $Mex(\{0, 1\}) = 2$。
* 所以，$Grundy(2) = 2$。
- 当 $n = k$ 时：玩家可以拿走 $1$ 到 $k$ 个石子。剩下的石子数可能是 $0, 1, …, k-1$。
* 下一步状态的 Grundy 数集合是 $\{0, 1, 2, …, k-1\}$。
* $Mex(\{0, 1, 2, …, k-1\}) = k$。
* 所以，$Grundy(k) = k$。
结论：对于这个简单的游戏，Grundy 数等于石子的数量。这验证了我们的直觉：它就是一个标准的尼姆游戏。
#### 代码实现：简单的单堆游戏
我们可以用递归非常优雅地实现这个逻辑。核心在于 INLINECODEd469d7af 函数，它会递归地求解所有子状态，然后调用 INLINECODEe1194b06 来得到当前状态的值。
C++ 实现
#include
#include
#include
using namespace std;
// 计算一个非负整数集合的 Mex (最小排除值)
int calculateMex(const unordered_set& set) {
int mex = 0;
// 只要 mex 存在于集合中，就一直增加
while (set.find(mex) != set.end()) {
mex++;
}
return mex;
}
// 计算 n 个石子的 Grundy 数
int calculateGrundy(int n) {
// 基本情况：0 个石子对应 Grundy 数 0
if (n == 0) {
return 0;
}
unordered_set nextStates;
// 遍历所有可能的移动：拿走 1 到 n 个石子
// 剩下的石子数是 0 到 n-1
for (int i = 0; i <= n - 1; i++) {
// 递归计算子状态的 Grundy 数并加入集合
nextStates.insert(calculateGrundy(i));
}
// 返回集合的 Mex
return calculateMex(nextStates);
}
int main() {
int n = 10;
cout << "石子数量为 " << n << " 时的 Grundy 数是: " << calculateGrundy(n) << endl;
return 0;
}
Python 实现
def calculate_mex(s):
"""计算集合 s 的 Mex (最小排除值)"""
mex = 0
while mex in s:
mex += 1
return mex
def calculate_grundy(n):
"""计算 n 个石子的 Grundy 数"""
# 基本情况：0 个石子对应 Grundy 数 0
if n == 0:
return 0
# 存储所有可能的下一步状态的 Grundy 数
next_states_grundy = set()
# 遍历所有可能的移动：拿走 1 到 n 个石子
# 这意味着剩下的石子数量从 0 到 n-1 不等
for i in range(n):
# 递归计算子状态并加入集合
next_states_grundy.add(calculate_grundy(i))
# 返回集合的 Mex
return calculate_mex(next_states_grundy)
if __name__ == "__main__":
n = 10
print(f"石子数量为 {n} 时的 Grundy 数是: {calculate_grundy(n)}")
实战演练：更复杂的游戏——只能拿 1、2 或 3 个
现在让我们把规则稍微改难一点。这不仅是一个练习，更是理解算法灵活性的关键。
游戏规则更新：
游戏开始时有一堆 $n$ 个石子。轮到的玩家可以拿走 1 个、2 个或 3 个 石子（不能拿更多，也不能不拿）。最后行动的玩家获胜。
#### 分析
我们可以重用上面的逻辑，唯一的变化在于 "下一步状态" 的生成。
- 当 $n = 0$ 时：$Grundy(0) = 0$ (必败)。
- 当 $n = 1$ 时：只能拿 1 个，剩下 0 个。集合 $\{Grundy(0)\} = \{0\}$。$Mex(\{0\}) = 1$。结果：1。
- 当 $n = 2$ 时：
* 拿 1 个，剩 1 个 (Grundy 1)。
* 拿 2 个，剩 0 个 (Grundy 0)。
* 集合 $\{0, 1\}$。$Mex(\{0, 1\}) = 2$。结果：2。
- 当 $n = 3$ 时：
* 剩 2 (Grundy 2)，剩 1 (Grundy 1)，剩 0 (Grundy 0)。
* 集合 $\{0, 1, 2\}$。$Mex(\{0, 1, 2\}) = 3$。结果：3。
- 当 $n = 4$ 时：关键来了！
* 拿 1 个，剩 3 (Grundy 3)。
* 拿 2 个，剩 2 (Grundy 2)。
* 拿 3 个，剩 1 (Grundy 1)。
* 下一步状态集合是 $\{1, 2, 3\}$。
* 注意这里没有 0！
* $Mex(\{1, 2, 3\}) = 0$。
这意味着：如果石子数量是 4，面对这个局面的玩家处于必败态。无论他拿 1、2 还是 3 个，对手都会面临一个 Grundy 数不为 0 的局面（即必胜态）。
#### 代码实现：限制步数的游戏
这里我们展示如何通过修改循环范围来适配新的规则。注意代码结构几乎没变，只改变了搜索子状态的逻辑。
C++ 实现
#include
#include
#include
using namespace std;
// 计算 Mex
int calculateMex(unordered_set Set) {
int Mex = 0;
while (Set.find(Mex) != Set.end())
Mex++;
return (Mex);
}
// 计算限制步数的游戏 Grundy 数
int calculateGrundy(int n) {
if (n == 0)
return 0;
unordered_set Set;
// 关键修改：我们限制了拿走的石子数为 1, 2, 3
// 所以剩下的石子数是 n-1, n-2, n-3
// 必须确保剩下的石子数 >= 0
for (int i = 1; i = 0) {
Set.insert(calculateGrundy(n - i));
}
}
return calculateMex(Set);
}
int main() {
// 让我们打印前 15 个数字的 Grundy 数，看看周期
for (int i = 0; i <= 15; i++) {
printf("%d: %d
", i, calculateGrundy(i));
}
return 0;
}
进阶：从单堆到多堆
在之前的例子中，我们实际上是在计算单个状态的 Grundy 数。在单堆游戏中，如果 $Grundy(n)
eq 0$，先手必胜；如果 $Grundy(n) = 0$，先手必败。
但在实际应用中，我们经常面对的是多堆石子或者多个独立游戏的组合（例如，你在玩尼姆游戏，有三堆石子）。
Sprague-Grundy 定理的威力在于此：
> 组合游戏的 Grundy 数等于各子游戏 Grundy 数的异或和（Nim-sum）。
假设你有三堆石子，数量分别为 $n1, n2, n_3$。那么这个局面的总 Grundy 数是：
$$G{total} = Grundy(n1) \oplus Grundy(n2) \oplus Grundy(n3)$$
如果 $G_{total}
eq 0$，先手可以通过一步操作让异或和变为 0，从而掌握胜势。如果 $G_{total} = 0$，先手必败（假设对手也是最优策略）。
常见错误与性能优化
在编写博弈论代码时，尤其是处理递归时，新手容易遇到两个主要问题：栈溢出（递归太深） 和 超时（重复计算）。
#### 1. 记忆化搜索（Memoization）
如果你仔细看上面的 calculateGrundy(10) 代码，你会发现为了计算 10，我们需要计算 9，为了计算 9，我们需要计算 8… 这种重复计算会随着 $n$ 的增大呈指数级爆炸。
解决方案：使用一个数组或哈希表存储已经计算过的值。
// C++ 记忆化优化示例
int dp[1000]; // 初始化为 -1
int calculateGrundyMemo(int n) {
if (n == 0) return 0;
// 如果已经计算过，直接返回
if (dp[n] != -1) return dp[n];
unordered_set Set;
for (int i = 1; i = 0) {
Set.insert(calculateGrundyMemo(n - i));
}
}
// 存入数组并返回
return dp[n] = calculateMex(Set);
}
#### 2. 寻找周期规律
很多组合游戏的 Grundy 数最终会呈现周期性。
例如在 "只能拿 1, 2, 3 个" 的游戏中，前几项是：0, 1, 2, 3, 0, 1, 2, 3 …
这是一个周期为 4 的循环。
实战技巧：如果你在比赛中或实际应用中发现 $n$ 非常大（比如 $10^{18}$），通常不需要一步步计算。你可以手动推导前几十项，观察是否有周期。一旦发现周期 $k$，那么 $Grundy(n) = Grundy(n \% k)$。这样可以将 $O(n)$ 甚至指数级的时间复杂度降低到 $O(1)$。
总结
在本文中，我们深入探讨了 Grundy 数和 Mex 算法。我们不仅学习了它们的定义，还通过代码实现了从简单到复杂的计算过程。
关键要点回顾：
- Mex (最小排除值) 是计算 Grundy 数的核心工具，它是集合中缺失的最小非负整数。
- Grundy 数 将一个复杂的游戏状态转化为一个数字。如果 Grundy 数为 0，则为必败态；否则为必胜态。
- 递归与记忆化 是计算 Grundy 数的标准方法，但在处理大数据时，寻找周期性规律才是解决问题的终极武器。
- 组合游戏 可以通过异或和来求解，这使得我们能将复杂的局面分解为简单的子问题。
现在，你已经具备了分析和解决绝大多数无运气因素的回合制游戏的理论基础。下次当你遇到一个新的游戏规则时，不妨试着写出前几步的 Grundy 数，看看能否发现制胜的规律！