公平组合游戏

应该是2016年的最后一篇博客了，Goodbye 2016！

定义

公平组合游戏与平常的游戏类似，但是需要满足以下要求：

1. 有两个玩家轮流行动。
2. 双方的游戏方式一致。
3. 双方均知道游戏的完整信息。
4. 以玩家无法行动为游戏结束。
5. 游戏在有限步数内结束，并且一定能分出胜负。

经典的Nim游戏就是公平组合游戏的代表，但是围棋、象棋以及井字棋这些不属于，因为这三种双方的行动不同。而且像井字棋，可能存在平局。

简单Nim游戏

现在通过一个简单的Nim游戏来介绍一些概念。这个Nim游戏规定如下：

1. 一开始有$n$个石子。
2. 双方轮流取石子，必须取一颗或两颗。
3. 无法取石子者失败。

对于这个游戏，我们想知道，在双方都十分聪明的情况下，先手/后手是否必胜。或者给出一个必胜的策略。

我们可以简单分析一下。以先手为例，如果没有石子，那么一开场就算输。如果只有一颗或两颗石子，那么先手可以马上取走并获得胜利。然而，当有$3$颗石子时，你会发现无论怎么取，先手都会输掉比赛，因为无法一次取走所有的石子，而后手在你取完一次之后，相当于变成了石子数为$1$或$2$的先手，那么后手必赢。

实际上，当$n \;\mathrm{mod}\; 3 = 0$的时候，先手会必输，否则后手必输，此时先手只用保证每次自己取完之后石子的数量都是$3$的倍数即可。

必胜与必败

我们规定一个位置 (例如上面的Nim游戏中石子的个数) 是$\mathrm{N}$点是当此时先手的人必胜的位置，而$\mathrm{P}$点则是此时先手的人必输的位置¹。例如，当$n = 0$时 (下面简写为$0$)，先手是必输的。因此$0$是$\mathrm{P}$点。而在$1$和$2$时，先手会必胜，所以它们是$\mathrm{N}$点。

简单分析可知：

1. 终止位置是$\mathrm{P}$点。
2. 所能到达的位置都是$\mathrm{N}$点的位置是$\mathrm{P}$点。
3. 能够到达$\mathrm{P}$点的位置是$\mathrm{N}$点。

例如，在$3$这个位置，取走一个石子会到达$2$这个位置，取走两个石子会到达$1$这个位置，而这两个位置都是$\mathrm{N}$点，所以$3$是$\mathrm{P}$点。因此$3$个石子时先手必败。

图的表示

如果将每个位置用点表示，而位置之间的转移用有向边表示，那么$0$到$3$之间的关系可以由下图表示：

由于游戏是有限步数的，所以这张图必须是拓扑图。在这图上，我们可以将所有没有出边的点标记为$\mathrm{P}$点，然后根据上面的规则就可以辨识所有的位置是$\mathrm{N}$点还是$\mathrm{P}$点。由此也可以看出，一个公平组合游戏必定能分出胜负。

Sprague-Grundy定理

现在我们将位置用图$G(V, E)$上的点表示，对于一个点$u$，那么定义它的SG函数$g$为：
$$ g(u) = \mathrm{mex}(\{g(v) : \forall (u, v) \in E\}) $$

$\mathrm{mex}$是定义域在集合上的函数，返回这个集合中最小的没出现过的非负整数。
例如：
$$ \begin{aligned} & \mathrm{mex}(\varnothing) & = 0 \\ & \mathrm{mex}(\{0\}) & = 1 \\ & \mathrm{mex}(\{0, 1, 2, 4, 5\}) & = 3 \end{aligned} $$

因此，对于没有出边的点，其$g$值为$0$。另一方面，这些点都是$\mathrm{P}$点。如果我们计算之前出现的图中的$g$值：

上图中$0$和$3$都是$0$，$1$和$2$都不是$0$。十分巧合的是，$0$和$3$是$\mathrm{P}$点，$1$和$2$是$\mathrm{N}$点。

对此，我们可以证明下面一点：

位置$p$是$\mathrm{P}$点当且仅当$g(p) = 0$。

证明：首先对于没有出边的点，它们是$\mathrm{P}$点，并且其$g$值为$0$。同时，所有能到达的这些点的点，其$g$值$\gt 0$，并且为$\mathrm{N}$点。
对于其他的点，如果是$\mathrm{N}$点，那么它一定能到达一个$\mathrm{P}$点，所以其$g$值不能为$0$。如果是$\mathrm{P}$点，那么它所能到达的点都是$\mathrm{N}$点，这些点中没有谁的$g$值是$0$，所以其$g$值为$0$。

这样我们拥有了一个量化胜负的函数。但是对于上面这个简单Nim游戏并没有什么好处，因为上面的计算完全可以利用逻辑运算而不需要计算什么$\mathrm{mex}$。

多数情况下，你所见到的所谓Nim游戏并没有这么简单：它通常有许多堆石子，允许任意取走 (或是取走指定数量的石子)，此时再去问你先手是必胜还是必败。

这并没有什么难的，我们依然可以将许多堆石子放入多元组来构成一个位置，然后依然可以计算这个位置是$\mathrm{N}$点还是$\mathrm{P}$点。但是，当石子数量比较多时，这个位置的增长几乎是不可接受的。

事实上，即使是多堆石子，它依然可以分解为多个一堆的Nim游戏，每次行动时，玩家可以任意选择其中一个游戏来行动。不妨用$G_1(V_1, E_1)$和$G_2(V_2, E_2)$两张图来表示两个公平组合游戏，那么定义$G(V, E) = G_1 + G_2$为游戏的组合，即新游戏$G$可以每一步在$G_1$中行动，或是在$G_2$中行动。我们需要将两张图加合为一张图，所以对于$u \in V_1$和$v \in V_2$的两个点，在$G$中将变为一个点$(u, v)$。同时和$u$、$v$相关的边都连向这个点。
可是，多数情况下，我们不会关心这个图是什么样的，因为它实在是太复杂了。但是却有一个很好的性质：

(Sprague-Grundy定理)
令$G = G_1 + G_2 + \cdots + G_n$，设$G_i$的SG函数为$g_i$，$G$的SG函数为$g$，那么有：
$$ g(X) = g((x_1, x_2, \dots, x_n)) = g_1(x_1) \oplus g_2(x_2) \oplus \cdots \oplus g_n(x_n) $$

其中$X \in V, x_i \in V_i$，$\oplus$是异或运算。

证明：在这里不再介绍异或了，如果不了解的可以先去看一下。
根据SG函数的定义，我们只用证明以下两点就可以完成整个定理的证明：
设$b = g_1(x_1) \oplus g_2(x_2) \oplus \cdots \oplus g_n(x_n)$。

1. 对于所有的$0 \leqslant a \lt b$，$X$一定存在一个可以到达的位置，满足其$g$值为$a$。
2. 对于所有$X$所可以到达的位置，没有$g$值为$b$。

证明$(1)$：设$d = a \oplus b$。设$d$的二进制表示的最高位的位置为$k$。由于$a \lt b$，所以一定有$a$的第$k$位为$0$，并且$b$的第$k$位为$1$。由于$b = g_1(x_1) \oplus g_2(x_2) \oplus \cdots \oplus g_n(x_n)$，那么一定存在一个$g_i(x_i)$的第$k$位为$1$。不失一般性，设$i = 1$，那么可以知道$d \oplus g_1(x_1) \lt g_1(x_1)$，所以存在一个位置$x^\prime_1$能够从$x_1$转移过来，并且满足$g_1(x^\prime_1) = d \oplus g_1(x_1)$。这相当于在$G_1$中行动一步，所以$(x_1, x_2, \dots, x_n)$也存在一个转移到$(x^\prime_1, x_2, \dots, x_n)$的行动，而此时有：
$$ \begin{aligned} a & = g_1(x^\prime_1) \oplus g_2(x_2) \oplus \cdots \oplus g_n(x_n) \\ & = d \oplus g_1(x_1) \oplus g_2(x_2) \oplus \cdots \oplus g_n(x_n) \\ & = d \oplus b \end{aligned} $$

所以$(1)$成立。

证明$(2)$：不失一般性，假设我们在$G_1$中从$x_1$行动到$x^\prime_1$，那么根据SG函数的定义，有$g_1(x_1) \neq g_1(x^\prime_1)$，所以$b \oplus g_1(x_1) \oplus g_1(x^\prime_1) \neq b$，所以$(2)$成立。

至此，我们已经成功证明了Sprague-Grundy定理。现在我们尝试将其运用到Nim游戏上：
首先对于一堆石子的情况，由于取走任意数量不为$0$的石子，所以只要不是没有石子，先手可以一次取完。简单推理可以知道$g(n) = n$。即只要有石子就先手必胜。
现在我们有许多堆石子，每一堆石子都可以视为一个Nim游戏，那么这个游戏就是许多Nim游戏加合。根据Sprague-Grundy定理，如果每一堆石子的个数为$x_i$，那么SG函数就是：
$$ \begin{aligned} g((x_1, x_2, \dots, x_n)) & = g(x_1) \oplus g(x_2) \oplus \cdots \oplus g(x_n) \\ & = x_1 \oplus x_2 \oplus \cdots \oplus x_n \end{aligned} $$

换言之，如果每堆石子数异或起来如果不为$0$，那么先手就必胜，否则将会必败。这确实是一个非常神奇的结论。同时，结合之前关于$\mathrm{N}$点和$\mathrm{P}$的一些讨论，我们知道只要能使异或和变为$0$的操作就是我们的先手必胜策略。