C语言实现Sprague-Grundy函数：博弈论核心算法与游戏策略编程实践269

在计算机科学与编程领域，C语言以其卓越的性能和贴近硬件的特性，长期以来都是实现底层算法和复杂数据结构的理想选择。当涉及到解决博弈论（Game Theory）中的特定问题时，一种被称为Sprague-Grundy定理（简称SG定理）的强大工具便浮出水面。它能够将许多看似复杂的“无偏博弈”（Impartial Games）转化为更简单的Nim游戏，从而帮助我们判断游戏的胜负状态，甚至找出必胜策略。本文将深入探讨SG定理的原理、SG函数（Grundy值）的计算方法，并提供详细的C语言实现代码，助您在游戏策略编程中游刃有余。

一、C语言与博弈论算法的交汇

C语言作为一门系统级编程语言，其强大的控制能力和高效的执行效率使其成为实现各种复杂算法的理想选择。在算法竞赛、游戏AI开发乃至学术研究中，我们常常需要用C语言来解决各种博弈问题。这些问题通常涉及两位玩家轮流操作，且每次操作都会改变游戏状态。SG定理提供了一种通用的框架来分析一类特定的博弈——无偏博弈。

无偏博弈的特点是：
两位玩家轮流操作。
游戏规则对两位玩家是完全相同的，即从任意给定状态出发，双方玩家可采取的行动是相同的。
游戏在有限步数内结束，不会出现平局。
玩家的目标是使自己能够做出最后一个合法移动。

经典的Nim游戏就是最典型的无偏博弈。而SG定理的伟大之处在于，它证明了所有正常玩法的无偏博弈都等价于某个Nim堆，其“Nim值”就是我们今天要深入探讨的SG函数值。

二、理解Sprague-Grundy定理与SG函数

2.1 P-position与N-position

在深入SG函数之前，我们需要先了解博弈论中关于游戏状态的两个基本概念：
P-position（Previous-player winning position）：先前的玩家（即当前轮到他操作之前的玩家）有必胜策略。对于当前轮到操作的玩家而言，这是一个必败态。
N-position（Next-player winning position）：当前的玩家有必胜策略。对于当前轮到操作的玩家而言，这是一个必胜态。

一个游戏状态是P-position当且仅当它所有的后继状态都是N-position。一个游戏状态是N-position当且仅当它至少有一个后继状态是P-position。最终的终止状态（无法进行任何操作的状态）被定义为P-position。

2.2 SG函数（Grundy值）的定义

Sprague-Grundy定理的核心是SG函数，它为每个游戏状态分配一个非负整数值，称为Grundy值或Nim值。SG函数定义如下：

对于一个游戏状态 `x`，其SG函数值 `sg(x)` 等于其所有后继状态的SG函数值集合中，未出现过的最小非负整数（Minimum Excluded value，简称MEX）。

用数学公式表示为：

sg(x) = MEX({ sg(y) | y 是 x 的后继状态 })

其中，MEX函数定义为：对于一个非负整数集合 `S`，`MEX(S)` 是不在 `S` 中的最小非负整数。例如：
`MEX({0, 1, 2}) = 3`
`MEX({1, 2, 4}) = 0`
`MEX({}) = 0`

对于终止状态（即没有后继状态），其SG值为 `MEX({}) = 0`。

2.3 SG函数与胜负判断

SG函数值与P/N-position有直接的关联：
如果 `sg(x) = 0`，则状态 `x` 是一个P-position（必败态）。
如果 `sg(x) > 0`，则状态 `x` 是一个N-position（必胜态）。

这个结论非常强大，因为它将一个复杂的无偏博弈问题转化为了计算SG值的问题。

2.4 组合游戏的SG值

当多个独立的无偏博弈组合在一起时，其总的SG值可以通过对各个子游戏的SG值进行异或（XOR）运算得到。这便是Nim和理论的核心：

sg(G1 + G2 + ... + Gn) = sg(G1) ^ sg(G2) ^ ... ^ sg(Gn)

其中 `^` 表示按位异或操作。如果最终的总SG值为0，则先手必败；否则先手必胜。

三、C语言实现SG函数的基本思路

计算SG函数通常采用递归的方式，并辅以记忆化搜索（Memoization），以避免重复计算，提高效率。因为每个状态的SG值都依赖于其后继状态的SG值，这形成了一个有向无环图（DAG），非常适合动态规划或带记忆化的递归。

3.1 核心数据结构

`grundy_values[]` 数组：用于存储已经计算过的SG值，实现记忆化。初始化为-1或某个特殊值，表示未计算。
`bool visited[]` 或 `std::set`：在计算 `MEX` 值时，用于标记已出现过的后继SG值。

3.2 算法步骤

定义状态：根据具体的游戏规则，确定如何表示游戏状态。例如，如果是一个取石子游戏，状态可以是剩余石子的数量。
定义移动：确定从当前状态可以转移到哪些后继状态。
`calculate_sg(int state)` 函数：

检查 `grundy_values[state]` 是否已计算。如果已计算，直接返回存储的值。
获取所有后继状态 `y`。
递归调用 `calculate_sg(y)` 获取所有后继状态的SG值。
将这些SG值收集到一个集合中。
使用 `MEX` 函数计算当前状态 `state` 的SG值。
将计算出的SG值存储到 `grundy_values[state]` 中，然后返回。


`MEX` 函数实现：

创建一个布尔数组 `seen_sg_values`，大小足以覆盖可能的最大SG值，并初始化为 `false`。
遍历后继状态的SG值集合，将 `seen_sg_values[sg_value]` 设为 `true`。
从0开始遍历 `seen_sg_values`，找到第一个为 `false` 的索引，即为 `MEX` 值。

四、C语言实现示例：一个简单的取石子游戏

让我们以一个经典的取石子游戏为例：有一堆 `N` 个石子，每次可以取走 `1`、`2` 或 `3` 个石子。问先手在有多少个石子时必胜？

4.1 游戏规则分析

状态：当前剩余的石子数量 `N`。
移动：从状态 `N` 可以移动到 `N-1`、`N-2` 或 `N-3`。
终止状态：`N=0` 时无法移动。

4.2 C语言代码实现

```c
#include
#include
#include // For memset
// 定义最大石子数，根据实际需求调整
#define MAX_STONES 100
// 定义每次可以取的石子数，可以根据游戏规则修改
const int MOVES[] = {1, 2, 3};
const int NUM_MOVES = sizeof(MOVES) / sizeof(MOVES[0]);
// 用于存储SG值的数组，-1表示未计算
int grundy_values[MAX_STONES + 1];
// MEX (Minimum Excluded) 函数的实现
// 参数: sg_set 是一个布尔数组，表示某个SG值是否已出现
// size 是 sg_set 的最大可能索引 (即最大可能SG值 + 1)
int calculate_mex(bool *sg_set, int size) {
for (int i = 0; i < size; ++i) {
if (!sg_set[i]) {
return i;
}
}
// 理论上不会发生，除非sg_set不够大
return size;
}
// 计算给定状态 (剩余石子数) 的SG值
int calculate_sg(int n) {
// 记忆化搜索：如果已经计算过，直接返回
if (grundy_values[n] != -1) {
return grundy_values[n];
}
// 用于存储当前状态所有后继状态的SG值
// 由于SG值可能最大为MAX_STONES，我们可能需要一个更大的数组来避免越界
// 但通常MEX函数的值不会特别大，这里取一个经验值MAX_STONES即可
bool seen_sg_values[MAX_STONES + 1];
memset(seen_sg_values, 0, sizeof(seen_sg_values)); // 初始化为false
// 遍历所有可能的移动
for (int i = 0; i < NUM_MOVES; ++i) {
int move = MOVES[i];
if (n >= move) {
// 获取后继状态
int next_state = n - move;
// 递归计算后继状态的SG值，并标记为已出现
seen_sg_values[calculate_sg(next_state)] = true;
}
}
// 计算MEX值并存储
grundy_values[n] = calculate_mex(seen_sg_values, MAX_STONES + 1);
return grundy_values[n];
}
int main() {
// 初始化所有SG值为-1，表示未计算
memset(grundy_values, -1, sizeof(grundy_values));
// 基本情况：0个石子的SG值为0 (P-position)
grundy_values[0] = 0;
printf("Sprague-Grundy (SG) Values for Take-Away Game (moves: 1, 2, 3):");
for (int i = 0; i 0) {
printf("For %d stones, the first player has a winning strategy.", initial_stones);
} else {
printf("For %d stones, the first player will lose if the second player plays optimally.", initial_stones);
}
// 组合游戏示例 (如果游戏是多个独立游戏的和)
// 假设有两堆石子，一堆5个，一堆7个
int pile1_stones = 5;
int pile2_stones = 7;
int total_sg_xor = calculate_sg(pile1_stones) ^ calculate_sg(pile2_stones);
printf("For a game with two piles (%d and %d stones), total SG XOR = %d.",
pile1_stones, pile2_stones, total_sg_xor);
if (total_sg_xor > 0) {
printf("The first player has a winning strategy in the combined game.");
} else {
printf("The first player will lose in the combined game.");
}
return 0;
}
```

4.3 代码解析

1. `grundy_values` 数组：这是记忆化数组，`grundy_values[i]` 存储着 `i` 个石子状态的SG值。初始化为-1表示未计算。

2. `MOVES` 数组：定义了每次可以取的石子数量，可以灵活修改以适应不同规则的取石子游戏。

3. `calculate_mex(bool *sg_set, int size)` 函数：
它接收一个布尔数组 `sg_set`，这个数组的索引代表SG值，值为 `true` 表示该SG值已出现。
从0开始递增查找 `sg_set` 中第一个为 `false` 的索引，这个索引就是 `MEX` 值。

4. `calculate_sg(int n)` 函数：
记忆化检查：首先检查 `grundy_values[n]` 是否不为-1。如果是，说明该值已计算过，直接返回，避免重复递归。
`seen_sg_values` 数组：这是一个局部布尔数组，用于当前状态计算 `MEX`。它会记录从当前状态 `n` 出发，所有后继状态的SG值。
遍历移动：`for` 循环遍历所有可能的取石子数量 (`MOVES` 数组)。
递归调用：对于每个合法的移动 (`n >= move`)，计算后继状态 `n - move` 的SG值，并通过 `seen_sg_values[calculate_sg(next_state)] = true;` 标记该SG值已出现。
计算并存储：调用 `calculate_mex` 函数得到当前的 `MEX` 值，并将其存储在 `grundy_values[n]` 中，然后返回。

5. `main` 函数：
初始化 `grundy_values` 数组。
设置基本情况 `grundy_values[0] = 0`。
循环计算并打印从0到 `MAX_STONES` 所有状态的SG值，并根据SG值判断是P-position还是N-position。
展示了如何判断特定初始状态的胜负。
演示了组合游戏（两堆石子）的SG异或和判断。

五、SG函数的应用与进阶

5.1 复杂状态的表示

上述例子中，游戏状态只用一个整数（石子数）表示。对于更复杂的无偏博弈，状态可能需要用结构体、数组或哈希表来表示。此时，记忆化数组可能需要替换为 `std::map` 或自定义哈希函数和哈希表来存储SG值。

5.2 性能与优化

SG函数的计算复杂度取决于状态的数量 `N`，以及每个状态的后继状态数量 `M`，以及计算 `MEX` 的复杂度 `K`。总复杂度大致为 `O(N * M * K)`。在上述取石子游戏中，`N` 是最大石子数，`M` 是 `MOVES` 的数量，`K` 是可能的最大SG值。由于 `K` 通常不会特别大，且 `M` 是常数，因此总复杂度大致为 `O(N * MAX_SG_VALUE)`。

对于状态数量巨大的问题，可能需要寻找SG值的循环节或者使用其他高级技巧。

5.3 组合游戏的策略生成

SG定理不仅能判断胜负，还能帮助玩家找出必胜策略。如果一个组合游戏的Nim和（总SG值）不为0，那么先手玩家必胜。为了赢得游戏，先手玩家需要找到一个移动，使得移动后的新游戏状态的Nim和变为0。对于一个子游戏G，如果其SG值是 `sg(G)`，总Nim和是 `S`，那么玩家需要从G中移动到G'，使得 `sg(G') = S ^ sg(G)`。只要能找到这样的 `G'`，就存在必胜策略。

六、总结

Sprague-Grundy定理是博弈论中的一个重要基石，它提供了一种通用的方法来分析和解决无偏博弈问题。通过将每个游戏状态映射为其Nim值（SG函数值），我们能够利用Nim和理论判断游戏的胜负，并为组合游戏制定策略。C语言作为实现高效算法的利器，为我们提供了编写SG函数、进行记忆化搜索的强大能力。

掌握SG函数的计算和应用，对于算法工程师、游戏开发者以及任何对博弈论和算法感兴趣的程序员来说，都是一项宝贵的技能。希望通过本文的详细解释和C语言代码示例，您能对SG函数有深入的理解，并在实际项目中灵活运用，编写出更加智能和强大的游戏策略程序。

2025-10-25

---

上一篇：C语言 UTF-8 输出全攻略：原理、实践与常见问题解析

下一篇：C语言数列函数编程：从基础到高效实现与优化详解