Skip to main content

Sprague-Grundy 定理

本文主要参考了 CP-Algorithms 的有关章节。

公平博弈​

一场公平博弈，指的是一场信息完全透明，两个参加者除了先后手差别之外完全对等，同时任意时刻的可行操作与胜负判定只由当前时刻的状态决定的二人博弈。

Nim 博弈​

Nim 是最经典的二人博弈之一。在 Nim 中，一共有若干堆石子，两个参加者轮流行动，每次的行动方可以选择任意一堆，并从中取出任意数目的石子。首先无石子可取的一方落败。

这里首先给出 Nim 博弈的结论：如果所有堆的石子数的异或和为 00，则后手有必胜策略；否则，先手有必胜策略。

我们可以通过数学归纳法给出证明。

首先，如果当前所有堆都没有石子，显然异或和为 00，而此时后手获胜，符合上面给出的结论。

接下来考虑还有石子的情况。

  • 如果当前 s=⊕ai=0s=\oplus a_i=0 ，先手方进行一步操作，将某一堆石子的个数从 xx 减少到 yy，则我们可以求出操作后的异或和：
t=s⊕x⊕y=x⊕yt=s\oplus x\oplus y=x\oplus y

因为 y<xy<x ，所以 x⊕y≠0x\oplus y\neq0 ，这意味着无论如何操作，接下来都会变为异或和不为 00 ，也即先手必胜的情况。所以当前这一步是后手必胜，符合上面给出的结论。

  • 如果当前 s≠0s\neq0 。设 ss 的二进制表示中的最高位为 dd，我们显然可以找到某一堆，其含有的石子数的二进制表示的第 dd 位不为 00（否则 ss 的第 dd 位不可能为 11）。设这一堆当前有 xx 个石子，则我们可以从中取出若干个石子，使剩余石子数变为 y=x⊕sy=x\oplus s（因为 xx 和 yy 高于 dd 位的部分是相同的，而 xx 的第 dd 位为 11，yy 的第 dd 位为 00，所以一定有 y<xy<x，这说明这一步操作是合法的）。这样，异或和变为：
t=s⊕x⊕y=s⊕x⊕(s⊕x)=0t=s\oplus x\oplus y=s\oplus x\oplus(s\oplus x)=0

这说明，对于异或和不为00的状态，我们总可以找到一种合法操作，在这一步操作后将异或和变为 00，也即后手必胜的情况。所以当前这一步是先手必胜，符合上面给出的结论。

从而，我们证明了我们一开始给出的结论。

可添加的Nim博弈​

在Nim中，参加者只能取石子而不能添加石子。如果参加者可以在满足一定条件的情况下向堆中添加石子，会如何呢？

实际上，我们可以通过简单的论证说明，允许添加操作对博弈结果不产生任何影响。如果一方添加了石子，另一方总可以从同一堆中取出相同数目的石子，从而让整个博弈回到添加石子之前的状态。为了保证博弈能够分出胜负，规则不应允许状态之间的无限循环，因此添加石子的次数必然是要受到限制的，那么最终整个博弈还是会按照不允许添加的情况进行下去，直到分出胜负为止。

对 Sprague-Grundy 定理的阐释​

Sprauge-Grundy 定理实际上是说明了任意公平博弈与可添加的Nim博弈之间的等价性。

首先考虑可添加的 Nim 博弈中的某一堆石子，也即单局 Nim 游戏。假设这堆石子有 NN 个，这意味着我们可以通过取石子的操作将其变为任意一个小于 NN 的非负整数；同时，我们也有可能通过添加石子的操作将其变为一个大于 NN 的正整数，但是这一操作是受到限制的，所以未必所有正整数都是可达的。

不妨令一步操作后能够到达的石子数的集合为 S\mathbb{S}，则我们可以发现，N=mex(S)N=\text{mex}(\mathbb{S})，其中 mex\text{mex} 代表不包含在某一集合中的最小的非负整数。这里，我们将 NN 称为这一状态的 Nim 数。对于单局 Nim 游戏，一个状态的 Nim 数即为这堆石子的个数。

现在我们来考虑一个一般的公平博弈。考虑单局博弈，根据前述条件，这一博弈至少存在一个终止状态 EE。从 EE 出发，不能到达任何其他状态，也即 SE=∅\mathbb{S}_E=\emptyset 。根据上面对 Nim 数的定义，我们可以知道 EE 的 Nim 数为 00。

在规定了终止状态的 Nim 数后，我们就可以根据 Nim 数的定义，对于任意状态，通过递归的方式求出其对应的 Nim 数。

现在，我们需要考虑这一一般博弈和 Nim 博弈之间的等价性。假设当前处在状态 VV，其对应的 Nim 数 mex(SV)=k\text{mex}(\mathbb{S}_V)=k。显然，这说明 ∀i,0≤i<k\forall i,0\leq i<k 的状态都是可达的，而 i>ki>k 的状态的则不能保证可达。如果我们把每一个 Nim 数想成堆中的石子个数，就刚好把当前状态 VV 等价成了一个当前有 kk 个石子的堆。这样，我们就把一般博弈变为了一个可添加的 Nim 博弈。从而，我们可以将这一多局博弈转变为多局 Nim 博弈，然后使用求解 Nim 博弈的方式来求解当前博弈的胜负结果。

练习题​

BS - Last to Toggle Wins​

提示一

每一段连续的 1 可以看成是单局博弈。如何求出单局博弈的 Nim 数，从而把整局博弈转变为 Nim 博弈？

提示二

在去除两个 1，从而把一段连续的 1 分为两段时，我们可以预先使用 Nim 博弈的结论，将两段的 Nim 数的异或值作为这一分法所对应的状态的 Nim 数。

参考代码（C++）
int nim[55];
bool inited = false;

void init() {
    inited = true;
    nim[0] = nim[1] = 0;
    for (int i = 2; i <= 50; ++i) {
        unordered_set<int> adj;
        for (int j = 0; j <= i - 2; ++j)
            adj.insert(nim[j] ^ nim[i - 2 - j]);
        while (adj.count(nim[i]))
            nim[i]++;
    }
}

bool solve(vector<int>& nums) {
    if (!inited)
        init();
    vector<int> ones;
    int now = -1, cnt = 0;
    for (int num : nums) {
        if (num == now)
            cnt++;
        else {
            if (now == 1 && cnt >= 2)
                ones.emplace_back(cnt);
            now = num;
            cnt = 1;
        }
    }
    if (now == 1 && cnt >= 2)
        ones.emplace_back(cnt);
    int ans = 0;
    for (int num : ones)
        ans ^= nim[num];
    return ans > 0;
}