浅析SG函数与SG定理

前言

$\rm SG$ 函数与 $\rm SG$ 定理在博弈论中的 公平组合游戏 里起了不可或缺的作用。本文将简单介绍它们的原理及作用。

公平组合游戏

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

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

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

必胜与必败

必胜点：常用字母 $\rm N$ 表示（意为 ”Next”，即执行这一步的人会赢），若某一方在此状态，且接下来双方操作均最优，则该方必胜。

必败点：常用字母 $\rm P$ 表示（意为 “Previous”，即执行上一步的人会赢），若某一方在此状态，且接下来双方操作均最优，则该方必败。

性质：我们定义一个点的 后继状态 为从该点通过一次操作得到的新状态。显然最后游戏结束的点没有后继状态，所以一般都已知是必败点，同时这个点也一定是其它某些点的后继状态。如果某个点的后继状态中有一个是必败点，则该点必胜。如果某个点的后继状态全部是必胜点，则该点必败。因此我们通过已知的点可以推出其它点是必胜点还是必败点。

$\rm SG$ 函数

我们可以把一个 公平组合游戏 放到 DAG 上。

对于任意一个点，它指向它的所有后继状态，即连一条单向边。

若当前的图为 $G(V,E)$，则对于一个点 $u$，它的 $\rm SG$ 函数值为：

$$g(u) = {\rm mex}(\{ g(v) \mid \forall (u,v) \in E \})$$

其中 $\rm mex$ 是定义域在集合上的函数。设 $S$ 表示一个自然数集合，${\rm mex}(S)$ 返回集合 $S$ 中最小没出现过的自然数。

$$\begin{aligned} {\rm mex}(\varnothing ) &= 0\\[1ex] {\rm mex}(\{0\} ) &= 1\\[1ex] {\rm mex}(\{0,1,3,4\}) &= 2 \end{aligned}$$

结论：

有向图游戏的某个局面必胜，当且仅当该局面对应节点的 $\rm SG$ 函数值大于 $0$ 。

有向图游戏的某个局面必败，当且仅当该局面对应节点的 $\rm SG$ 函数值等于 $0$ 。

解释：

对于一个出度为 $0$ 的节点，它的 $\rm SG$ 函数值为 $0$，对应必败点。

若一个节点的某个后继节点的 $\rm SG$ 函数值为 $0$，则在 $\rm mex$ 运算后该节点的 $\rm SG$ 函数值大于 $0$ 。等价于该点的后继状态中有一个是必败点，该点必胜。

若一个节点的所有后继节点的 $\rm SG$ 函数值均大于 $0$，则在 $\rm mex$ 运算后该节点的 $\rm SG$ 函数值等于 $0$ 。等价于该点的后继状态全部是必胜点，该点必败。

应用举例：[hdu]1847

$\rm SG$ 定理

令 $G = G_1 + G_2 + \cdots + G_n$，设 $G_i$ 的 $\rm SG$ 函数值为 $g_i$，$G$ 的 $\rm SG$ 函数值为 $g$，则

$$g(X) = g((x_1,x_2,\ldots,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$ 是异或运算。