博弈论
策梅洛定理
考虑对于一个游戏，他满足以下的特点
-
两人单挑，轮流操作
-
信息公开透明
-
没有随机因素
-
有限步内必然结束
-
不存在平局
根据策梅洛定理：对于这样的一个游戏，任何一个局面先手或者后手其中之一必然存在必胜策略。
如何证明呢？
我们先考虑最后的状态，根据游戏规则，必然有一方必胜。
-
如果已经到了最终状态，按照游戏规则，必然有一方已经获胜
-
如果某一状态的所有后继状态都为先手必胜，那么此状态先手必败。
-
如果某一状态存在后继状态为先手必败，那么此时先手必胜。
因此，任何一个局面一定存在某一方必胜。
SG 函数
我们把上面的定理转化为数学语言。
定义先手必败的状态为零，先手必胜的状态为非零。则最后一个状态一定为 \(0\)。
根据上面的定理，判断一个局面的必胜，只需要观察它的后继状态是否存在零即可，
我们定义 SG 函数为所有子状态 SG 函数的 mex，SG 函数记录了这一状态能转移到的所有子状态。
如果子状态 SG 存在零，那么此时 SG 函数一定不为零，即 如果某一状态存在后继状态为先手必败，那么此时先手必胜。
如果子状态 SG 全部大于零，那么此时 SG 函数一定能取到零，即 如果某一状态的所有后继状态都为先手必胜，那么此状态先手必败。。
因此 SG 函数很好的模拟了上述的策梅洛定理，并且将它转化为了可运算的数学公式。
我们顺便完善 SG 函数的定义：
-
阶数：能转移到 \(0\) 至 \(n-1\) 中任一阶状态的状态，称为 \(n\) 阶状态。
-
\(SG(x)=mex \{ SG(y)|x \to y \}\)
SG 定理
定义了 SG 函数，开始研究有关 SG 函数的运算，既然是运算，就涉及不同状态间的拆分和合并。
（注意：不同 SG 函数之间为不同子游戏的并列和包含关系，而不是上文所说的状态的前驱和后继关系，放在 Nim 游戏里就是不同石子堆的关系。）
令 \(z=x+y\) （状态 \(z\) 的子状态为 \(x,y\)）。
-
如果 \(SG(x)=0,SG(y)=0\) 那么显然必败。
-
如果 \(SG(x)=1,SG(y)=0\)，后继状态只可能是 \(SG(x)=0,SG(y)=0\)，后继必败，所以当前必胜。
-
如果 \(SG(x)=1,SG(y)=1\)，后继状态只可能是 \(SG(x)=1,SG(y)=0\)，\(SG(x)=0,SG(y)=1\)，根据刚刚讨论的，无论怎么移动对方都会进入必胜态，所以当前必败。
这样得到结论，任意两个同阶的 SG 函数总能有一种操作使双方进行一轮操作后仍保持同阶，
先手无论怎么移动一定得到不同阶的后继状态。
对于任意一个不同阶的状态，对方一定能使它回到同阶的状态，这样先手又接到了一个同阶状态。
而随着越来越接近最终态，后继状态不停在减少，所以一定会落在 \(SG(x)=0,SG(y)=0\) 的必败状态上。
所以同阶必败，不同阶一定有一个同阶的后继状态，所以不同阶必胜。
以上讨论以分成两个子游戏为例，由于不同子游戏间一定是并列关系，所以 SG 函数也满足结合律和交换律。
综上，SG 函数的运算具有以下性质：
-
满足交换律，结合律。
-
单位元为零（必败状态）。
-
同阶组合必败（逆元是自己） 。
通过瞪眼法 我们通过观察得到，SG 函数的性质实际上和异或运算是一样的。
因此得出结论：\(SG(x)=SG(x_1+x_2+ \dots +x_n)=SG(x_1)\ xor\ SG(x_2)\ \dots\ xor\ SG(x_n)\)
(感性证明：性质一样，理性证明)
SG 定理证明
设 $$z=x+y$$
根据定义
\[SG(z)=mex \{ SG(w)|z \to w \} \]因为每次只能进行一次操作，设
\[x \to u，y \to v \]\[w=(u+y)\ \bigcup\ (x+v) \]\[SG(z)=mex \{ \{SG(u+y)|x \to u \}\ \bigcup\ \{SG(v+x)|y \to v \} \} \]既然 \(u,v\) 是 \(x,y\) 的任意 后继状态，不妨设
\[u=0,v=0 \]根据 SG 函数定义，显然
\[SG(u+y)=SG(u)\ xor\ SG(y) \]\[SG(v+x)=SG(v)\ xor\ SG(x) \]则
\[SG(z)=mex \{ \{SG(u)\ xor\ SG(y)|x \to u \}\ \bigcup\ \{SG(v)\ xor\ SG(x)|y \to v \} \} \]根据 SG 函数定义
\[SG(u) \ne SG(x)\ ,SG(v) \ne SG(y) \]所以
\[SG(x)\ xor\ SG(y) \ne SG(u)\ xor\ SG(y) \]\[SG(x)\ xor\ SG(y) \ne SG(v)\ xor\ SG(x) \]\[SG(x)\ xor\ SG(y) \notin \{ \{SG(u)\ xor\ SG(y)|x \to u \}\ \bigcup\ \{SG(v)\ xor\ SG(x)|y \to v \} \} \]设 \(X=SG(x),Y=SG(y),W<SG(x)\ xor\ SG(y),Z = SG(x)\ xor\ SG(y)\ xor\ W\)
\[X\ xor\ Z = W\ xor\ Y < X \]根据 SG 函数定义，必然存在
\[SG(u)=W\ xor\ Y < X \]\[W=SG(u)\ xor\ Y \]同理
\[W=SG(v)\ xor\ X \]所以对于任意 \(W<X\ xor\ Y\)，必然存在 \(W=SG(v)\ xor\ X\) 或 \(W=SG(u)\ xor\ Y\)。
因此对于任意 \(W<X\ xor\ Y\)
\[W \in \{ \{SG(u)\ xor\ SG(y)|x \to u \}\ \bigcup\ \{SG(v)\ xor\ SG(x)|y \to v \} \} \]因此根据 \(mex\) 定义
\[SG(z)=SG(x)\ xor\ SG(y) \]参考资料
完结撒花！！！
https://www.luogu.com.cn/article/shyocttb
https://blog.csdn.net/A_Comme_Amour/article/details/79347291
https://www.cnblogs.com/Ratio-Yinyue1007/p/18317441
标签：状态,xor,函数,必败,博弈论,后继,SG From： https://www.cnblogs.com/ppllxx-9G/p/18321744