Nim博弈与SG函数入门

阅读量：266 次

发布时间：2019-03-01

本文共 4473 字，大约阅读时间需要 14 分钟。

文章摘自

希望这篇题解能都帮到初学者。 Nim游戏

从一个问题进入。

描述

今天我们要认识一对新朋友，Alice与Bob。 Alice与Bob总是在进行各种各样的比试，今天他们在玩一个取石子的游戏。在这个游戏中，Alice和Bob放置了N堆不同的石子，编号1..N，第i堆中有Ai个石子。每一次行动，Alice和Bob可以选择从一堆石子中取出任意数量的石子。至少取1颗，至多取出这一堆剩下的所有石子。 Alice和Bob轮流行动，取走最后一个石子的人获得胜利。假设每一轮游戏都是Alice先行动，请你判断在给定的情况下，如果双方都足够聪明，谁会获得胜利？

讨论

这是一个古老而又经典的博弈问题：Nim游戏。

Nim游戏是经典的公平组合游戏(ICG)，对于ICG游戏我们有如下定义：

两名选手

两名选手轮流行动，每一次行动可以在有限合法操作集合中选择一个

游戏的任何一种可能的局面(position)，合法操作集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它因素；局面的改变称为“移动”(move)

如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负

对于第三条，我们有更进一步的定义Position，我们将Position分为两类：

P-position：在当前的局面下，先手必败

N-position：在当前的局面下，先手必胜

它们有如下性质：

合法操作集合为空的局面是P-position

可以移动到P-position的局面是N-position

所有移动都只能到N-position的局面是P-position

算法实现 取子游戏算法实现——

步骤1:将所有终结位置标记为必败点（P点）；步骤2: 将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点）步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点），则将该点标记为必败点（P点）；步骤4: 如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。

在这个游戏中，我们已经知道A[] = {0,0,…,0}的局面是P局面，那么我们可以通过反向枚举来推导出所有的可能局面，总共的状态数量为A1∗A2∗...∗AN。并且每一次的状态转移很多。虽然耗时巨大，但确实是一个可行方法。

当然，我们这里会讲这个题目就说明肯定没那么复杂。没错，对于这个游戏有一个非常神奇的结论：

对于一个局面，当且仅当A1 xor A2 xor ... xor AN =0时，该局面为P局面。

如何证明这个结论呢？

这里写图片描述

SG函数

同样从一个问题进入。

描述

给定一个有向无环图和一个起始顶点上的一枚棋子，Alice和Bob交替的将这枚棋子沿有向边进行移动，无法移动者判负。问是否有必胜策略。

讨论

事实上，这个游戏可以认为是所有ICG游戏的抽象模型。也就是说，任何一个ICG游戏都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。下面我们就在有向无环图的顶点上定义SG(Sprague-Garundy)函数。

Sprague-Grundy Theorem

这里写图片描述

SG函数的建立

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

对于一个给定的有向无环图，定义关于图的每个顶点的SG函数sg如下：sg(x)=mex{ sg(y) | y是x的后继 }。也就是说，一个点的SG函数为在它所有后继中都未出现的最小的值。

SG函数的性质

来看一下SG函数的性质。首先，所有的没有出边的顶点，其SG值为0，因为它的后继集合是空集。然后对于一个sg(x)=0的顶点x，它的所有后继y都满足 sg(y)≠ 0。对于一个sg(x)≠ 0的顶点，必定存在一个后继y满足sg(y)=0。

这个时候你就应该有所发现了！SG函数的性质和N,P局面的性质非常相似！以上表明，顶点x所代表的postion是P-position当且仅当sg(x)=0（跟P-positioin/N-position的定义是完全对应的）。

后手必胜当且仅当sg的异或和为0

解题模型

举个栗子

例如：取石子问题，有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.把原游戏分解成多个独立的子游戏，则原游戏的SG函数值是它的所有子游戏的SG函数值的异或。

即sg(G)=sg(G1)^sg(G2)^...^sg(Gn)。

2.分别考虑没一个子游戏，计算其SG值。

SG值的计算方法：（重点）
1. 可选步数为1~m的连续整数，直接取模即可，SG(x) = x % (m+1);
2. 可选步数为任意步，SG(x) = x;
3. 可选步数为一系列不连续的数，用模板计算。

关于SG(x) = x % (m+1);和SG(x) = x; 这里写图片描述

模板两种方法我觉得都是搜索

方法一：打表 f[]可以取走的石子个数,注意f[]需要从小到大排序 sg[]SG函数值；vis[]标记数组，用于求mex{}

//f[N]:可改变当前状态的方式，N为方式的种类，f[N]要在getSG之前先预处理//SG[]:0~n的SG函数值//S[]:为x后继状态的集合int f[N],SG[MAXN],S[MAXN];void  getSG(int n){    int i,j;    memset(SG,0,sizeof(SG));    //因为SG[0]始终等于0，所以i从1开始    for(i = 1; i <= n; i++){        //每一次都要将上一状态 的 后继集合 重置        memset(S,0,sizeof(S));        for(j = 0; f[j] <= i && j <= N; j++)            S[SG[i-f[j]]] = 1;  //将后继状态的SG函数值进行标记        for(j = 0;; j++) if(!S[j]){   //查询当前后继状态SG值中最小的非零值            SG[i] = j;            break;        }    }}

方法二：dfs s数组是定义特殊取法规则的数组，注意要按照从小到大排序；n表示集合大小 SG函数要初始化为-1，每个集合只需初始化一遍

int s[MAXN],sg[MAXN],n;bool vis[MAXN];int SG_dfs(int x){    if (sh[x]!=-1)        return sg[x];    memset(vis,0,sizeof(vis));    for (int i=0; i
   
    =s[i])        {            SG_dfs(x-s[i]);            vis[sg[x-s[i]]]=1;        }    }    int i=0;    while (1)    {        if (!vis[i])            return sg[x]=i;        i++;    }}

拓展

SG函数与Nim游戏的联系？ 　　如果对于一个游戏，它是ICG。那么我们可以发现，对于此游戏的一种局面，ICG上的多个sg函数的值，如果看做多个石堆的话，就相当于一个nim游戏！我们来一步步推导：

首先来个引理，s≥sg(x)s≥sg(x)，这个用归纳法证，应该说简单。

如果当前局面，所有sg函数的值都是零，先手必输。分类讨论一下。如果当前局面上的所有棋子都不能走了，显然它们的sg函数值都是零，那么先手必输。如果还有棋子能走，我们可以选一个棋子走一步，那么这个棋子的sg函数值就会变成非零。非零说明什么，说明当前棋子所在结点的孩子结点一定有一个sg函数值为零，那对手只要将棋走到那个结点就行了。然后局面就又变成了原来的。

前面那个其实相当于nim游戏的终止局面。那普通局面就相当于有sg函数的值不为零。还是分类讨论。如果现在对手走，sg值异或和为零（注意是异或和），他会选一个石子，然后把这个石子放到它的孩子结点上。sg值有可能增加，也有可能减少。只要sg值增加，你就把它还原回来（根据sg函数的定义，好好思考一下！），那么sg函数总有不能增加的一天，因为第一条的引理。这就相当于sg值只能减少！那这不是一个nim游戏吗？根据nim游戏里面的证明，你一定可以找到一个数，找一个石子堆，减去这个数以后，异或和还是零。最终对手就会被逼迫到第二条的局面上，然后它就输了。反之如果异或和不为零，你一定输！

通过这个sg函数，我们就可以把所有ICG游戏转换成nim游戏！