博弈论详解 2（SG函数和 SG定理）

传送门：博弈论详解 1（基本理论定义和 Nim 游戏）

什么是 SG 函数

接着上次的讲解，我们来了解一个更通用的模型。我们把每一个状态变成一个点（在 Nim 游戏里就代表 $a$ 数组），如果可以从一种状态转移到另一种状态，就在它们之间连一条有向边（在 Nim 里就是从 $a_1,a_2,...,a_n$ 到 $a_1',a_2,...,a_n(a_1'<a_1)$ ）根据公平博弈游戏的性质（有限步），这张图应当是 DAG（有向无环图）。真的是吗？似乎不是，在一些游戏里，它可能是多个 DAG（当然，你把 Nim 游戏的每个 $a_i$ 的变化看成独立的一张图也不是不可以，输的条件就是每个 DAG 都走到了最终局面 $0$ ）。不过为了方便，我们先考虑一个 DAG 的情况。

SG 函数的定义与计算

设有向边的集合是 $E$ ，那么 $(\{x,x'\}\in E)$ ，所以 $s g$ 函数需要用拓扑序逆序进行计算。

MEX(X) 是指不包含在整数集合 X 中的最小非负整数，如果 X 是空集，MEX(X)=0。

举个简单的例子，下图中每个点旁边的数字式是 $s g$ 函数值。
在这里插入图片描述

SG 函数与必胜条件 C

最终局面，即出度为 $0$ 的点（图中标蓝）的 $s g$ 函数值是 $0$ ，推测必胜条件 $C$ 是 $sg(x)\ne0$ 。

对于 $C$ 需要满足的三个条件进行证明（博弈论详解 1 中加粗的那三条）：
第一个条件：从一个 $sg(x)\ne0$ 的点 $x$ ，必然能走到一个点 $x^{'}$ ，使 $s g (x^{'}) = 0$ ，否则 $s g (x) = 0$ 。符合。
第二个条件：从一个 $s g (x) = 0$ 的点 $x$ ，必然走不到一个点 $x^{'}$ ，使 $s g (x^{'}) = 0$ ，否则 $s g (x) > 0$ 。符合。
第三个条件：最终局面出度为 $0$ ， $x^{'}$ 的集合为空，其 $s g$ 函数值为 $0$ 。符合。

结论：在一个 DAG 中，某个状态的必胜条件是 $sg(x)\ne0$ 。

一个DAG到多个DAG——SG 定理

定理：对于一个由 $n$ 个 DAG 组成的游戏，设第 $i$ 张图当前状态是 $sg_1,sg_2,...,sg_n$ （一开始就是每张图的初始状态），全局的状态就是这些 $sg_i$ 的集合。定义 SG 和， $sum=sg_1\oplus sg_2\oplus...\oplus sg_n$ ，必胜条件 $C$ 是 $sum\ne0$ 。

这里第一个条件的验证方法和 Nim 游戏的验证方法很像，读者可以尝试自己推算，要注意 MEX 的性质。
第一个条件：假设 $sum(sum\ne0)$ 最高位的 $1$ 表示 $2^k$ ，则存在 $sg_i$ 的第 $k$ 位是 $1$ 。由于 $s u m$ 在比 $k$ 更高的位置上都是 $0$ ，所以 $sg_i$ 在异或 $s u m$ 之后第 $k$ 位变成 $0$ ，而更高位上的数字不变，得到 $sg_i\oplus sum<sg_i$ 。根据函数定义，从代表 $sg_i$ 的点连出去的边指向的点中一定有一个点的 $s g$ 函数值是 $sg_i\oplus sum$ （用了 MEX，只要小于 $sg_i$ 的非负整数一定出现在了相邻的点上）。如果从 $sg_i$ 的点移到 $sg_i\oplus sum$ 的点，那么 $sum_{新}=sum_{原}\oplus sg_i\oplus(sg_i\oplus sum_{原})=0$ 。可以从满足 $C$ 的状态走到不满足 $C$ 的状态，符合。
第二个条件：如果此时 $s u m = 0$ ，要使其仍然是 $0$ ，必须找到一个 $sg_i$ ，他的边指向的点中有一个点的 $s g$ 函数值与 $sg_i$ 相等，此时 $s u m$ 不变。而 MEX 的集合里面如果有一个数 $x$ ，结果一定不是 $x$ 。从不满足 $C$ 的状态只能走到满足 $C$ 的状态，符合。
第三个条件：当所有 $sg_i$ 都是最终局面，无法进行任何操作的时候，所有的 $sg_i$ 都是 $0$ ，此时 $s u m = 0$ ，符合。