SG 定理与反常游戏

部分内容于 2026 年 3 月重制.

公平组合游戏与有向图游戏

公平组合游戏是这样的二人游戏:

  • 玩家轮流行动.
  • 任何时刻, 游戏的双方知道关于游戏的所有信息.
  • 任何相同的状态下, 无论当前由哪一方行动, 他都拥有相同的行动集合.
  • 行动集合为空的玩家失败, 另一方获胜.
  • 游戏总是在有限时间内结束(不存在无限长的行动序列).

公平组合游戏是先手必胜或者后手必胜的.

本文只考虑有限的公平组合游戏, 即游戏的状态只有有限种.

有限有向图游戏是这样的游戏: 在一个有限的有向无环图上, 初始时一个特定节点上有一个棋子. 玩家轮流行动, 每次选择当前棋子所在节点的一条出边, 将棋子移动到出边的终点. 无法行动的玩家失败. 通过将游戏的状态抽象为点, 任何行动抽象为边, 任何公平组合游戏实际上对应一个有限有向图游戏, 记所有有限有向图游戏为 $\mathcal{G}$, 它是一个可数无限集.

显然, 任何非结束的有限有向图游戏进行一次操作以后, 将得到一个新的有限有向图游戏. 我们把 $G \in \mathcal{G}$ 在进行一次操作后能得到的所有游戏状态的集合称为它的后继集合 $Next(G)$. 如果 $Next(G) = \varnothing$, 则根据定义, 它后手必胜. 如果 $Next(G)$ 中存在后手必胜的局面, 则 $G$ 先手必胜, 否则它后手必胜.

一个典型的公平组合游戏是 Nim 游戏. 它是说: 有若干堆石子, 每次玩家必须选择一堆石子, 减少它的数量 (至少减少 $1$, 可以减少至 $0$ 即删除这一堆). 如果没有非空石子堆, 则无法操作, 当前玩家失败.

对于只有一堆非空石子的 Nim 游戏, 先手显然必胜. 对于没有石子的 Nim 游戏, 后手显然必胜. 不过, 有多堆石子的 Nim 游戏, 其胜负性质并不显然.

SG 定理

游戏的和

对于两个有向图游戏 $G_1, G_2\in \mathcal{G}$, 定义两者的游戏的和 $G_1 \oplus G_2$ 是这样的游戏: 每次玩家可以任意选择一个未结束的游戏, 在选定的游戏中进行一次行动, 另一个游戏则保持不变. 无法行动的玩家失败.

探索游戏的和的胜负性质

复杂的游戏有时可以由简单游戏的和构造而成. 比如, 多堆的 Nim 游戏, 本质上是多个单堆 Nim 游戏的和. 这启发我们探索游戏的和的胜负性质.

对于任何有向图游戏 $G$, 定义 $W(G) = [G\text{ 先手必胜}]$. 不幸的是, 不存在二元运算 $\sigma$ 使得 $W(G_1\oplus G_2) = \sigma(W(G_1), W(G_2))$. 一个反例是, 堆大小分别为 $\{1,1\}$ 的 Nim 游戏是后手必胜的, 而 $\{1,2\}$ 的 Nim 游戏先手必胜; 但是 $\{1\}$ 和 $\{2\}$ 的 Nim 游戏都是先手必胜的.

更有效的做法是, 寻找这样的分类函数, 将有限的公平组合游戏映射到一个标记集 $S$ 上, 即 $f: \mathcal{G}\to S$. 它满足:

$$ \exists \sigma: S^2\to S~\forall G_1, G_2 \in \mathcal{G}~\left(f(G_1\oplus G_2) = \sigma(f(G_1), f(G_2))\right) $$

同时:

$$ \exists w:S\to \{0,1\}~(w(f(G)) = W(G)) $$

为了研究有向图游戏的胜负, 我们期待将尽可能多的不同的游戏划分为同一类, 并使 $\sigma, w$ 尽可能简单. 为此, 首先研究什么样的游戏可以被视为相同.

如果:

$$ \forall G \in \mathcal{G}~(W(G_1 \oplus G) = W(G_2 \oplus G)) $$

则记 $G_1 \simeq G_2$. 不难验证, $\simeq$ 是一个等价关系. 不妨构造 $S, f$, 使得:

$$ f(G_1) = f(G_2) \iff G_1 \simeq G_2 $$

此时, 注意到如果 $G_1 \simeq G_2$, 那么:

$$ \forall G \in \mathcal{G}~(G_1 \oplus G \simeq G_2 \oplus G) $$

所以, 设 $\sigma(f(G_1), f(G_2)) = f(G_1 \oplus G_2)$, 不难验证 $\sigma$ 是良定义的二元运算, 且满足交换律和结合律. 这是一种合理的定义 $S, f, \sigma$ 的方法.

接下来, 我们试图发掘更多 $\sigma$ 的代数性质.

对于一个后手必胜的游戏 $G_0$, 它与任何其他游戏 $G$ 的和都与 $G$ 具有相同胜负状态. 这是因为, 假设 $G$ 是先手必胜的, 则先手只需在 $G$ 上正常行动, 将它转变为一个后手必胜游戏, 则归纳地, 结论成立.

假设 $G$ 是后手必胜的, 则: 要么 $G_0$ 已经是结束状态; 要么先手行动后, $G_0$ 转变为先手必胜态, 但原来的后手可以也在 $G_0$ 上行动, 将它变回后手必胜态, 这样的过程至多重复有限次. 归纳地, 结论依然成立.

所以, 所有后手必胜的游戏本质上都和空游戏 $\varnothing$ 相同. 它们的 $f$ 值都等于 $f(\varnothing)$. 并且满足:

$$ \forall a\in S~(\sigma(a, f(\varnothing)) = a) $$

除此之外, 所有游戏与自身的和都是后手必胜的: 因为先手无论选择哪个游戏以及如何进行行动, 后手都可以在另一个完全相同的游戏上模仿. 所以满足:

$$ \forall a\in S~(\sigma(a, a) = f(\varnothing)) $$

由此可知, $(S, \sigma)$ 构成 Abel 群, 其中单位元是 $f(\varnothing)$, 每个元素的逆元是其本身.

因为所有有限有向图游戏是可数的, 所以 $S$ 必然可数.

所有单堆 Nim 游戏 (对应的有向图游戏) 彼此都不等价, 这是因为:

$$ \forall n\neq m~(W(Nim(n)\oplus Nim(n))\neq W(Nim(n)\oplus Nim(m))) $$

综上, $S$ 是可数无限集. 由此可知, 以上定义出的 $(S, \sigma)$ 是一个可数无限集上满足任何元素逆元是自身的 Abel 群. 事实上, 这样的群具有唯一的结构, 那就是 $(\mathbb N, \operatorname{xor})$.

定义一个元素 $x$ 可以被一个集合 $T$ 表出, 表示存在 $T$ 的一个有限子集, 它们全部运算起来恰好得到 $x$.

因为 $S$ 是可数无限集合, 不妨将所有元素排成一列. 定义 $Gen(S)$ 是 $S$ 中不能被 排序后标号小于自己的元素组成的集合 表出的元素组成的集合.

显然 $Gen(S)$ 是一个可数无限集, 并且 $S$ 中所有元素可以被 $Gen(S)$ 表出. 这样, 不难构造 $(S, \sigma)$ 到 $(\mathbb{N}, \operatorname{xor})$ 的同构映射.

由此得到, 必然存在从 $(\mathcal{G}, \oplus)$ 到 $(\mathbb{N}, \operatorname{xor})$ 的同态映射 $f$, 它反映了在游戏的和意义下各种游戏的性质. 其中 $f(\varnothing) = 0$, 所有后手必胜游戏的函数值都是 $0$, 也就是说, 上文中 $w(n) = [n \neq 0]$. 这个映射 $f$ 就叫做游戏的一种类 SG 函数.

SG 定理

不难发现, 类 SG 函数不是唯一的, 但存在一种最典型的类 SG 函数, 也就是标准的 SG 函数.

SG 定理:

  1. 任何有向图游戏 $G$ 都与某个单堆 Nim 游戏 (对应的有向图游戏) 等价.
  2. 任何两个不同的单堆 Nim 游戏具有不同的 SG 值.

第二点在前一节已经得到说明, 接下来证明第一点.

按照游戏的理论最长游戏回合数 (必然有限) 进行归纳. 对于空游戏, 显然它等价于空 Nim 游戏. 假设当前游戏是 $G$, 它的所有后继的理论最长游戏回合数都小于它, 所以它们都与某个单堆 Nim 游戏等价.

考虑 $G$ 的后继游戏对应的单堆 Nim 游戏的石子数构成的集合 $Follow(G)$, 取这个集合中没有出现过的最小自然数 $t$, 我们证明, $G$ 与 $Nim(t)$ 具有相同 SG 函数值. 这只需要证明 $G\oplus Nim(t)$ 后手必胜.

如果第一步操作的是 $G$, 那么: (一) 若得到的游戏 $G’$ 与 $Nim(x)(x<t)$ 有相同的 SG 值. 那么接下来, 操作的一方可以将 $Nim(t)$ 转化为 $Nim(x)$, 从而使得游戏变为后手必胜态.

(二) 若得到的游戏 $G’$ 与 $Nim(y)(y>t)$ 有相同的 SG 值, 那么接下来, 操作的一方可以继续操作这个游戏, 把它变成 $Nim(t)$, 使得游戏变为后手必胜态.

如果第一步操作的是 $Nim(t)$, 得到了 $Nim(t’)(t’<t)$, 那么 $Follow(G)$ 中一定有某个游戏的 SG 值与 $Nim(t’)$ 相同, 从而接下来, 操作的一方可以将 $G$ 转移到这个后继游戏, 使得游戏变为后手必胜态.

由此得证. 因此, 不妨定义一个有向图游戏的标准 SG 函数值是与他等价的单堆 Nim 游戏的石子数. 求解 SG 函数的方法与上文的证明过程相同.

反常游戏

反常游戏是这样的有向图游戏变体: 不能行动的人取得胜利. 反 Nim 游戏是最经典的反常游戏. 反游戏的和同游戏的和类似, 就是每次选择一个游戏进行操作, 无法操作者获胜.

注意, 不能简单地将反常游戏理解为在对应版本的有向图游戏的终止节点后接上一个节点 (“补偿操作”), 重新计算 SG 值. 这是因为, 几个反游戏的和不是对应的补偿游戏的和. 反游戏的和中, 某个子游戏结束后不能再对它操作; 但是, 如果简单地将每个反子游戏进行补偿操作转化为一般游戏, 然后再取游戏的和, 那么子游戏结束后都可以进行一次补偿操作, 这不符合反游戏的定义.

反常游戏的研究是很复杂的, 在程序设计竞赛中, 对于一类类似反 Nim 游戏的反常游戏, 有着与 SG 定理相似的结论, 这一结论在贾志浩的国家集训队论文中最早被引进, 常被称为 SG-Jia 定理 (或 SJ 定理).

定义反常游戏的 SG 值是与它拥有相同有向图结构的一般游戏的 SG 值. 这种情况下, 如果某个反常游戏满足: 任何时刻, 如果游戏的 SG 值为 0, 那么它必定已经处于终止状态; 那么我们称这种游戏是 Jia-反常游戏. 反 Nim 游戏是 Jia-反常游戏. Jia-反常游戏的和不一定是 Jia-反常游戏.

SG-Jia 定理: 一组 Jia-反常游戏的和是一个反常游戏, 这个反常游戏先手必胜当且仅当如下条件中有一个成立.

  1. 所有子游戏的 SG 值都为 $1$, 并且异或和为 $0$.
  2. 存在子游戏的 SG 值大于 $1$, 并且异或和不为 $0$.

下面我们证明 SG-Jia 定理. 边界条件是没有未终止游戏, 此时先手必胜, 它满足第一条 (空真). 我们按照一个游戏的理论最长游戏时间进行归纳.

如果当前子游戏的 SG 值都是 $1$, 显然先手必胜只和个数的奇偶性有关.

如果存在当前子游戏的 SG 值大于 $1$, 并且异或和不为 $0$. 那么有两种情况:

  1. 如果只有一堆的异或和大于 $1$, 那么先手可以任意选择将这一堆取成 $0$ 还是取成 $1$, 从而使得游戏进入第一类中后手必胜的情况, 从而使自己获胜.
  2. 如果有不止一堆的异或和大于 $1$, 那么先手选择一堆, 操作后一定可以转化为第二类中后手必胜的情况, 即异或和为 $0$ 但是存在子游戏 SG 值大于 $1$.

如果存在当前子游戏的 SG 值大于 $1$, 但是异或和为 $0$. 那么此时, 至少存在两个子游戏的值大于 $1$ (否则 $2$ 以上的二进制位无法抵消). 所以先手无论如何操作, 都会转化为至少存在一堆 SG 值大于 $1$ 而异或和不等于 $0$ 的情形, 从而他必败. 综上所述, SG-Jia 定理得证.