爱思考的你，想没想过SG函数为什么偏偏要取异或和

SuperJvRuo · 2018-02-19 20:37:28 · 个人记录

零、一些碎碎念

作为OIer，我们总会遇到一些博弈论题目。

【P1247】取火柴游戏

【P2252】取石子游戏

【P2148】【SDOI2009】E&D

曾经，学哥学姐或是教练抛出一个SG函数后告诉我们：

对于这样的题目，将所有的mex(minimum excluded)取xor和，如果结果为0，我们面对的就是败态；否则就是胜态。

一对聪明绝顶的CP：Alice和Bob，

一套使人一头雾水的博弈论，

一个神来之笔般的SG函数，

一个让人匪夷所思的xor运算……

想必所有人学到博弈论，用SG函数AC掉一道又一道题时，都会~~一边感叹着这函数真TM好用，一边~~在脑中冒出一个大大的问号：这么牛逼的SG函数以及异或运算都是怎么想出来的呢？

这篇博客，就来谈一谈SG函数的发现与证明。

一、Nim博弈

初始时有若干堆石子，游戏双方轮流选定一堆并从中拿走任意颗石子（可以把一堆拿光），拿走最后一颗石子者为胜。

显然，这道【P1247】取火柴游戏就是Nim博弈的板子题。

二、策梅洛定理

自然地，我们会关心一个问题：给定一个初始状态，先手玩家是否有必胜策略？

其实啊，我们如果倒着来推的话：

对于一个终局状态：

根据规则，我们就可以钦定面对此状态的人的胜负，在Nim博弈中，终局状态（即所有石子都被对面取光）是负态，我们可以把终态视为一种特殊的负态；

对于一个非终局状态：

如果我们能留给对手的所有可能状态都是胜态，那么该状态为负态；

如果我们能留给对手的所有可能状态中存在负态，那么该状态为胜态。

所以，此游戏中的任何一个可达到的状态，要么是胜态，要么是负态，前提是：

双人、回合制；
信息完全公开；
无随机因素；
必然在有限步内结束；
没有平局。

这就是策梅洛定理(Zermelo's theorem)。

由此亦可知，经过一步行动，负态只能变成胜态，胜态可以（但不一定）变成负态。

同时，根据这样的性质，我们就可以利用记忆化搜索来暴力解决某些博弈论问题，比如这道：【Trie、博弈论】CF455B A Lot of Games，或是打表找出规律。

三、状态的组合

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,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
(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
(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)

我们只需证明

SG(A)xorSG(B)\notin (\lbrace SG(A)xorSG(C)|B\rightarrow C\rbrace\bigcup \lbrace SG(D)xorSG(B)|A\rightarrow D\rbrace)
\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]);
}