Nim游戏

/ 算法 / 没有评论 / 86浏览

游戏规则

给定n堆石子,每堆有\(a_i\)个石子。两个人轮流从其中的某一堆中取走任意个石子,不能不取。取走最后的石子的人获胜。
例如,有3堆石子分别有1,1,2个石子,先手可以先取走第三堆的两个石子,然后无论后手取走哪一堆石子,先手取走剩下的石子即获胜。

必胜策略

\(a_1 \oplus a_2 \oplus ... \oplus a_n=0(\oplus\)为异或),则后手胜,反之则先手胜。

简单证明

必败态一定转化为必胜态

从任意某堆石子中取走任意个石子,则从异或为0的状态变为异或不为0的状态,即必败态一定转化为必胜态。

必胜态能转化为必败态

必胜态异或值不为0,则异或值一定有一位为最高位的1。二进制表示对应位也为1的某堆石子中取走n个石子,使得异或值变为0。
下面解释n一定存在:由于要把异或值最高位的1也要变为0,因此取走的石子的二进制数为最高位的1一定低于异或值中最高位的1的位置。因此n一定小于被取的这堆石子的数目,n一定存在。 即必胜态能转化为必败态。

先后手策略

具体策略:
第一种情况:如果一开始异或值为非0,这时候只要先手取走适当的石子使得异或值为0。然后无论后手取任意石子,异或值都会变成非0,然后先手能取适当的石子使得异或值为0。因此这时候所有异或值为0的状态都是先手取得的,而获胜状态也是一种异或值为0的状态,因此先手必胜。

第二种情况:如果一开始异或值为0,则无论先手取任何石子,异或值都变为非0,此时后手取走适当的石子即可使得异或值为0。这种情况就可以看做交换了先后手的第一种情况,因此后手必胜。

Nim游戏扩展

Staircase Nim(阶梯博弈)

题目链接(POJ1704).在排成直线的格子上放有n个棋子,第i个棋子放在从左数第ai个格子上。Georgia和Bob可以轮流选择一个棋子向左移动若干格,但是不能反超其它的棋子,也不能跟其它棋子同一个格子。
无法移动的一方失败。给定n,以及这n个棋子的位置。假设Georgia先走,当双方采取最有策略时,谁会获胜?

  这道题就是Nim游戏的变形。假设棋子有偶数个,那么我们就可以把相邻的两个棋子分为一对,一共n/2对,这n/2对就可以看做n/2堆石子。每对棋子的距离就可以看做是每堆石子的数量,把每对棋子的右边的棋子向左边的棋子移动的步数就可以看做是从这堆石子中拿走的石子数。

  如果移动左边的棋子,相当于把石子数增加了,但是注意到移动左边的棋子一定是必败方,因为必胜方只需要移动右边的棋子就能保持必胜所以无需移动左边的棋子。而如果必败方移动了左边的棋子,必胜方只需要移动对应右边的棋子相同步数,这时候又回到了原来的状态,即必胜方还是必胜态。所有移动左边的棋子不会影响最后的结果。

  而如果棋子有奇数个,只需要把第一个棋子与最左边的边界看成一对棋子,剩下的仍然看成两两一对即可。
  这样我们就能利用Nim游戏的判定条件判断这个阶梯博弈的必胜方了。

参考代码:

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
    int T;cin>>T;
    while(T-->0){

        int n;cin>>n;

        int p[n+1];p[0]=0;
        for(int i=0;i<n;i++){
            cin>>p[i+1];
        }
        sort(p, p+n+1);

        int res = 0;
        for(int i=1+n%2;i<n;i+=2){
            res ^= (p[i+1]-p[i]-1);
        }
        if(n%2){
            res ^= (p[1]-p[0]-1);
        }

        if(res)
            puts("Georgia will win");
        else
            puts("Bob will win");
    }
    return 0;
}

Grundy数

在Nim游戏以及阶梯博弈中,我们都可以拿走任意不超过总数的石子。但是如果我们约定只能拿走规定数量的石子数时怎么办呢?例如只能拿走{1,3,4}中某个数量的石子数。这时候就可以用到Grundy数。

当前状态的Grundy值就是除任意一步能转移到的状态的Grundy值的最小非负整数。

注意到Grundy值跟Nim游戏中的一个石子堆有类似的性质:

而判定胜负条件也跟Nim游戏类似,把所有堆石子的Grundy值求异或然后跟0比较即可:

题目链接(POJ-2311)。准备一张分成w×h的格子的长方形纸张,两人轮流切割纸张。要沿着格子的边界切割,水平或者垂直把纸张切成两部分。切割n次之后得到n+1张纸,每次选择切得的某一张纸继续切割。率先切出(1×1)的纸张的一方获胜。当双方采取最有策略时,给定w和h,哪方会获胜?

  这道题就可以利用Grundy数解决。当把一张纸分为两张时,假设分得的两张纸的Grundy值分别为G1、G2,则这张纸对应的状态的Grundy值为G1^G2。我们枚举这张纸的所有可分为两张纸的情况,就可以然后把所有的能转移状态的求出,然后找到一个最小的不能转移的状态就是这张纸最终的Grundy值。

  由于这里只有一张纸,因此我们判断这张纸的Grundy值是否非0即可判断获胜方。

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <set>
    #include <algorithm>
    #define MAXN 202
    using namespace std;

    int mem[MAXN][MAXN];//记忆化搜索用的数组  
    int grundy(int w,int h)
    {
        if(mem[w][h]!=-1) return mem[w][h]; 
        set<int>s;
        // 保证边长至少为2,否则下面切的人会直接获胜
        // 遍历所有可能切的情况
        for(int i=2; w-i>=2; ++i) 
            s.insert(grundy(i,h)^grundy(w-i,h));
        for(int i=2; h-i>=2; ++i)  
            s.insert(grundy(w,i)^grundy(w,h-i));
        int res=0;
        while(s.count(res))
            ++res;
        return mem[w][h]=res;
    }
    int main()
    {
        int w,h;
        memset(mem,-1,sizeof(mem)); 
        while(~scanf("%d%d",&w,&h)) 
        {
            if(grundy(w,h)) puts("WIN");
            else puts("LOSE");
        }
        return 0;
    }