Sprague-Grundy定理

本文内容主要参考自CP-Algorithms (opens new window)。

公平博弈

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

Nim博弈

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

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

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

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

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

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

$$t=s\oplus x\oplus y=x\oplus y$$

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

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

$$t=s\oplus x\oplus y=s\oplus x\oplus(s\oplus x)=0$$

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

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

可添加的Nim博弈

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

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

对Sprague-Grundy定理的阐释

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

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

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

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

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

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

练习题

BS - Last to Toggle Wins (opens new window)

提示一

每一段连续的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;
}