浅谈SG函数和博弈论

· · 题解

结论大家都讲过了，这里来重点研究SG函数的所以然

（看到这里大都直接感性理解或者上结论决定来写写）

参考资料

【Part1——策梅洛定理】

我们考虑对于一个游戏，他满足以下的特点

策梅洛定理：对于这样的一个游戏，任何一个局面先手或者后手其中之一必然存在必胜策略

证明：

所以每一个状态的胜负都可以被确定

所以这些游戏可以使用记忆化搜索暴力解决

举例：报数游戏

显然这符合上述五项要求

一个数字初始为0，甲乙两人每次加上1,2,3中其中一个，达到21的人立刻获胜

设S[x]表示数字为x时胜负确定情况，1先手必胜，0先手必败

那么S[21]=0，因为此时先手没得报，无子可动判负

根据上述证明过程，可以发现

18,19,20$均可以通过一次报数转移到必败状态$21$，所以他们全都是必胜态，以此类推，可以得出本游戏先手有必胜策略，$S[0]=1

【Part2——状态的组合I】

参见题面

对于Nim游戏来说，无论几堆石子，我们都可以把石子一堆一堆拉出来讨论

像Nim游戏这样的可拆分游戏，满足两个条件

这样的情况下，双方不需要考虑这一步走完以后下一个人操作集合不同的情况，是一个公平游戏

这样的情况下，把游戏拆分成子游戏（比如把每一堆石子单拉出来讨论，或把某几堆单拉出来讨论）不会有任何影响，因为子游戏中操作和目标依然对等，所以这样的游戏是可拆分的

那么进一步讨论胜负状态的组合

如果一个游戏满足五项要求和公平游戏原则，比如Nim游戏，那么他的胜负状态不仅可以确定，而且可以随着子游戏的组合而组合

这里考虑两个子游戏的组合，因为一旦实现了两个子游戏之间的组合，就可以实现任意个的组合

（这里的游戏规定无子可动判负）

但是Nim游戏不是可以确定的吗？

我们先前的努力，並不是全部白费的，因为我们发现，必胜局面和必胜局面是不可以相提并论的——

【Part3——SG函数的登场】

考虑一堆石子的情况

$1$是必胜态，直接拿掉就好 $2$是必胜态，但是特殊情况出现了 $2$可以转移到$1$这个必胜态，也可以转移到$0$这个必败态 显然你要赢往必败态转移就好，但是实际情况中，肯定不止这一堆，上面已经说明了两个局部的必胜无法达成总体的必胜 这时候引入一个概念——**状态的阶数** 对于必败态，阶数为$0

对于1这样的只能转移到必败态的必胜态，阶数为1

而对于2这样的，既可以转移到必败态，也可以转移到1阶状态的必胜态，阶数为2

同样，对于3，他可以转移到0,1,2，所以是3阶状态

阶数的定义：能转移到0至n-1中任一阶状态的状态，称为n阶状态

接下来找主角出来：

定义状态x的阶数为SG(x)

由此可见，SG(x)>0时x为必胜态，SG(x)=0时x为必败态

同时根据上述原则，还可以观察出SG(x)的计算方法

SG(x)=mex \{ SG(y)|x->y \}

其中mex表示集合中未出现的最小的整数，x->y表示y是x的后继状态

这就很好理解了，这个整数以下的所有阶数都可以被取到，那么这个整数就是状态的阶

所以mex是这样出现的哦

【Part4——状态的组合II】

回过头来看放在我们面前的两个必胜态

观察出来，不难发现两个同阶状态放一起必败，不同阶必胜，再回去看看两个必败和一胜一败的分析，更加证实了我们的观点

【Part5——SG定理】

那么我们来探究一下对于x和y的组合状态z即x+y=z，SG(x),SG(y),SG(z)的关系吧

先找规律

SG(x)=0,SG(y)=0$，两必败组合为必败,$SG(z)=0 SG(x)=1,SG(y)=0$，一个一阶态和一个必败态，后继只能是两个必败态，所以$SG(z)=1 SG(x)=1,SG(y)=1$，同阶状态必败，$SG(z)=0

又因为每个子游戏之间地位平等，SG组合满足交换律，结合律

那么推广到一个SG(x)=k,SG(y)=0呢？

那么只有x可以被降阶到0至k-1阶，所以SG(z)=k

初步总结一下，SG数的组合运算满足以下规律

到这里我们根据性质初步猜测SG按照异或组合

再考虑SG(x)=1,SG(y)=2

那么后继状态存在下面的阶数组合

SG(x')=0,SG(y)=2,SG(z_1)=2 SG(x)=1,SG(y'_1)=1,SG(z_2)=0 SG(x)=1,SG(y'_2)=0,SG(z_3)=1

根据计算法则，SG(z)=3，诶，对了

再来几组：

SG(x)=1,SG(y)=3

那么后继状态存在下面的阶数组合

SG(x')=0,SG(y)=3,SG(z_1)=3 SG(x)=1,SG(y'_1)=2,SG(z_2)=3 SG(x)=1,SG(y'_2)=1,SG(z_3)=0 SG(x)=1,SG(y'_3)=0,SG(z_4)=1

根据计算法则，SG(z)=2

SG(x)=2,SG(y)=3

同理

SG(x'_1)=1,SG(y)=3,SG(z_1)=2 SG(x'_2)=0,SG(y)=3,SG(z_2)=3 SG(x)=2,SG(y'_1)=2,SG(z_3)=0 SG(x)=2,SG(y'_2)=1,SG(z_4)=3 SG(x)=2,SG(y'_3)=0,SG(z_5)=2

故SG(z)=1

由此观察得到，当x+y=z的时候SG(z)=SG(x) \ xor\ SG(y)

注意，这里的x+y指的是局面上的组合而非数量加和！SG(2)和SG(4)的组合应该是SG(2,4)，此处意义下2+4=(2,4)

由结合律可以推广：

SG(x)=SG(x_1+x_2+...+x_n)=SG(x_1)\ xor\ SG(x_2)\ xor \ ... \ xor \ SG(x_n)

【Part6——对SG定理的严格证明】

由计算方法，SG(z)=mex \{ SG(w)|z->w \}

由上面的设定，z=x+y

又因为w是z的后继，那么w=u+y或者w=x+v，也就是每次只能改变其中一个

展开得

SG(x+y)=mex \{ \{SG(u+y)|x->u\}∪\{SG(x+v)|y->v\} \}

接下来是精彩的一点，利用数学归纳法：

假定我们之前已经证明了SG(u+y)=SG(u)\ xor\ SG(y)和SG(x+v)=SG(x)\ xor\ SG(v)，因为u+y,x+v是x+y的后继，所以必然更加靠近终局状态

对于终局状态的SG(x)=0,SG(y)=0时候的结论已经证明

所以可以展开得到

SG(x+y)=mex \{ \{SG(u)\ xor\ SG(y)|x->u\}∪\{SG(x)\ xor\ SG(v)|y->v\} \}

下面利用SG(u+y)=SG(u)\ xor\ SG(y)和SG(x+v)=SG(x)\ xor\ SG(v)推出SG(x+y)=SG(x)\ xor\ SG(y)

证明：

设X=SG(x),Y=SG(y),U=SG(u),V=SG(v),A=\{SG(u+y)|x->u\},B=\{SG(x+v)|y->v\}

第一部分：X\ xor\ Y∉A∪B

因为x->u，故X≠U,同理Y≠V

所以U\ xor \ Y≠X\ xor \ Y，也就是说SG(x)\ xor\ SG(y)∉A

同理SG(x)\ xor\ SG(y)∉B

所以SG(x)\ xor\ SG(y)∉A∪B

第二部分：证明对于所有W<X\ xor\ Y，都有W∈A∪B

设Z=X\ xor\ Y\ xor\ W

可以发现Z异或上X,Y,W其中的至少一个时，会使其减小

但是由于Z\ xor\ W=X\ xor\ Y>W，所以排除W

因为X,Y平等，所以不妨设是X吧

也就是说Z\ xor\ X=W\ xor\ Y<X

展开

W\ xor\ SG(y)<SG(x)

则x必然存在一个后继状态u使得U=SG(u)=W\ xor\ SG(y)

也就是存在u使得W=SG(u)\ xor\ SG(y)

那么同理，上面如果设Y

就会得到存在v使得W=SG(x)\ xor\ SG(v)

因为Z至少能够使X,Y之一变小，上述两个条件至少有一个成立

所以对于所有W<SG(x)\ xor\ SG(y)，都有W∈A∪B

所以根据定义：

SG(x+y)=mex\{ A∪B \}=SG(x)\ xor\ SG(y)

【证毕】

【Part7——Nim游戏题解】

之前已经讲到，本题中SG(0)=0,SG(1)=1,SG(2)=2,SG(3)=3

因为可以取任意多石子，所以对于某一堆，SG(n)=n，因为可以转移到0到n-1任意阶的状态

然后本题中几堆石子可以组合，组合方式为按照SG定理异或

所以SG(x_1,x_2,...,x_n)=SG(x_1)\ xor\ SG(x_2)\ xor\ ... \ xor\ SG(x_n)

按照定义，直接把所以数字异或起来，大于0先手必胜，等于0则后手必胜

谢谢阅读，谢谢大家