SG函数与SG定理

重新看博弈论的题。
从最开始的nim游戏开始，这种取石子游戏是最基本的一种博弈论。

必胜点N与必败点P

必胜点和必败点的概念：
P点：必败点，换而言之，就是谁处于此位置，则在双方操作正确的情况下必败。
N点：必胜点，处于此情况下，双方操作均正确的情况下必胜。

必胜点和必败点的性质：

1. 所有终结点是 必败点 P 。（我们以此为基本前提进行推理，换句话说，我们以此为假设）
2. 从任何必胜点N 操作，至少有一种方式可以进入必败点 P。
3. 无论如何操作，必败点P 都只能进入 必胜点 N。

首先通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。（在这里我们保证就算必败的人也一定使用最优的方案）

很显然，只是拥有一定规律的。它含有必胜点与必败点，我们发现，如果堆数只剩下一堆，那么一定是先取的人赢，如果有一堆加一个，那么先取的人将一堆取的只剩一个，就剩下只有一个石子的两堆。很明显，又是先取者赢。根据一定的判断，后来的状态跟之前存在一定的关系，我们就可以找到一定的规律来求解问题。

还记得之前在做联赛初赛模拟题的时候，有几道博弈论的题目。当时看的题解，说的是将每堆存在的数转化为二进制，然后比较每一位上 ‘1’ 的个数。我们比较出来的结果，若一个数位上有奇数个 ‘1’ ，我们称之为奇数位，若一个数位上有偶数个 ‘1’ 我们称之为偶数位。如果有一个奇数位，先取者必胜，因为当先取者将那一堆的那个 “1” 取掉之后，剩下都是偶数位，后取的人不管怎么操作，都会将偶数位操作成奇数位，那么先取的人就可以对称取，把出现的奇数位再取成偶数位。而对于 $2n+1$ 个奇数位和 $2n$ 个奇数位的情况请读者自证。

举个例子：
假设有5堆，每堆分别是 7,10,2,8,5。然后问先取的人必胜还是必败。
先将这些数转换为二进制数。

然后再将其右对齐

也就是先取者在第1、2、3堆里面取掉 $2$，就必胜了。

显然可以感性的理解这样做的原因。

我们再看一下实际的原理：
1、最后的游戏状态必然是所有石子个数为0，也可以看成所有石子异或为0。
2、假如现在所有石子异或起来为J，我们用Ai表示第i堆石子个数，总共n堆。那么就有
$A1xorA2xorA3\dots \dots xorAn=j$，我们把 $j$ 二进制表示，则$A$中必有一个数最高位与j的最高位同为1（位数一样），不然j的那个1是哪来的？ 然后我们令这个数是$Am$，所以 $Amxorj$ 必然小于$Am$，显然最高位被消掉变小了。我们可以取石子把$Am$变成$Amxorj$，那么对于原式就是 $A1xorA2xor\dots \dots xorAnxorj=jxorj=0$；
3、如果异或起来为0，那么如果任意拿掉石子，新的异或一定不为0，这个证明十分简单，留给读者解决.
原文：https://blog.csdn.net/kamisama123/article/details/77649118

比我上面写的更加专业一点？因为我那是自己YY 的。
看了上面的一系列讲解，估计读者们都已经对nim游戏有了更深入的了解。
综合上面的，我们得到一个 定理 ：NIM博弈先手必胜当且仅当 $A1xorA2xorA3\dots \dots xorAn!=0$
将NIM游戏推广，我们就得到了公平组合游戏ICG，他拥有如下性质：

1. 由2名玩家交替行动
2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关
3. 不能行动的玩家判负。

进入正题

SG函数

mex运算：

首先定义一个 $mex()$ 运算。我也不知道为什么学习SG函数一定要学习这个 $mex$ 运算。但是显然用的到。
$mex(s)$ 为求出不属于集合 $S$ 的最小非负整数的运算，即： $mex(s)=min【x】,x\in N,x\notin S$

好，来看真正的SG函数。

给一到例题：
给定一个有向无环图，图中又一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

接下来的讲解来自lyd的《算法进阶指南》。

在有向图游戏中，对于每个节点 $x$ 设从 $x$ 出发有 $k$ 条边，分别到达节点 y 1 , y 2 , y 3 . . . y k y_1,y_2,y_3...y_k y1​,y2​,y3​...yk​，定义$SG（x）$为 $x$ 的后继结点 y 1 , y 2 , y 3 . . . y k y_1,y_2,y_3...y_k y1​,y2​,y3​...yk​ 的 $SG$ 函数值构成的集合再执行 $mex$ 运算的结果，即：
$S$ G ( x ) = m e x ( S G ( y 1 ) , S G ( y 2 ) , . . . S G ( y k ) ) G(x)=mex(SG(y_1),SG(y_2),...SG(y_k)) G(x)=mex(SG(y1​),SG(y2​),...SG(yk​))
特别的，整个有向图游戏 $G$ 的$SG$函数值被定义为有向图游戏的起点$s$的 $SG$函数值，即 $SG(G)=SG(s)$。

有向图游戏的和
设 $G1,G2,G3...,Gm$ 是 $m$ 个有向图游戏。定义有向图游戏 $G$，它的行动规则是任意选择某个有向图游戏$Gi$并在$Gi$上行动一步。$G$ 被称为有向图游戏 $G1,G2,G3...,Gm$ 的和。
有向图游戏的和的 $SG$ 函数值等于它包含的各个子游戏 $SG$函数值的异或和（其实为什么是异或和在前面的铺垫中也能够迷迷糊糊的清楚一些，实在不行请补一补位运算）。即 $SG(G)=SG(G1)xorSG(G2)xor...xorSG(Gm)$

到这里，我还是 一脸懵逼.jpg。只能硬着头皮往下看。

定理
有向图的某个局面必胜，当且仅当该局面对应节点的$SG$函数值大于0。
有向图的某个局面必败，当且仅当该局面对应节点的$SG$函数值等于0

读者可以这样理解（终于说出这个SG函数的边界情况了！！）（还有我LaTeX我懒的打了）
在一个没有出边的节点上，棋子不能移动，它的SG函数值为0.对应必败局面。
若一个节点的某个后继节点SG值为0，在 mex 运算后，该节点的SG值大于0。这等价于，若一个局面的后继局面中存在必败局面，则当前局面为必胜局面。（其实这就跟开始讲的有些相似，也就是说状态之间互相影响，边界状态影响之前的状态）
若一个节点的某个后继节点SG值均不为0，在 mex 运算后，该节点的SG值为0。这等价于，若一个局面的后继局面中存在必胜局面，则当前局面为必败局面。

这些话读着拗口，但一定要细细品读，就能深刻的了解SG函数。我个人认为SG函数跟dp的思想有些类似，也就是一个状态转移的思想。

$\text{对于以上 有向图游戏我唯一的疑问就是为什么多个图的SG值，就是各个小图的SG值的异或和。}$

我突然想起来，这不是就是NIM游戏吗？每个小堆就是一个小的有向图游戏。然后对于能否在总的必胜，就决定在小的是否能必胜，然后这就运用到NIM 游戏的那个定理了，各个小块的异或和就是决定性因素。

我想解决的问题是这道 games on DAG
下次更新。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！