SG函数

SG函数的坑弃了很久了……高一的大佬已经开始D我了……

什么是SG函数

首先我们需要知道，有限状态博弈问题可以表示为一个DAG，每个节点表示一个局面，而每个选择就相当于一条边。

例如取石子问题。一共$5$个石子，玩家可以取两个或者取一个，先取完者胜。那么这个图是长成这样的：

点上的数表示“在这个局面下，还有多少个点没有被取”。

这个图上有“P点”和“N点”。P点表示必败点，N点表示必不败点（在这个图中，就是必胜点）。关于P点和N点，我们作如下约定：

无路可走的点称为“终点”(Terminal)。终点是P点。
如果一个点能走向P点，那么它是N点。因为可以让对手输。
如果一个点只能走向N点，那么它是P点。因为只能让对手赢。

那么根据这几个约定，上面的博弈图可以画成下面这样。橙色表示P点，绿色表示N点。

上图的意思是，遇到$3$或$0$局面的玩家必败，否则必胜。由于$5$是N点，所以这个游戏是先手必胜的。（先手取两个石子，使对手面临$3$的局面，即可获胜）

那么什么是SG函数呢？SG函数就是判断了上面的三个约定，并把结果用数值表示出来。

我们首先定义$\text{mex}$运算，它是作用于集合上的运算。设$S$是一个整数集合，则$\text{mex}\left(S\right)$表示没有在$S$中出现的最小非负整数。

例如，$\{0,1,2,4\}$的$\text{mex}$值是$3$，$\{1,2,3\}$的$\text{mex}$值是$0$，$\left\{\right\}$的$\text{mex}$值是$0$。

在之前的图上，每个点表示一个状态。

SG函数给了每个点一个值：$sg\left(x\right)=\text{mex}\left\{sg\right(p\left)|p是x的儿子节点\right\}$。终点的$sg$值是0。

如果$sg\left(x\right)$为$0$，那么$x$是P点；否则$x$是N点。

SG函数有一个神奇的特性：如果一个游戏可以分成几个同时进行的子游戏，那么整个局面的$sg$值，就是所有子游戏的当前节点$sg$值的异或和。

Nim游戏

我们借助Nim游戏来理解SG函数。

Nim游戏的规则是：有$n$堆石子，第$i$堆石子有$a_i$个。每次可以从一堆石子里面取走任意个（至少取一个；允许一次取完）。

我们先分析某一堆石子的SG函数。由于$p$号节点可以走到$0,1,2\cdots p-1$，所以$sg\left(0\right)=0,sg\left(1\right)=1,sg\left(2\right)=2\cdots$，所以$sg\left(p\right)=p$。

因此，每一堆石子的$sg$函数都已经知道。在初始的时候，第$i$堆石子当前局面的$sg$值为$a_i$。（还没有石子被取）

我们的博弈是个大游戏，每一堆石子都是一个小游戏。因此整个局面的$sg$值就是每一堆石子的$sg$值的异或和。也就是说：

$$sg\left(begin\right)=a_1\otimes a_2\otimes a_3\cdots \otimes a_n$$

如果$sg\left(begin\right)$的函数值为$0$，说明整个游戏的最初局面是P点，先手必败。否则整个游戏先手必胜。