SG函数详解（C++实现博弈论中的尼姆游戏核心算法）

SG 函数与尼姆游戏

在尼姆游戏中，有若干堆石子，两名玩家轮流从任意一堆中取走至少一个石子。最后取光石子的人获胜。这个游戏的每个堆可以看作一个独立的子游戏，而整个游戏的 SG 值等于各堆 SG 值的异或（XOR）。

有趣的是，在标准尼姆游戏中，一堆大小为 n 的石子的 SG 值就是 n 本身。因此，整个游戏的胜负由所有堆数量的异或结果决定。

C++ 实现 SG 函数

下面我们用 C++ 编写一个通用的 SG 函数计算程序。假设我们有一个自定义规则的游戏：每次可以从一堆石子中取 1、2 或 3 个石子。我们将计算从 0 到 n 的所有状态的 SG 值。

#include <iostream>#include <vector>#include <unordered_set>using namespace std;// 计算 mex 值int mex(const unordered_set<int>& s) {    int m = 0;    while (s.count(m)) {        m++;    }    return m;}// 计算 SG 函数（可取 1, 2, 3 个石子）vector<int> computeSG(int n) {    vector<int> sg(n + 1, 0);    for (int i = 1; i <= n; i++) {        unordered_set<int> nextStates;        // 可以取 1, 2, 3 个石子        for (int take = 1; take <= 3 && i - take >= 0; take++) {            nextStates.insert(sg[i - take]);        }        sg[i] = mex(nextStates);    }    return sg;}int main() {    int n = 10;    vector<int> sg = computeSG(n);    cout << "SG values from 0 to " << n << ":\n";    for (int i = 0; i <= n; i++) {        cout << "SG[" << i << "] = " << sg[i] << endl;    }    return 0;}

运行上述代码，你会得到如下输出：

SG values from 0 to 10:SG[0] = 0SG[1] = 1SG[2] = 2SG[3] = 3SG[4] = 0SG[5] = 1SG[6] = 2SG[7] = 3SG[8] = 0SG[9] = 1SG[10] = 2

可以看到，SG 值呈现周期性（0,1,2,3,0,1,2,3,...），这是因为规则限制了每次最多取 3 个石子。

如何判断胜负？

如果有多个独立子游戏（比如多堆石子），总 SG 值为各子游戏 SG 值的异或：

total_sg = sg[a] ^ sg[b] ^ sg[c] ^ ...

如果 total_sg != 0，先手必胜；否则先手必败。

总结

通过本教程，我们学习了 SG函数 的基本概念、mex 运算、以及如何用 C++算法 实现它来解决 博弈论 中的经典问题，如 尼姆游戏。掌握 SG 函数不仅能帮助你在算法竞赛中快速解题，还能加深你对游戏策略的理解。

建议读者动手修改规则（比如允许取 1、3、4 个石子），观察 SG 值的变化，从而真正掌握这一强大工具！