公平组合游戏

经典的公平组合游戏有很多，包括取数游戏，31 点，以及 Nim 游戏等。

Nim 游戏

首先介绍什么是 Nim 游戏。有 \(n\) 堆物品，每堆有 \(a_i\) 个。

两个玩家轮流取走任意一堆的任意个物品，但不能不取，取走最后一个物品的人获胜。

例如，如果现在有 \(n=3\) 堆物品，而每堆分别有 \(2,5,4\) 个，那么可以取走第 \(1\) 堆中的 \(2\) 个物品，

局面就变成了 \(0,5,4\) ，或者也可以取走第 \(2\) 堆的 \(4\) 个物品，局面就变成了 \(2,1,4\) 。

如果现在的局面为 \(0,0,5\) ，甲取走了第 \(3\) 堆的 \(5\) 个物品，也就是取走了最后一个物品，甲获胜。

不过我相信会来看这篇文章的人大概都知道 Nim 游戏吧。

博弈图 & 状态

如果将每个状态视为一个节点，再从每个状态向它的后继状态连边，我们就可以得到一个博弈状态图。

例如，如果节点 \((i,j,k)\) 表示局面为 \(i,j,k\) 时的状态，则我们可以画出下面的博弈图（部分）

定义 必胜状态 为先手必胜的状态（通常用 \(\mathrm{N}\) 表示），必败状态 为先手必败的状态（通常用 \(\mathrm{P}\) 表示）。

通过推理，我们可以得出下面三条定理：

定理 1：没有后继状态的状态是必败状态。
定理 2：一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。
定理 3：一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。

上面三个定理非常显然，这里不给出证明了。

如果博弈图是一个有向无环图 (DAG)，那么通过这三个定理，

我们可以在绘出博弈图的情况下用 \(\mathcal{O}(n+m)\) 的时间，得出每个节点的状态。

Nim 和

让我们再次回顾 Nim 游戏。

通过绘制博弈图，可以在 \(\mathcal{O}(\prod_{1 \le i \le n} a_i)\) 的时间内暴力求出该局面是否先手必胜。

但是，这样的时间复杂度实在太高。~~有没有什么巧妙而快速的方法呢~~？

定义 Nim 和为 \[ a_1 \oplus a_2 \oplus \ldots \oplus a_n \] 当且仅当 Nim 和为 \(0\) 时，该状态为必败态；否则该状态为必胜态。

证明：

为了证明该定理，只需要证明下面三个定理：

定理 1：没有后继状态的状态是必败状态。
定理 2：对于 \(a_1 \oplus a_2 \oplus \cdots \oplus a_n \ne 0\) 的局面，一定存在某种移动使得 \(a_1 \oplus a_2 \oplus \ldots \oplus a_n=0\)
定理 3：对于 \(a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0\) 的局面，一定不存在某种移动使得 \(a_1 \oplus a_2 \oplus \ldots \oplus a_n=0\)

对于定理 1，没有后继状态的节点只有一个，即全 \(0\) 的情况，此时 \(a_1 \oplus a_2 \oplus \ldots \oplus a_n=0\)

对于定理 2，不妨假设 \(a_1 \oplus a_2 \oplus \ldots a_n=k \neq 0\) ，如果我们要将 \(a_i\) 改为 \(a_i^{\prime}\) ，则 \(a_i^{\prime} = a_i \oplus k\)

假设 \(k\) 的二进制最高位 \(1\) 为 \(d\) ，即 \(2^d \le k < 2^{d + 1}\) 。

根据异或的定义，一定有奇数个 \(a_i\) 的二进制第 \(d\) 位为 \(1\)

满足这个条件的 \(a_i\) 一定也满足 \(a_i > a_i \oplus k\) ，因而这是一个合法的移动。

对于定理 3，如果我们要将 \(a_i\) 改为 \(a_i^{\prime}\) ，则根据异或运算律可以得出 \(a_i = a_i^{\prime}\) ，因而这不是合法的移动。\(\square\)

有向图游戏与 SG 函数

~~这才是本文的重点，不是么~~

有向图游戏是一个经典的博弈游戏——实际上，大部分的公平组合游戏都可以转换为有向图游戏。

在一个有向无环图中，只有一个起点，上面有一个棋子，两个玩家轮流沿着有向边推动棋子，不能走的玩家判负。

定义 \(\mathrm{mex}\) 函数的值为不属于集合 \(S\) 中的最小非负整数，即 \[ \operatorname{mex}(S)=\min \{x\} \quad(x \notin S, x \in N) \] 例如 \(\operatorname{mex}(\{0,2,4\})=1,~\operatorname{mex}(\{1,2\})=0\) 。

对于状态 \(x\) 和它的所有 \(j\) 个后继状态 \(y_1,y_2,\cdots,y_k\) ，定义 SG 函数为 \[ \mathrm{SG}(x)=\operatorname{mex}\left\{\operatorname{SG}\left(y_1\right), \mathrm{SG}\left(y_2\right), \ldots, \mathrm{SG}\left(y_k\right)\right\} \] 而对于由 \(n\) 个有向图游戏组成的组合游戏，设它们的起点分别为 \(s_1,s_2,\cdots,s_n\) ，则

有定理：当且仅当 \[ \mathrm{SG}\left(s_1\right) \oplus \mathrm{SG}\left(s_2\right) \oplus \ldots \oplus \mathrm{SG}\left(s_n\right) \neq 0 \] 时，这个游戏是先手必胜的，同时这是一个组合游戏的游戏状态 \(x\) 的 SG 值

这一定理被称作 Sprague–Grundy 定理，简称 SG 定理。

SG 定理的证明

可以使用数学归纳法来证明。

我们假设对于游戏状态 \(x^{\prime}\) ，其当前节点 \(s_1^{\prime}, s_2^{\prime}, \ldots, s_n^{\prime}\) （对于任意 \(i\) 有 \(s_i^{\prime}<s_i\) ）皆满足 SG 定理。

显然当 \(\mathrm{SG}\left(s_1\right)^{\prime}=\mathrm{SG}\left(s_2\right)^{\prime}=\ldots \mathrm{SG}\left(s_n\right)^{\prime}=0\) 时，该状态能满足 SG 定理。

那么只需要证明对于游戏状态 \(x\) ，其当前节点 \(s_1^{\prime}, s_2^{\prime}, \ldots, s_n^{\prime}\) 符合 SG 定理，SG 定理便成立。

事实上这一个状态可以看作一个 Nim 游戏：

对于某个节点 \(s_i\) ，它可以移动到任意一个 SG 值比它小或比它大的节点。

在有向图游戏中，当一方将某一节点 \(s_i\) 移动到 \(\mathrm{SG}\) 值比它大的节点时，

另一方可以移动回和 SG 值和 \(\mathrm{SG}\left(s_i\right)\) 一样的节点，所以向 SG 值较大节点移动是无效操作。

当移动到 SG 值较小的节点时，情况则会和 Nim 游戏一样，

能够到达任何一个游戏状态 \(x^{\prime}\) 使得 \[ \mathrm{SG}\left(x^{\prime}\right)=\mathrm{SG}\left(s_1^{\prime}\right) \oplus \mathrm{SG}\left(s_2^{\prime}\right) \oplus \ldots \oplus \mathrm{SG}\left(s_n^{\prime}\right)<\mathrm{SG}(X) \] （注意到前文已经假设 \(x^{\prime}\) 满足 SG 定理），但到达不了 SG 值为 \(\mathrm{SG}\left(s_1\right) \oplus \mathrm{SG}\left(s_2\right) \oplus \ldots \oplus \mathrm{SG}\left(s_n\right)\) 的节点。

所以状态 \(x\) 符合 SG 定理。证毕。