SG 函数学习笔记

发表于 分类于 ， 阅读次数： Disqus：

SG 函数是解决博弈论问题的一种方法。

博弈论概念

公平组合游戏

首先我们需要了解以下几个概念。

公平组合游戏指的是一类满足下列条件的游戏：

  1. 有两名玩家交替操作；
  2. 每名玩家可用的操作与玩家的先后无关；
  3. 无法移动的玩家判负。

如 Nim 游戏就属于公平组合游戏。而像绝大多数棋类游戏则不是公平组合游戏，因为玩家只能操作黑棋或白棋子，不满足条件 \(2\)，且判负也不满足条件 \(3\)。

我们将公平组合游戏中先操作的人叫做先手，之后操作的叫做后手。

有向图游戏

对于一张 DAG（有向无环图），图中仅有唯一起点，在起点上有一枚棋子，两名玩家交替移动这枚棋子，无法移动的玩家判负。这样的游戏成为有向图游戏。

我们可以发现：公平组合游戏可转化为有向图游戏，其中节点表示状态，边表示状态转移。

SG 函数则可以解决有向图游戏中先手是否有必胜策略的问题。

Nim 游戏

Nim 游戏可参照 洛谷题面。简单而言就是有 \(n\) 堆石子 \(a_n\)，两人交替取石子。每次可从任意一堆中取走任意数量的石子，且不能不取。取完所有石子的玩家获胜，问先手是否有必胜策略。

这里可以引出一个 Nim 游戏的定理：Nim 博弈先手必胜，当且仅当 \(\oplus_{i = 1}^n{a_i} > 0\)（\(\oplus_{i = 1}^n{a_i}\) 表示 \(a_n\) 的异或和）。

证明：首先当所有石子取完时必败，此时 \(\oplus_{i = 1}^n{a_i} = 0\)。然后对于任意 \(\oplus_{i = 1}^n{a_i} = 0\) 的局面，显然无论怎么取石子，都会使 \(\oplus_{i = 1}^n{a_i} \ne 0\)；对于任意 \(\oplus_{i = 1}^n{a_i} \ne 0\) 的局面，只要我们选择石头最多的那一堆，都可以一步变化为 \(\oplus_{i = 1}^n{a_i} = 0\) 的局面。

于是我们可以使用数学归纳法证明：

  • 当 \(\oplus_{i = 1}^n{a_i} > 0\) 时，先手只要每次选石子时将局面变化至 \(\oplus_{i = 1}^n{a_i} = 0\)，后手只能将局面变化成 \(\oplus_{i = 1}^n{a_i} > 0\)。又由于石子总数总能减小，且 \(\oplus_{i = 1}^n{a_i} > 0\) 时肯定有剩余石子，于是可导致最后的石子被先手拿走。
  • 当 \(\oplus_{i = 1}^n{a_i} = 0\) 时，先手无论如何都只能将状态变化为 \(\oplus_{i = 1}^n{a_i} > 0\)，于是后手就可以用上述相同的方法拿走最后石子，故先手必败。

SG 函数

mex 运算

我们首先定义一种运算 mex。设 \(S\) 表示一个非负整数即可，\(\operatorname{mex}(S)\) 即为不属于 \(S\) 的最小非负整数。可用下列等式表示：

\[ \operatorname{mex}(S) = \min\limits_{x \in \complement_\mathbb{N}S} \{x\} \]

概念

在有向图游戏中，假设从节点 \(u\) 可一步到达的节点集合为 \(E_u\)，定义 SG 函数为 \(E\) 中所有节点的 SG 函数值的集合的 \(\text{mex}\) 运算。即为下列等式：

\[ \operatorname{SG}(u) = \operatorname{mex}(\{ x | x = \operatorname{SG}(v), v \in E_u \}) \]

当 \(u\) 没有可出的节点时，我们定义 \(\operatorname{SG}(u) = 0\)。

特别得，我们定义整个有向图游戏 \(G\) 的 SG 函数值为该游戏的起点节点 \(s\) 的 SG 函数值，即 \(\operatorname{SG}(G) = \operatorname{SG}(s)\)。

性质

胜负性质

我们可以得到下列性质：

  • 对于有向图游戏 \(G\)，当 \(\operatorname{SG}(G) > 0\) 时，先手必胜；
  • 对于有向图游戏 \(G\)，当 \(\operatorname{SG}(G) = 0\) 时，先手必败。

证明：首先对于一个没有出度的点 \(u\)，满足 \(\operatorname{SG}(u) = 0\) 且该状态必败。于是我们可以使用数学归纳法证明：

  • 对于节点 \(u\)，存在可一步到达的节点 \(v\) 且 \(\operatorname{SG}(v) = 0\) 时，说明 \(SG(u) > 0\)，且此时玩家可将状态移动到 \(v\) 以达到必胜。
  • 对于节点 \(u\)，可一步到达的节点 \(v\) 均满足 \(\operatorname{SG}(v) > 0\) 时，说明 \(\operatorname{SG}(x) = 0\)，且此时无论玩家怎么移动都会将状态转移到后一个玩家必胜的状态，即当前玩家必败。

有向图游戏的和

对于一种有向图游戏 \(G\)，设 \(G\) 包含 \(n\) 种有向图游戏 \(H_n\)，玩家每次操作为任意选择一个 \(H_i\) 进行一次操作，则 \(G\) 被称为有向图游戏 \(H_{1 \cdots n}\) 的和，它的 SG 函数值满足下列等式：

\[ \operatorname{SG}(G) = \oplus_{i = 1}^n{\operatorname{SG}(H_i)} \]

证明方法与 Nim 游戏的证明方法类似。