SG函数

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

什么是SG函数

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

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

DAG

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

这个图上有“P点”和“N点”。P点表示必败点,N点表示必不败点(在这个图中,就是必胜点)。关于P点和N点,我们作如下约定:

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

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

PN点

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

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

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

例如,$\{0,1,2,4\}$$\text {mex}$值是$3$$\{1,2,3\}$$\text {mex}$值是$0$$\{ \}$$\text {mex}$值是$0$

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

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

如果$sg(x)$$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(0)=0,sg(1)=1,sg(2)=2\cdots$,所以$sg(p)=p$

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

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

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

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


CC0协议 @ ruanxingzhi 2017. CC0是啥玩意?
Home apps close