爱思考的你，想没想过SG函数为什么偏偏要取异或和
SuperJvRuo
2018-02-19 20:37:28
## 零、一些碎碎念
作为OIer，我们总会遇到一些博弈论题目。
[【P1247】取火柴游戏](https://www.luogu.org/problemnew/show/P1247)
[【P2252】取石子游戏](https://www.luogu.org/problemnew/show/P2252)
[【P2148】【SDOI2009】E&D](https://www.luogu.org/problemnew/show/P2148)
曾经，学哥学姐或是教练抛出一个SG函数后告诉我们：
对于这样的题目，将所有的mex(minimum excluded)取xor和，如果结果为0，我们面对的就是败态；否则就是胜态。
一对聪明绝顶的CP：Alice和Bob，
一套使人一头雾水的博弈论，
一个神来之笔般的SG函数，
一个让人匪夷所思的xor运算……
想必所有人学到博弈论，用SG函数AC掉一道又一道题时，都会~~一边感叹着这函数真TM好用，一边~~在脑中冒出一个大大的问号：这么牛逼的SG函数以及异或运算都是怎么想出来的呢？
这篇博客，就来谈一谈SG函数的发现与证明。
## 一、Nim博弈
初始时有若干堆石子，游戏双方轮流选定一堆并从中拿走任意颗石子（可以把一堆拿光），拿走最后一颗石子者为胜。
显然，这道[【P1247】取火柴游戏](https://www.luogu.org/problemnew/show/P1247)就是Nim博弈的板子题。
## 二、策梅洛定理
自然地，我们会关心一个问题：给定一个初始状态，先手玩家是否有必胜策略？
其实啊，我们如果倒着来推的话：
对于一个终局状态：
根据规则，我们就可以钦定面对此状态的人的胜负，在Nim博弈中，终局状态（即所有石子都被对面取光）是负态，我们可以把终态视为一种特殊的负态；
对于一个非终局状态：
**如果我们能留给对手的所有可能状态都是胜态，那么该状态为负态；**
**如果我们能留给对手的所有可能状态中存在负态，那么该状态为胜态。**
所以，此游戏中的任何一个可达到的状态，要么是胜态，要么是负态，前提是：
* 双人、回合制；
* 信息完全公开；
* 无随机因素；
* 必然在有限步内结束；
* 没有平局。
这就是策梅洛定理(Zermelo's theorem)。
由此亦可知，**经过一步行动，负态只能变成胜态，胜态可以（但不一定）变成负态。**
同时，根据这样的性质，我们就可以利用记忆化搜索来暴力解决某些博弈论问题，比如这道：[【Trie、博弈论】CF455B A Lot of Games](https://www.luogu.org/problemnew/show/CF455B)，或是打表找出规律。
## 三、状态的组合
### 1、状态组合的性质
通常来说，在题目中的游戏里，玩家的任意一步行动都只能影响一个子状态（对于E&D这样的题来说，我们将一个二元组视为一个子状态）。
显然，Nim博弈就是一些子状态（一堆石子/火柴）的组合。如果能利用子状态的胜负情况推出状态组合的胜负情况，我们就可以看出Nim博弈的胜负了。
我们不妨定义状态组合运算@（这是我随便定义的），状态组合运算@应具有以下性质：
* **交换律**：如果有两堆石子构成二元组$ (a,b) $，显然，状态$ (b,a) $和它是一样的，即$ a @ b == b @ a $;
* **结合律**：如果有三堆石子$(a,b,c)$，显然，a与$(b,c)$组合和$(a,b)$与c组合也是一样的，即$a @ (b @ c) == (a @ b) @ c$。
因为@具有结合律，所以我们只要研究明白两个状态如何组合，就可以进行若干个状态的组合了。
### 2、两个状态的组合结果
#### （1）、负态 @ 负态
负态 @ 负态 = 负态。先手只能将组合变成胜态 @ 负态；而后后手就可以把胜态变成负态，把负态 @ 负态返还给先手方。直到两个负态均为终态为止。
#### （2）、胜态 @ 负态
由（1）可知，这种状态是胜态。必胜策略就是把胜态变成负态，把负态 @ 负态留给后手。
#### （3）、胜态 @ 胜态
对于这种情况，我们不应把一个胜态转化为负态，因为你将把胜态 @ 负态 = 胜态留给后手。所以我们不得不把胜态转化成另一个胜态，把胜态 @ 胜态留给后手。后手自然会采取与你相同的策略。
然而，游戏是有限的，迟早有一个玩家仅能把局面转化成胜态 @ 负态，输掉游戏。问题是，我们不知道会是哪个玩家、在哪一步输掉游戏。因此，我们需要知道两个胜态的更多性质。
## 四、SG函数
举个例子：
有四堆石子：1、2、3、7。分开单独来看，每堆石子也就是每个子状态，都是胜态。
第一堆石子1只能变成终负态0。我们不妨称它为一级胜态。第二堆石子2只能变成1或0，可以被称为二级胜态。以此类推，3是三级胜态，7是七级胜态。
我们就发明了如下定义：**一个胜态可以变为1～n-1级的胜态，则称该胜态为n级胜态。**这个级数也就是对该胜态的所有后续情况取**mex(minimum excluded，不包含在内的最小自然数)**的结果。
胜态组合的胜负，与胜态的级数密切相关。
当你面对两个级数相同的胜态时，你只能认输，因为你的每一次操作都可以被对手拷贝。你取走这一堆的一颗石子，他就会取走另一堆的一颗石子。于是，当你取光一堆石子时，另一堆也被对手取光，对手就赢得了胜利。
而当你面对两个级数不同的胜态时，你就可以把级数较高的胜态转化为另一个胜态的同级胜态，把两个级数相同的胜态留给对手，你便获胜了。
其实啊，我们定义的胜态级数正是传说中的SG函数：
$$ SG(A)=mex \lbrace SG(B)|A\rightarrow B \rbrace $$
## 五、SG函数的组合
### 1、SG函数组合的猜想
我们继续第三节的思考，现在我们解决了两个胜态组合后的胜负情况，但我们还要求出这两个组合成的状态的SG函数值，才能进行更多状态间的组合运算。
我们已经知道状态组合$@$有如下性质：
* 交换律：如果有两堆石子构成二元组$ (a,b) $，显然，状态$ (b,a) $和它是一样的，即$ a @ b == b @ a $;
* 结合律：如果有三堆石子$(a,b,c)$，显然，a与$(b,c)$组合和$(a,b)$与c组合也是一样的，即$a @ (b @ c) == (a @ b) @ c$。
* 状态$A@0=A$，一堆空的石子对结果没有影响
* 状态$A@A=0$，两个SG相同的状态组合是负态
当两个状态的SG函数不同且都不为0时呢？我们举几个例子：
1. $(1,2)$的后续情况包括：$SG(0@2)=2$，$SG(1@0)=1$，$SG(1@1)=0$。故$SG(1@2)=mex(\lbrace SG(1@A)|2\rightarrow A\rbrace\bigcup \lbrace SG(B@2)|1\rightarrow B\rbrace)=3$
2. $(1@3)$的后续情况包括：$SG(0@3)=3$，$SG(1@0)=1$，$SG(1@1)=0$，$SG(1@2)=3$。故$SG(1,3)=mex(\lbrace SG(1,A)|3\rightarrow A\rbrace\bigcup \lbrace SG(B,3)|1\rightarrow B\rbrace)=2$
3. $(2,3)$的后续情况包括：$SG(0,3)=3$，$SG(1,3)=2$，$SG(2,0)=2$，$SG(2,1)=3$，$SG(2,2)=0$。故$SG(2,3)=mex(\lbrace SG(2,A)|3\rightarrow A\rbrace\bigcup \lbrace SG(B,3)|2\rightarrow B\rbrace)=1$
当然，我们是学过的，我们知道$SG(A@B)=SG(A) xor SG(B)$，也的确，$Axor0=A$，$AxorA=0$，$1xor2=3$，$1xor3=2$，$2xor3=1$。
但是，
我们只是通过举例的方法，发现了状态的组合对应着SG函数的异或。我们并没有证明通过子状态的SG函数能够唯一确定母状态的SG函数（即$xor$运算结果的唯一性），也没有证$xor$是能够达到这个目的的唯一一种运算。
能否证明出xor的正确性呢？
### 2、xor运算正确性的证明
已知：上面我胡扯的所有内容
求证：$SG(A@B)=SG(A) xor SG(B)$，其中$@$代表状态的组合
证明：
由SG函数定义可知$SG(A@B)=mex(\lbrace SG(A@C)|B\rightarrow C\rbrace\bigcup \lbrace SG(D@B)|A\rightarrow D\rbrace)$
我们可以按游戏状态的拓扑序排序，使用数学归纳法，终态$SG(0@0)=0=0xor0$成立，先使得$SG(A@B)=mex(\lbrace SG(A)xorSG(C)|B\rightarrow C\rbrace\bigcup \lbrace SG(D)xorSG(B)|A\rightarrow D\rbrace)$
我们只需证明
1. $SG(A)xorSG(B)\notin (\lbrace SG(A)xorSG(C)|B\rightarrow C\rbrace\bigcup \lbrace SG(D)xorSG(B)|A\rightarrow D\rbrace)$
2. $\forall E<SG(A)xorSG(B)$，有$E\in(\lbrace SG(A)xorSG(C)|B\rightarrow C\rbrace\bigcup \lbrace SG(D)xorSG(B)|A\rightarrow D\rbrace)$
首先，证明第一个式子：
$\because A\rightarrow C,B\rightarrow D$
$\therefore SG(A)\neq SG(C),SG(B)\neq SG(D)$
$\therefore SG(A)xorSG(B)\notin (\lbrace SG(A)xorSG(C)|B\rightarrow C\rbrace\bigcup \lbrace SG(D)xorSG(B)|A\rightarrow D\rbrace)$
第二个式子的证明有些难了：
我们定义$F=SG(A)xorSG(B)xorE$。
用$F$与$SG(A),SG(B),E$三者异或，至少使得其中一者减小（因为$F$非零，$F$的二进制表示中最高位的$1$必来自$SG(A),SG(B),E$三者之一，$F$与这一者异或会使它减小）。
但这一者不会是$E$，因为$FxorE =SG(A)xorSG(B)> E$。
不妨设这一者是$SG(A)$，即有$FxorSG(A)=E xorSG(B)<SG(A)$。此时，可取A的一个次态C使得$SG(C) = ExorSG(B)$，由SG数的定义，这是一定能做到的。
这就证明了$\forall E<SG(A)xorSG(B)$，有$E\in(\lbrace SG(A)xorSG(C)|B\rightarrow C\rbrace\bigcup \lbrace SG(D)xorSG(B)|A\rightarrow D\rbrace)$。
故$SG(A+B) = SG(A) xor SG(B)$。
## 六、上代码
### P1247取火柴游戏
```
#include<cstdio>
#include<cctype>
int k,n[500005];
int Read()
{
int x=0;
char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c))
{
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x;
}
int main()
{
k=Read();
int x=0;
for(int i=1;i<=k;++i)
{
n[i]=Read();
x^=n[i];
}
if(!x)
{
puts("lose");
return 0;
}
for(int i=1;i<=k;++i)
{
if((n[i]^x)>=n[i])
continue;
printf("%d %d\n",n[i]-(n[i]^x),i);
n[i]^=x;
break;
}
for(int i=1;i<=k;++i)
printf("%d ",n[i]);
}
```