博弈论-SG函数

公平组合游戏（ICG）

在算法竞赛中，遇到的最多的就是公平组合游戏（ICG），一个公平组合游戏应该满足如下的性质：

• 有两名玩家
• 两名玩家轮流操作，在一个有限集合内任选一个进行操作，改变游戏当前局面
• 一个局面的合法操作，只取决于游戏局面本身且固定存在，与玩家次序或者任何其它因素无关
• 无法操作者，即操作集合为空，输掉游戏，另一方获胜

ICG具有先手必胜状态和先手必败状态，具体地说：

• 先手必胜状态：可以走到某一个必败状态（走完之后，对于后手就是必败的）
• 先手必败状态：走不到任何一个必败状态（不管怎么走，后手都是必胜的）

Nim游戏

给定 $n$ 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。

这个问题的结论是熟知的：假设第 $i$ 堆石子有 $a_i$ 个，则先手必胜当且仅当：

$a_1\oplus a_2\oplus\cdots\oplus a_n \ne 0$

我们可以分别证明，满足这个式子，可以走到 $a_1\oplus a_2\oplus\cdots\oplus a_n =0$ 的先手必败状态，如果本身就是 $a_1\oplus a_2\oplus\cdots\oplus a_n =0$ 的先手必败状态，那么不管怎么拿，都不能走到 $a_1\oplus a_2\oplus\cdots\oplus a_n \ne 0$ 的先手必胜状态

对于前者，由于 $a_1\oplus a_2\oplus\cdots\oplus a_n =x\ne 0$，设 $x$ 的最高二进制位为第 $k$ 位，说明至少存在一个数 $a_i$，其二进制的第 $k$ 位为1（假设不存在这样的数，异或和 $x$ 的第 $k$ 位只能为0），那么 $a_i\oplus x<a_i$，因为 $a_i\oplus x$ 相当于把 $a_i$ 的第 $k$ 位变成0，而更高位都不变，自然就变小，这样子，先手就可以从 $a_i$ 中拿取 $a_i-(a_i\oplus x)$ 个石子，使得其变成 $a_i\oplus x$ ，这样子，操作后的异或和为：

$a_1\oplus a_2\oplus\cdots\oplus a_{i-1}\oplus (a_i\oplus x) \oplus a_{i+1}\oplus \cdots \oplus a_n=x\oplus x=0$

这样就走到了先手必败状态

对于后者，由于 $a_1\oplus a_2\oplus\cdots\oplus a_n = 0$，先手随便选择一堆石子 $a_i$，拿走一部分，将其变成 $a_i^\prime(a_i^\prime \ne a_i)$，操作后的异或和为：

$a_1\oplus a_2\oplus\cdots\oplus a_{i-1}\oplus a_i^\prime \oplus a_{i+1}\oplus \cdots \oplus a_n=a_i\oplus a_i^\prime\ne 0$

这样就走到了先手必胜状态，且一定走到先手必胜状态

Sprague-Grundy 函数（SG函数）

SG函数是解决博弈论问题的一个利器，它能十分公式地解决大部分博弈论问题

Mex运算

设 $S$ 表示一个非负整数集合，定义 $Mex(S)$ 为求出不属于集合 $S$ 的最小非负整数的运算，例如，$Mex({1,2,3})=0$

SG函数

博弈论问题可以看作状态的转移，每一次操作都是当前局面向其他局面的转移，可以抽象成一个有向图

我们规定这个有向图中出度为0的点为终点，若 $x$ 是终点，则规定 $SG(x)=0$，对于其他的点，有如下递推：

$SG(x) = mex({SG(y_1),SG(y_2),\cdots,SG(y_k)})$

其中 $y_1,y_2,\cdots,y_k$ 为与点 $x$ 相邻的所有点

知道这个SG函数后，每个状态是先手必胜状态还是先手必败状态就十分好判断：

• $x$ 是先手必胜状态 $\Leftrightarrow$ $SG(x)\ne 0$
• $x$ 是先手必败状态 $\Leftrightarrow$ $SG(x)=0$

这个判定依据是很好理解的：如果 $SG(x)\ne 0$，说明 $x$ 的下一个状态肯定有0，先手可以走到先手必败状态，则先手必胜；如果 $SG(x)=0$，说明 $x$ 的下一个状态没有0，先手一定走到先手必胜状态，则先手必败

在实际问题中，我们抽象出来的有向图可以有很多个起点（入度为0的点），先手可以选择任何一个起点走，假设起点是 $x_1,x_2,\cdots ,x_n$，判定先手必胜还是必败的依据可以写成：

• 先手必胜 $\Leftrightarrow$ $SG(x_1)\oplus SG(x_2)\oplus \cdots \oplus SG(x_n)\ne 0$
• 先手必败 $\Leftrightarrow$ $SG(x_1)\oplus SG(x_2)\oplus \cdots \oplus SG(x_n) = 0$

证明过程类似Nim游戏的证明：先手必败，说明 $SG(x_i)=0$，那么 $SG(x_1)\oplus SG(x_2)\oplus \cdots \oplus SG(x_n) = 0$ 是显然的；若 $SG(x_1)\oplus SG(x_2)\oplus \cdots \oplus SG(x_n)=x\ne 0$，一定有 $SG(x_i)\oplus x<SG(x_i)$，而由于SG函数的Mex定义，$x_i$ 的下一个状态的SG函数值可以取到 $0\sim SG(x_i)-1$ 当中的任何一个数，因此 $x_i$ 可以转移到SG函数值为 $SG(x_i)\oplus x$ 的下一个状态，这样子就变成了先手必败状态；类似的，若 $SG(x_1)\oplus SG(x_2)\oplus \cdots \oplus SG(x_n) = 0$，先手将 $SG(x_i)$ 转移到 $SG(y_i)$，肯定有 $SG(y_i)<SG(x_i)$，这样子就变成了先手必胜状态

我们可能刚接触SG函数时会有疑问：为什么SG函数需要用Mex运算来定义，为什么判断先手必胜的依据中要用到异或，上文的证明告诉我们：Mex保证了转移过程时类似于Nim游戏的（可以转移到任何一个SG函数变小的状态），故可以直接套用Nim游戏的异或的判定依据