无偏博弈

2026-07-19

无偏游戏的定义

我们在幼儿园或许玩过一种二人报数游戏：从 开始轮流报数，每次将当前数减少 或 ，且不得小于 ，谁先报出 就胜利。

来分析一下这个游戏：

当 或 ，先手必胜，因为第一个人可以直接报完

当 ，先手必败，因为无论第一个人报了 还是 ，第二个人都可以报完

当 或 ，先手必胜，第一个人总是可以把 的先手必败局面留给对方

当 ，先手必败，因为第一个人不得不把 或 的先手必胜局面留给对方

以此类推，容易证明当 时，先手必败，否则先手必胜。

报数游戏的精神是：两个人轮流做出行动，在相同局面下可选择的行动一样，最后无路可走的一方失败。

这就是组合博弈论中，正规规则无偏游戏的精神，正规规则无偏游戏满足以下要求：

1. 两人轮流行动
2. 完全信息
3. 没有随机因素
4. 双方在同一状态有相同的合法行动
5. 正规规则：无法行动者失败
6. 不存在无穷行动序列，即游戏总会终止

现在形式化地定义无偏游戏，但是只限制在有限游戏上，来避免无限游戏带来的集合论技术细节。

无偏游戏由一个三元组刻画：

是状态集合， 描述状态之间的后继关系， 是初始状态，需满足：

• 是一个有向无环图（DAG）
• 中的所有状态由 可达。

此外，如果游戏 和 存在保持初始状态的图同构，则认为它们是同一个游戏，因此我们始终在商掉同构等价的基础上工作，不深入讨论技术细节。

定义游戏的高度 为起点为 的最长路径长度，以边数计，也就是一局游戏最多能够进行的步数。

对任意状态 ，由 及其所有从 可达状态组成的带根子图仍然是一个游戏，记为 ​。以后不区分状态 与以 为起点的子游戏 ​

必胜与必败

由于状态图是 DAG，我们可以递归地计算每个状态是（当前行动者）必胜还是（当前行动者）必败。

1. 叶子节点，即没有后继状态的节点是必败的
2. 如果 存在必败的后继节点，那么 必胜
3. 反之， 的所有后继节点都必胜，那么 必败

这就证明了每个游戏状态都必胜或必败，把必胜状态的集合记为 ，必败状态的集合记为 ，则

由于并不区分游戏和状态， 和 同样适用于游戏。

游戏的代数

先定义游戏的和。

对于游戏 和 ，直观上，将两个游戏的和定义为这样一个新游戏：每一轮，当前玩家可以选择在 中行动还是在 中行动，最后在所有游戏中都没有行动可选的玩家失败。

形式化地，对于游戏 ，，定义

（在图同构的意义上，）加法满足交换律和结合律

接下来，定义零游戏 为 ，它没有合法移动，所以是必败的，

容易验证，在图同构的意义上，它是加法的单位元，即

下面这个性质总是成立：

这是因为，后手总是可以采取模仿策略，和先手选择对称的行动，使先手最终无路可走而失败。

第二个性质是

这是显然的

另一组性质是：

这说明提供一个必败游戏作为独立分量，不会改变原游戏的胜负类型，我们使用数学归纳法来证明这组性质。

若 ，则 ，性质成立

若 ，且这组性质对 的情况均成立，现在设 ，对 分类讨论：

若 ，则图 中存在 后继状态，选择这个后继状态，把局面 交给对手，，。根据归纳假设，这是 型的必败局面，所以 必胜

若 ，则下一步无论在 还是 中选择，同理必定把归纳假设中 型的必胜局面交给对手（交换律），所以 必败

综上，性质始终成立，完成归纳步

这个命题的推论是，一个 游戏在加法中总是不影响胜负类型，因此与零游戏 等价，这启发我们定义游戏之间的等价关系。

若游戏 满足:

则称 和 等价，记为

取 可知，等价保持胜负类型。

自反，对称和传递性自然成立，实际上容易验证这还是一个同余关系

有推论

因此能够对游戏的等价类定义加法

加法的结果不依赖代表元的选取，因此是良定义的。

由先前证明的定理可以立刻得到：

考虑商集

有

而

所以

所以 是交换群，且每个非零元素的阶均为

由该群的性质可以导出下面的命题

此外，这样的群自然是 上的线性空间。只需对于 ，令

则容易验证线性空间公理成立。

为了使任何等价的 与 都能在我们遇到的环境中互换，还需要后继等价引理：

需要证明

对 使用强归纳：

当 ，可知 ，只需证明 ，因为 和 地位对称。

由 可知， 存在必败后继局面，记为

那么存在 ， 也是 的必败后继局面，所以

当 ，只需证明 ，因为 和 地位对称。

由 可知， 存在必败后继局面。

如果这个必败后继局面是 ，那么存在 是 的后继， 也是 的必败后继。

如果这个必败后继局面是 ，那么 ，由归纳假设，，所以

得证。

接下来，我们可以在所有情形下忽略等价游戏间的差异，从而完全在商集 上工作。为了简化记号，用 替代 ，所以写 而不是 或 是合法的。

Nim 游戏

我们考虑一族游戏，称为 Nim 游戏，规则如下：

有 堆石子，第 堆有 个（），每次行动可以从一堆石子中取出任意多个，先取完所有石子者获胜；等价地，轮到行动时无石子可取的玩家失败。

当 时，若这堆石子有 个，则把这个 Nim 游戏称为

容易发现下面的事实成立：

3. 每个 Nim 游戏都是

由性质 4 和性质 5 可以推出

接下来，借助线性空间的性质深入研究 Nim 游戏的代数结构

首先， 是一个线性子空间

其次， 是一个线性子空间，这个线性子空间是一维的，基向量只能选取

我们继续扩大这个线性子空间，由性质 6， 不在集合 中，所以可以考虑加入 后张成的线性子空间

选取基为 ，则 中的元素可以表示为 ，共有 个元素，分别为

事实上，

回忆一下，我们始终在商集上工作，所以 背后的含义是 ，而不是 与 在原始游戏的意义上有图同构

这是因为， 的后继状态为

它们分别等价于 ，正好是 的后继状态，由后继等价引理，

所以

下一步把 加入空间中，并作为基向量，得到

新产生的向量必然是

其中

考虑

的后继集合，为

其中

由线性子空间的平移性质或子群的性质

所以

由后继等价引理

考虑

的后继集合，为

所以

考虑

的后继集合，为

所以

这就证明了

完全相同的论证可以归纳进行：

若

我们先证明

对 做强归纳

当 ， 平凡成立

当 ，

的后继状态集合是

由归纳假设

而

所以后继状态集合恰为

由后继等价引理，

得证。

进一步，加入 后扩出的线性空间为

最终得到

这就是所有 Nim 游戏构成的 -线性空间，它的基是

同时还能得到如下定理

所以，所有 在基 上的坐标表示，恰和 的二进制位对应

例如

这也可以用来计算 Nim 游戏的加法

一般地，令 表示异或运算，则

所以每个 Nim 游戏都与一个单堆 Nim 游戏等价。

SG 定理

在上一节中，我们证明了每个 Nim 游戏都与一个单堆 Nim 游戏 等价。SG 定理（Sprague-Grundy 定理）进一步指出，每个无偏游戏都与一个唯一的单堆 Nim 游戏 等价。

对游戏 的高度 进行强归纳

当 ，

当 ，由归纳假设，所有后继状态都与某个单堆 Nim 游戏等价，记为

对集合 ，定义 为没有在 中出现过的最小非负整数。自动地，

令 ，下面证明 与 等价：

只需证明 ，即 的每个后继都属于

如果在 中走一步，那么 变为 ，满足 ，所以 在 的后继中，因此 存在 后继 ，它本身属于

如果在 中走一步，那么 变为 ， 变为 ，然而 ，所以

归纳部分证毕。

由于 ，和 等价的单堆 Nim 游戏是唯一的，这就证明了 SG 定理。

SG 定理说明单堆 Nim 游戏构成商集 的代表元系。

由唯一性，可以对每个游戏定义 SG 函数：若 ，则定义 。

以下性质立刻成立：

SG 函数和二进制展开分别给出 -线性空间同构

这里， 表示的是直和，只允许有限个位置非零。

注意到，以上论证过程同时给出了一个计算 SG 函数的朴素算法。

1. 得到状态图
2. 对状态图拓扑排序
3. 逆拓扑序计算

拓扑排序的时间复杂度为 ，下面考虑计算过程的时间复杂度，使用 word-RAM 模型，忽略数位长度的影响。

对每个节点 ，设出度为 ，则 ，只需建立下标范围 的bool 数组，然后处理 个出边，标记 范围内后继节点的 SG 值，最后再扫描一遍 区间，直到找到第一个未被标记的数，这就是 的值。最后直接清空这个 bool 数组即可。整个 SG 计算过程的时间为

因此，第 2，3 步的时间总和为

如果游戏本身以 的邻接表形式输入，那么第一步的时间为 。由于输入长度 是 的，这立刻给出一个计算 SG 函数的 算法。

如果游戏本身并不以 形式输入，则使用这个朴素算法，需要先计算出状态图 ，再在状态图上拓扑排序和计算。具体的时间复杂度取决于计算状态图的效率，但可以知道这是 的。

当然，许多时候并不需要显式计算出整个状态图，用更好的方式计算 SG 函数。考虑开篇的报数游戏，很容易直接计算游戏的 SG 值。

设 为从 开始的报数游戏的 SG 值，则