精华内容
下载资源
问答
  • 什么SG?+SG模板

    2018-08-31 11:10:00
    并且若存在局面i和局面j,且j是i的后继局面(即局面i可以转化为局面j),我们用一条有向边,从i出发到j,连接表示局面i和局面j的点。则整个游戏可以表示成为一个有向无环图:根据ICG游戏的定义我们知道...

    先,定义一下 状态Position P 先手必败 N x先手必胜

    操作方法: 反向转移

     相同状态 不同位置 的一对 相当于无

    对于ICG游戏,我们可以将游戏中每一个可能发生的局面表示为一个点。并且若存在局面i和局面j,且j是i的后继局面(即局面i可以转化为局面j),我们用一条有向边,从i出发到j,连接表示局面i和局面j的点。则整个游戏可以表示成为一个有向无环图:

    根据ICG游戏的定义我们知道,任意一个无法继续进行下去的局面为终结局面,即P局面(先手必败)。在上图中我们可以标记所有出度为0的点为P点。接着根据ICG游戏的两条性质,我们可以逆推出所有点为P局面还是N局面:

    对于一个游戏可能发生的局面x,我们如下定义它的sg值:
    (1)若当前局面x为终结局面,则sg值为0。
    (2)若当前局面x非终结局面,其sg值为:sg(x) = mex{sg(y) | y是x的后继局面}。
    mex{a[i]}表示a中未出现的最小非负整数。举个例子来说:
    mex{0, 1, 2} = 3, mex{1, 2}=0, mex{0,1,3}=2

    我们将上图用sg函数表示后,得到:

    可以发现,若一个局面x为P局面,则有sg(x)=0;否则sg(x)>0。同样sg值也满足N、P之间的转换关系:
    若一个局面x,其sg(x)>0,则一定存在一个后续局面y,sg(y)=0。
    若一个局面x,其sg(x)=0,则x的所有后续局面y,sg(y)>0。

    由上面的推论,我们可以知道用N、P-Position可以描述的游戏用sg同样可以描述。并且在sg函数中还有一个非常好用的定理,叫做sg定理:
    对于多个单一游戏,X=x[1..n],每一次我们只能改变其中一个单一游戏的局面。则其总局面的sg值等于这些单一游戏的sg值异或和。

     

     

    先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

    对于一个给定的有向无环图,定义关于图的每个顶点的Sprague-Grundy函数g如下:g(x)=mex{ g(y) | y是x的后继 },这里的g(x)即sg[x]

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

    sg[0]=0,f[]={1,3,4},

    x=1时,可以取走1-f{1}个石子,剩余{0}个,mex{sg[0]}={0},故sg[1]=1;

    x=2时,可以取走2-f{1}个石子,剩余{1}个,mex{sg[1]}={1},故sg[2]=0;

    x=3时,可以取走3-f{1,3}个石子,剩余{2,0}个,mex{sg[2],sg[0]}={0,0},故sg[3]=1;

    x=4时,可以取走4-f{1,3,4}个石子,剩余{3,1,0}个,mex{sg[3],sg[1],sg[0]}={1,1,0},故sg[4]=2;

    x=5时,可以取走5-f{1,3,4}个石子,剩余{4,2,1}个,mex{sg[4],sg[2],sg[1]}={2,0,1},故sg[5]=3;

    以此类推.....

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

    sg[x]      0  1  0  1  2  3  2  0  1....

     

    计算从1-n范围内的SG值。

    f(存储可以走的步数,f[0]表示可以有多少种走法)

    f[]需要从小到大排序

    1.可选步数为1~m的连续整数,直接取模即可,SG(x) = x % (m+1);

    2.可选步数为任意步,SG(x) = x;

    3.可选步数为一系列不连续的数,用GetSG()计算

     

    //f[]:可以取走的石子个数
    //sg[]:0~n的SG函数值
    //hash[]:mex{}
    int f[N],sg[N],hash[N];     
    void getSG(int n)
    {
        int i,j;
        memset(sg,0,sizeof(sg));
        for(i=1;i<=n;i++)
        {
            memset(hash,0,sizeof(hash));
            for(j=1;f[j]<=i;j++)
                hash[sg[i-f[j]]]=1;
            for(j=0;j<=n;j++)    //求mes{}中未出现的最小的非负整数
            {
                if(hash[j]==0)
                {
                    sg[i]=j;
                    break;
                }
            }
        }
    }
    SG打表
    //注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍
    //n是集合s的大小 S[i]是定义的特殊取法规则的数组
    int s[110],sg[10010],n;
    int SG_dfs(int x)
    {
        int i;
        if(sg[x]!=-1)
            return sg[x];
        bool vis[110];
        memset(vis,0,sizeof(vis));
        for(i=0;i<n;i++)
        {
            if(x>=s[i])
            {
                SG_dfs(x-s[i]);
                vis[sg[x-s[i]]]=1;
            }
        }
        int e;
        for(i=0;;i++)
            if(!vis[i])
            {
                e=i;
                break;
            }
        return sg[x]=e;
    }
    dfs

     注意在SG表的初始化中,不用每次都初始;否则会T的,因为可以循环利用,这是一个强大的地方

    HDU1536 实战

    #include<stdio.h>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    int s[110],sg[10010],n;
    char op[200];
    int SG_dfs(int x)
    {
        int i;
        if(sg[x]!=-1)
            return sg[x];
        bool vis[110];
        memset(vis,0,sizeof(vis));
        for(i=0;i<n;i++)
        {
            if(x>=s[i])
            {
                SG_dfs(x-s[i]);
                vis[sg[x-s[i]]]=1;
            }
        }
        int e;
        for(i=0;;i++)
            if(!vis[i])
            {
                e=i;
                break;
            }
        return sg[x]=e;
    }
    int main()
    {
       int k;
        while(scanf("%d",&n)!=EOF)
        {
            if(n==0)
            break;
            for(int i=0 ; i<n ; i++)
            scanf("%d",&s[i]);
            sort(s,s+n);
            int m,cnt=0;
            scanf("%d",&m);
            memset(sg,-1,sizeof(sg));
            for(int i=0 ; i<m ; i++)
            {
    
                scanf("%d",&k);
                int x=0;
                while(k--)
                {
                    int w;
                    scanf("%d",&w);
                    x^=SG_dfs(w);
    
                }
                if(x!=0)
                printf("W");
                else
                printf("L");
            }
                 puts("");
        }
    
        return 0;
    }
    View Code

     

    转载于:https://www.cnblogs.com/shuaihui520/p/9564718.html

    展开全文
  • SG函数

    2019-07-12 20:18:00
    SG函数 对于游戏的每个子游戏,存在一种衡量局面优劣的函数SG函数,整个游戏的SG函数就是各个子游戏的异或和。 每个局面的SG函数为当前局面的后继状态的SG函数...3、如果后继状态全是必胜,那么SG函数为0,表示必...

    SG函数

    对于游戏的每个子游戏,存在一种衡量局面优劣的函数SG函数,整个游戏的SG函数就是各个子游戏的异或和。

    每个局面的SG函数为当前局面的后继状态的SG函数集合中最小的没有出现的非负整数,可以发现对于某一状态而言:

    1 、如果没有后继状态,SG函数为0,表示必败。

    2 、如果后继状态中存在必败状态,那么SG函数为正,表示必胜。

    3 、如果后继状态全是必胜,那么SG函数为0,表示必败。

    转载于:https://www.cnblogs.com/shxnb666/p/11178199.html

    展开全文
  • SG函数和SG定理

    2018-10-26 14:35:05
    SG定理: **游戏和的SG函数等于各个游戏SG函数的Nim和。...首先定义mex运算,这是施加于集合得运算,表示最小的不属于这个集合的非负整数,例如mex{0,1,2,4}=3、mex[2,3,5]=0. 对于任意状态x,定义SG(x)...

    SG定理:
    **游戏和的SG函数等于各个游戏SG函数的Nim和。**意思就是例如对Nim游戏,各个游戏的SG函数也就是每一堆石子的数量即SG(x)=x.那么游戏和的SG函数就是对各个游戏SG函数进行异或求得Nim和。

    SG函数:

    首先定义mex运算,这是施加于集合得运算,表示最小的不属于这个集合的非负整数,例如mex{0,1,2,4}=3、mex[2,3,5]=0.
    对于任意状态x,定义SG(x)=mex(S),其中S是x的后续状态的集合。例如x有三个后续状态分别为SG(a),SG(b),SG©,那么SG(x)=mex(SG(a),SG(b),SG©),对于SG(0)来说它没有后续状态那么它的值就是0.

    取石子问题:

    有1堆含n个石子,每次只能取[1,3,4]个石子,先取完石子者获胜,那么各个数的SG函数为多少?
    SG[0]=0, f[]={1,3,4};
    x=1时,可以取走1-f[1]个石子,剩余{0}个,所以SG[1]=mex{SG[0]}=mex{0}=1;
    x=2 时,可以取走2 - f{1}个石子,剩余{1}个,所以 SG[2] = mex{ SG[1] }= mex{1} = 0;
    x=3 时,可以取走3 - f{1,3}个石子,剩余{2,0}个,所以 SG[3] = mex{SG[2],SG[0]} = mex{0,0} =1;
    x=4 时,可以取走4- f{1,3,4}个石子,剩余{3,1,0}个,所以 SG[4] = mex{SG[3],SG[1],SG[0]} = mex{1,1,0} = 2;
    x=5 时,可以取走5 - f{1,3,4}个石子,剩余{4,2,1}个,所以SG[5] = mex{SG[4],SG[2],SG[1]} =mex{2,0,1} = 3;
    以此类推…

    由上述实例我们就可以得到SG函数值求解步骤,那么计算1~n的SG函数值步骤如下:
    1、使用 数组f 将 可改变当前状态 的方式记录下来。
    2、然后我们使用 另一个数组 将当前状态x 的后继状态标记。
    3、最后模拟mex运算,也就是我们在标记值中 搜索 未被标记值 的最小值,将其赋值给SG(x)。
    4、我们不断的重复 2 - 3 的步骤,就完成了 计算1~n 的函数值。

    //f[N]当中记录的是可改变当前状态的方式
    //SG[N]记录0~n的SG函数值
    //S[]记录的是x的后继状态
    int f[N],SG[MAXS],S[MAXS];
    void getSG(int n){
    	memset(SG,0,sizeof(SG));
    	//因为i=0的时候SG[0]=0,所以从1开始
    	for(int i=1;i<=n;i++){
    	//每次都要将上一状态的后继集合重置
    	    memset(S,0,sizeof(S));
    	    for(int j=0;f[j]<=i&&j<N;j++){
    		S[SG[i-f[j]]]=1;//将后继状态进行标记
    	    }
    	    for(int j=0;j<MAXS;j++){
    		if(!S[j]){
    			SG[i]=j;
    			break;
    	        }
    	    }
    	}
    }
    

    对于SG函数的理解:
    首先,一个点的子状态可能有多个,然后每个子状态又会有自己的子状态。当一个状态的子状态可以判断必胜还是必败的时候,子状态返回自己的SG值,然后用一个vis数组存下来,然后当当前状态的所有子状态都返回了自己的SG值,那么vis从0开始,第一个没有被标记过的自然数就是当前状态的SG值。
    当一个值被vis数组记录过,说明当前状态可以转换成对应sg值的状态,那么,如果0被标记了,那么说明当前状态可以转换成必败态,那么当前状态一定是非0的,也就是必胜态。mex函数也就是寻找第一个不能转换到的状态,那么,只需要关注0和非0即可。意思是,当你通过vis数组找到的当前点的SG值为0则说明,当前点没有没有办法转换的必败态,那么当前点就是必败态,所有SG函数的值为0,反之,就是当前点可以一步到达必败态,那么此时就是必胜态。
    当所有点的SG的值都推出来的时候,答案一般就是所求点的SG值得异或,异或为0先手必败,反之先手必胜。

    展开全文
  • 06SG429_后张预应力混凝土结构施工图表示方法与构造详图,建筑规范、施工设计图纸、方案、范本/考试资料、建筑图集等资料。本文档内容比较详细,字迹比较清晰,如果你需要一份这样的资料作为工作学习参考工具。赶紧...
  • 博弈论 SG函数 SG定理

    2018-11-30 22:15:37
    本来这篇博客叫《博弈论入门》,但写完后发现好像没东西了…… ...没有出度的点的SG值为0,其它点的SG值为它的后继的SG值的mex。即SG(u)=mex{SG(v)},u→vSG(u)=mex{SG(v)},u→v。  在SG值为0的点上,先手必败,而在...

    本来这篇博客叫《博弈论入门》,但写完后发现好像没东西了……

    SG函数

    一个公平游戏(impartial game)可以抽象为:在一个DAG上有一枚棋子,两人轮流移动它,不能移动者输。 
    SG函数的定义如下。没有出度的点的SG值为0,其它点的SG值为它的后继的SG值的mex。即SG(u)=mex{SG(v)},u→vSG(u)=mex{SG(v)},u→v。 
    在SG值为0的点上,先手必败,而在其它点上先手必胜。

    数据规模较大时,一般来说,可以通过打表找到SG函数的通项。 
    其它时候可以递推求。求mex用Trie树上的跳法。

    SG定理

    在多个DAG上进行上述游戏操作,每次可以移动一个DAG上的棋子。设当前状态为每个DAG上棋子所在位置的集合{p1,p2,...}{p1,p2,...},则SG({p1,p2,...})=SG(p1)⊕SG(p2)⊕...SG({p1,p2,...})=SG(p1)⊕SG(p2)⊕...。

    Tartan定理

    描述组合游戏在多个维度上的合并。

    Nim和在01状态且决策互相影响游戏上的特殊性

    给定一个棋盘,每个格子有黑白两个状态。每次操作只能针对黑色格子,会对某些格子取反。由于Nim和的性质,可以证明一个格子的SG值是它所影响的格子的游戏的合并。即无需考虑是否会统计到白色格子。 
    如:SG(i)←mexeachtransferencekind{XOR{SG(eachstatekinder)}}SG(i)←mexeachtransferencekind{XOR{SG(eachstatekinder)}}

    无向图删边游戏

    给定一个无向图,有一中心点,两人轮流操作,每次可切断一条中心点所在联通块内的一条边,先不能操作者输。 
    Fusion Principle定理说明:在无向图删边游戏中,将一个环上的所有边变为环上的一个点上的相同数量的自环后,图的SG值不变。 
    这里写图片描述 
    picture from Game Theory, Qin Yue, Tsinghua Univ. 
    缩点后做树形删边游戏即可。

    SJ定理

    反公平游戏(Anti-SG Game)描述为:DAG上没有出度的点为胜利状态,其它定义与一般游戏相同。现在的问题是解决多个反公平游戏的合并。 
    SJ定理说明:先手必胜,当且仅当以下两个条件同时成立或同时不成立: 
    1.合并的SG值为0; 
    2.所有游戏的SG值不超过1。

    其它经典模型

    有向图公平游戏

    在有向图上进行经典游戏。

    先算出可计算的SG函数,最后不能计算的点是平局点。

    欧几里得的游戏

    给定a、ba、b,每次对一个数删去另一个数的若干倍,有一个数为0时失败。

    若a≥2ba≥2b,则先手必胜。否则递归处理。

    擦数游戏

    有数1~n,每次选一个数划去它的所有约数,没有数则失败。

    先手必胜。

    階梯博弈

    以0为地面,1~n为逐渐升高的台阶,每个台阶上有若干石子。每人每次将一个台阶上的若干石子移到比它低的台阶。

    当且仅当所有奇数台阶上的式子异或和不为0时,先手必胜。 
    阶梯博弈推广 “每个格子有黑白两种状态,每次选择某白色格子可确定的格子翻转,不能操作者输”与这个游戏等价:每个格子有黑白两种状态,每次选择某格子可确定的格子翻转,将所有格子都变为黑色的人赢。

    无向点地理问题(Undirected vertex geography problem)

    在一个无向二分图上进行轮流移动棋子游戏,不能经过重复的点。

    广义地理(generalized geography)是一个典型的完全P空间(PSPACE-Complete)问题。 
    当且仅当棋子在所有最大匹配上时,先手必胜。 
    from LOJ536

    练习题

    Lasker的游戏

    有n堆石子,每次可以选一堆石子中取出一些石子或分成两堆石子。没有石子则失败。

    SG(i)表示i个石子的SG值,打表发现SG函数形如1,2,4,3,5,6,8,7,9,10,12,11,……。按SG定理合并即可。

    本来这篇博客叫《博弈论入门》,但写完后发现好像没东西了……

    SG函数

    一个公平游戏(impartial game)可以抽象为:在一个DAG上有一枚棋子,两人轮流移动它,不能移动者输。 
    SG函数的定义如下。没有出度的点的SG值为0,其它点的SG值为它的后继的SG值的mex。即SG(u)=mex{SG(v)},u→vSG(u)=mex{SG(v)},u→v。 
    在SG值为0的点上,先手必败,而在其它点上先手必胜。

    数据规模较大时,一般来说,可以通过打表找到SG函数的通项。 
    其它时候可以递推求。求mex用Trie树上的跳法。

    SG定理

    在多个DAG上进行上述游戏操作,每次可以移动一个DAG上的棋子。设当前状态为每个DAG上棋子所在位置的集合{p1,p2,...}{p1,p2,...},则SG({p1,p2,...})=SG(p1)⊕SG(p2)⊕...SG({p1,p2,...})=SG(p1)⊕SG(p2)⊕...。

    Tartan定理

    描述组合游戏在多个维度上的合并。

    Nim和在01状态且决策互相影响游戏上的特殊性

    给定一个棋盘,每个格子有黑白两个状态。每次操作只能针对黑色格子,会对某些格子取反。由于Nim和的性质,可以证明一个格子的SG值是它所影响的格子的游戏的合并。即无需考虑是否会统计到白色格子。 
    如:SG(i)←mexeachtransferencekind{XOR{SG(eachstatekinder)}}SG(i)←mexeachtransferencekind{XOR{SG(eachstatekinder)}}

    无向图删边游戏

    给定一个无向图,有一中心点,两人轮流操作,每次可切断一条中心点所在联通块内的一条边,先不能操作者输。 
    Fusion Principle定理说明:在无向图删边游戏中,将一个环上的所有边变为环上的一个点上的相同数量的自环后,图的SG值不变。 
    这里写图片描述 
    picture from Game Theory, Qin Yue, Tsinghua Univ. 
    缩点后做树形删边游戏即可。

    SJ定理

    反公平游戏(Anti-SG Game)描述为:DAG上没有出度的点为胜利状态,其它定义与一般游戏相同。现在的问题是解决多个反公平游戏的合并。 
    SJ定理说明:先手必胜,当且仅当以下两个条件同时成立或同时不成立: 
    1.合并的SG值为0; 
    2.所有游戏的SG值不超过1。

    其它经典模型

    有向图公平游戏

    在有向图上进行经典游戏。

    先算出可计算的SG函数,最后不能计算的点是平局点。

    欧几里得的游戏

    给定a、ba、b,每次对一个数删去另一个数的若干倍,有一个数为0时失败。

    若a≥2ba≥2b,则先手必胜。否则递归处理。

    擦数游戏

    有数1~n,每次选一个数划去它的所有约数,没有数则失败。

    先手必胜。

    階梯博弈

    以0为地面,1~n为逐渐升高的台阶,每个台阶上有若干石子。每人每次将一个台阶上的若干石子移到比它低的台阶。

    当且仅当所有奇数台阶上的式子异或和不为0时,先手必胜。 
    阶梯博弈推广 “每个格子有黑白两种状态,每次选择某白色格子可确定的格子翻转,不能操作者输”与这个游戏等价:每个格子有黑白两种状态,每次选择某格子可确定的格子翻转,将所有格子都变为黑色的人赢。

    无向点地理问题(Undirected vertex geography problem)

    在一个无向二分图上进行轮流移动棋子游戏,不能经过重复的点。

    广义地理(generalized geography)是一个典型的完全P空间(PSPACE-Complete)问题。 
    当且仅当棋子在所有最大匹配上时,先手必胜。 
    from LOJ536

    练习题

    Lasker的游戏

    有n堆石子,每次可以选一堆石子中取出一些石子或分成两堆石子。没有石子则失败。

    SG(i)表示i个石子的SG值,打表发现SG函数形如1,2,4,3,5,6,8,7,9,10,12,11,……。按SG定理合并即可。

    展开全文
  • 组合游戏 - SG函数和SG定理

    万次阅读 多人点赞 2015-05-07 08:09:04
    组合游戏的和通常是很复杂的,所以我们介绍一种新工具,可以使组合问题变得简单————SG函数和SG定理。 Sprague-Grundy定理(SG定理):  游戏和的SG函数等于各个游戏SG函数的Nim和。这样就可以将每一个子游戏...
  • sg函数

    2016-09-01 19:14:06
    //f[]:可以取走的石子个数 ...//sg[]:0~n的SG函数值 //hash[]:mex{} int f[N],sg[N],hash[N]; void getSG(int n) { int i,j; memset(sg,0,sizeof(sg)); for(i=1;i;i++) { memset(hash,0,s
  • sg函数模板

    2018-08-15 10:35:49
     首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。  对于任意状态 x , 定义 SG(x) = mex(S),其中 S 是 x ...
  • sg函数和sg定理

    2018-04-28 21:31:12
    在介绍SG函数和SG定理之前我们先介绍介绍必胜点与必败点吧.必胜点和必败点的概念: P点:必败点,换而言之,就是谁处于此位置,则在双方操作正确的情况下必败。 N点:必胜点,处于此情况下,双方操作均正确的情况...
  • SG模板

    2018-03-15 10:52:32
    首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如 mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。 对于一个给定的有向无环图,定义关于图的每个顶点的...
  • SG定理

    千次阅读 2015-09-13 18:52:20
    SG定理 相信很多人都已经知道了这个定理。 假设现在有一个有向无环的游戏图G(V,E)G(V,E),若(i,j)∈E(i,j) \in E则表示状态ii可以转移到状态jj. 我们还要定义必胜态与必败态的概念。 必胜态表示,从当前状态可以
  • 博弈 - SG函数和SG定理

    2017-03-30 20:42:44
    在介绍SG函数和SG定理之前我们先介绍介绍必胜点与必败点吧. 必胜点和必败点的概念:  P点:必败点,换而言之,就是谁处于此位置,则在双方操作正确的情况下必败。  N点:必胜点,处于此情况下,双方操作均正确...
  • 文章目录前置芝士SG函数意义mex运算SG函数的求法举个栗子SG定理证明 前置芝士 Nim游戏 如果不明白 NimNimNim 游戏是啥的...这是一个施加于集合的运算,表示求出这个集合中最小的没有出现过的非负整数,比如 mex{0,2,...
  • 再谈SG函数和SG定理

    千次阅读 2017-08-28 15:18:33
    今天考了一道博弈论的题,让我重新复习一下SG定理吧。 首先通常的Nim游戏的定义是这样的:有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗(不能不拿)”,如果轮到某个人时所有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,978
精华内容 7,591
关键字:

sg表示什么