SG函数 - Blog

参考博客：http://blog.csdn.net/luomingjun12315/article/details/45555495

对于某一类游戏（博弈），我们可以把游戏中的各个状态看作点，状态之间的转移看作有向边，构成一个有向无环图，把博弈的过程看成是两个人拿一个棋子轮流在图上面走，如果轮到某一方时走不动就算输。这可以看做ICG（公平组合游戏，Impartial Combinatorial Games）的一种抽象模型。

必胜点与必败点

P-position：先手必败的状态。

N-position：先手必胜。

性质

1.所有终结点是必败点P。

2.从任何必胜点N操作，至少有一种方式可以进入必败点P。

3.无论如何操作，必败点P都只能进入必胜点N（后续有必败态的当前一定是必胜态）。

（1.无法继续走的点是P-position；

2.有出边指向P-position的点是N-position；

3.任何出边都指向N-position的点是P-position。）

分析必胜点和必败点都是以终结点进行逆序分析

以hdu 1847 Good Luck in CET-4 Everybody!为例：

总共n张牌，每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…），抓完牌，胜负结果也出来了，最后抓完牌的人为胜者。

当n=0时，为必败点。

当n=1时，为必胜点。

当n=2时，为必胜点。

当n=3时，要么就是剩一张要么剩两张，无论怎么取对方都将面对必胜点，故这一点为必败点。

以此类推，最后你就可以得到；

n ： 0 1 2 3 4 5 6 …

position： P N N P N N P …

使用了P/N来分析，使问题变简单了。

Sprague-Grundy定理（SG定理）

一个有向无环图上的一个点i的SG函数g(i)定义如下：

如果该点没有出边，g(i)=0，否则定义一个mex操作，返回值为集合中所不包含的最小的非负整数，那么g(i)=mex{g(x)|i有出边指向x}。

游戏和的SG函数等于各个游戏SG函数的Nim和（异或和）。

性质

设g(i)=k，这就表示从点i可以走到一个SG函数值等于0,1,2,…,k−1的点。

SG值为0就是必败，SG大于0就是必胜。

举例

有1堆n个的石子，每次只能取{1,3,4}个石子，先取完石子者胜利，那么各个数的SG值为多少？

SG[0]=0，f[]={1,3,4}，

当x=1时，后继状态为0，所以SG[1]=mex{SG[0]}=mex{0}=1；

当x=2时，后继状态为1，所以SG[2]=mex{SG[1]}=0;

当x=3时，后继状态为0和2，所以SG[3]=mex{SG[0],SG[2]}=1;

当x=4时，后继状态为0和1和3，所以SG[4]=mex{SG[0],SG[1],SG[3]}=2;

当x=5时，后继状态为1和2和4，所以SG[5]=mex{SG[1],SG[2],SG[4]}=3。

以此类推，

x 0 1 2 3 4 5 6 7 8….

SG[x] 0 1 0 1 2 3 2 0 1….

模板

打表（首选）

以HDU1848为例：

题意：给出m,n,p三堆石子，每次可以取斐波那契数个，给出m,n,q，判断先手赢还是后手赢。

代码：

int f[20];//可改变当前状态的方式
int sg[1010];//0~n的SG函数值
bool s[1010];//mex{}
void init()
{
    f[1]=1;f[2]=2;
    for(int i=3;i<=15;i++)
    {
        if(f[i-2]+f[i-1]>1000)break;
        f[i]=f[i-2]+f[i-1];
    }
}
void getsg(int n)
{
    memset(sg,0,sizeof(sg));
    for(int i=1;i<=n;i++)
    {
        memset(s,0,sizeof(s));
        for(int j=1;f[j]<=i&&j<=15;j++)
            s[sg[i-f[j]]]=true;
        for(int j=0;j<=n;j++)
        {
            if(!s[j])
            {
                sg[i]=j;
                break;
            }
        }
    }
}
int main()
{
    int m,n,p;
    init();
    getsg(1000);
    while(scanf("%d%d%d",&m,&n,&p)!=EOF)
    {
        if(m==0&&n==0&&p==0)break;
        if(sg[m]^sg[n]^sg[p])printf("Fibo\n");
        else printf("Nacci\n");
    }
    return 0;
}

DFS

以POJ2425为例：

题意：给出一张图，有m个棋子，每个人可以任意移动一个棋子，最后不能移动的人为输，问先手赢还是输。

代码：

vector<int>v[1010];
int sg[1010];
int getsg(int x)
{
    if(sg[x]!=-1)return sg[x];
    bool vis[1010];  //vis应该是局部变量，因为下面进行递归调用的时候会打乱vis
    memset(vis,0,sizeof(vis));
    for(int i=0;i<v[x].size();i++)
        vis[getsg(v[x][i])]=true;
    int i=0;
    while(vis[i])
        i++;
    return sg[x]=i;
}
int main()
{
    int n,m,x;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
            v[i].clear();
        memset(sg,-1,sizeof(sg));
        for(int i=0;i<n;i++)
        {
            scanf("%d",&m);
            while(m--)
            {
                scanf("%d",&x);
                v[i].push_back(x);
            }
        }
        while(scanf("%d",&m)!=EOF)
        {
            if(m==0)break;
            int ans=0;
            while(m--)
            {
                scanf("%d",&x);
                ans^=getsg(x);
                /*for(int i=0;i<n;i++)
                    printf("%d ",sg[i]);
                printf("\n");*/
            }
            //printf("%d\n",ans);
            if(ans==0)printf("LOSE\n");
            else printf("WIN\n");
        }
    }
    return 0;
}