浅谈SG函数和博弈论

## 结论大家都讲过了，这里来重点研究$SG$函数的所以然 （看到这里大都直接感性理解或者上结论决定来写写） [参考资料](https://zhuanlan.zhihu.com/p/20611132) ### 【Part1——策梅洛定理】 我们考虑对于一个游戏，他满足以下的特点 - 两人单挑，轮流操作 - 信息公开透明 - 没有随机因素 - 有限步内必然结束 - 不存在平局 #### 策梅洛定理：对于这样的一个游戏，任何一个局面先手或者后手其中之一必然存在必胜策略 证明： - 如果已经到了最终状态，按照游戏规则，必然有一方已经获胜 - 如果当前状态**所有**后继都导向先手必胜，那么本状态先手必败 - 如果当前状态**可以**导向先手必败，那么本状态先手必胜 所以每一个状态的胜负都可以被确定 所以这些游戏可以使用记忆化搜索暴力解决 #### 举例：报数游戏 显然这符合上述五项要求 一个数字初始为$0$，甲乙两人每次加上$1,2,3$中其中一个，达到$21$的人立刻获胜 设$S[x]$表示数字为$x$时胜负确定情况，$1$先手必胜，$0$先手必败 那么$S[21]=0$，因为此时先手没得报，无子可动判负 根据上述证明过程，可以发现 $18,19,20$均可以通过一次报数转移到必败状态$21$，所以他们全都是必胜态，以此类推，可以得出本游戏先手有必胜策略，$S[0]=1$ ### 【Part2——状态的组合I】 参见[题面](https://www.luogu.com.cn/problem/P2197) 对于Nim游戏来说，无论几堆石子，我们都可以把石子一堆一堆拉出来讨论 像Nim游戏这样的可拆分游戏，满足两个条件 - 双方操作对等，操作集合只和局面有关 - 双方游戏目标相同 这样的情况下，双方不需要考虑这一步走完以后下一个人操作集合不同的情况，是一个公平游戏 这样的情况下，把游戏拆分成子游戏（比如把每一堆石子单拉出来讨论，或把某几堆单拉出来讨论）不会有任何影响，因为子游戏中操作和目标依然对等，所以这样的游戏是可拆分的 #### 那么进一步讨论胜负状态的组合 如果一个游戏满足五项要求和公平游戏原则，比如Nim游戏，那么他的胜负状态不仅可以确定，而且可以随着子游戏的组合而组合 这里考虑两个子游戏的组合，因为一旦实现了两个子游戏之间的组合，就可以实现任意个的组合 （这里的游戏规定无子可动判负） - **假如我面前摆着两个必败的游戏，实际上我必败** 必败的走一步必然走到必胜的（证明过程） 等会对面再把另一个变成必败的，我又收到了两个必败游戏 最后我会收到两个无子可动的终盘游戏，我败了 - **假如我面前摆着一败一胜的游戏，实际上我必胜** 必胜的走一步能走到必败的（证明过程） 对面会收到两个必败，对面一定会输 - **假如我面前摆着两个必胜游戏，我不能确定** 随便举个例子，对于Nim游戏，随便拉出来一堆，先手肯定必胜，因为直接取光就好 但如果面前放着两堆呢？ 这时候就要讨论了吧？ 但是Nim游戏不是可以确定的吗？ 我们先前的努力，並不是全部白费的，因为我们发现，必胜局面和必胜局面是不可以相提并论的—— ### 【Part3——SG函数的登场】 考虑一堆石子的情况 $0$是必败态，显然 $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$数的组合运算满足以下规律 - 交换律，结合律 - 单位元是$0$，也就是和零阶组合阶数不变 - 逆元是自己，也就是和同阶组合必败 **到这里我们根据性质初步猜测$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$则后手必胜 谢谢阅读，谢谢大家