Nim && Grundy (基础博弈游戏）

通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

结论：（不给证明，可去搜证明）

对于一个Nim游戏的局面(a1,a2,...,an)，它是必败态当且仅当a1^a2^...^an=0，其中^表示异或(xor)运算。怎么样，是不是很神奇？我看到它的时候也觉得很神奇，完全没有道理的和异或运算扯上了关系。但这个定理的证明却也不复杂，基本上就是按照两种position的证明来的。

int N,A[maxn]

void solve( )

{

    int x = ;

    for(int i= ; i<N ; i++)

    x^=A[i];

    if(x!=)

    puts("A");

    else

    puts("B");

    return ;

}

现在来实战分析Nim

poj 1704

题意】

从左到右有一排石子，给出石子所在的位置。规定每个石子只能向左移动，且不能跨过前面的石子。最左边的石子最多只能移动到1位置。每次选择一个石子按规则向左移动，问先手是否能赢。

分析：如果我们将棋子两两看成一对，之间的距离表示Nim里面小石头堆的数量，那这就是个Nim.那这里就有个疑问了，那奇数的时候怎么办了呐？很简单拿第一个棋子的距离与 1 当成是一个堆其他的不变就好了，那问题又来了，为什么，可以这样转换呢？这个道理很简单我棋子向左移动，是不是距离就减少了，那不就是相当于拿走石头吗，等等！聪明仔可能发现了问题了，一个棋子左移动，那肯定是有一堆的石头的数量增加了呀，这不符合Nim呀！想想也是，不过如果我们将其看做是对手不讲道义，破坏规则，进行加石头。那我们只要将对手增加石头的部分减回去，不就是原来的状态了吗。神奇不，注意需要排序，超坑

#include<stdio.h>

#include<algorithm>

using namespace std;

const int maxn =  ;

int n,p[maxn],val[maxn];

int main( )

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

    scanf("%d",&n);

    for(int i= ; i<=n ; i++)

    scanf("%d",&p[i]) ;

    sort(p+,p++n);

    int cnt=;

    if(n%==)

    {

        for(int i= ; i<=n ; i+=)

        {

            val[cnt++]=p[i]-p[i-]-;

        }

    }

    else

    {

        val[cnt++]=p[]-;

        for(int i= ; i<=n ; i+=)

        {

            val[cnt++]=p[i]-p[i-]-;

        }

    }

    int x=;

    for(int i= ; i<cnt ; i++)

    {

        x^=val[i];

        //printf("%d ",val[i]);

    }

     if(x!=)

        puts("Georgia will win");

     else

        puts("Bob will win");

    }

     return ;

}

题目：

A 和 B 在玩游戏，给k个数字a1 , a2 , ... , ak ; 一开始有n堆硬币，每一堆有 xi 枚。 A 和 B 轮流选出一堆硬币，从中取出硬币，每次所取硬币的枚数一定在a1 , a2 , a3 ,...., ak ; 里面，A先取，取光硬币的一方获胜。

分析：这里引入一个概念 Grundy , 利用这个东西，很多游戏都可以转换为Nim>

只有一堆石头的情况

int grundy(int x){

    集合S={}；

    for(j=:k){

        if(a_j<=x) 将grundy(x-a_j)加到S集合中

    }

    return 最小的不属于S的非负整数

}

rundy值：除（任意一步所能转移到的状态的Grundy值）以外的最小非负整数，这样的Grundy值，和Nim中的一个石子堆类似，有如下性质：

mex{0，1，2}=3；mex{ 1, 2}=0 ; mex{ 2, 3}=1

1.Nim中有x颗石子的石子堆，能转移成有0，1，……，x-1堆石子的石子堆

2.从Grundy值为x的状态出发，可以转移到Grundy值为0，1，……，x-1的状态。

Nim：

所有石子堆的石子数xi的XOR

x1 XOR x2 XOR …XOR xk

为0必败，为1必胜

Grundy值等价于Nim中石子数，所以对于Grundy的情况：

所有硬币堆的Grundy的值

grundy(x1) XOR grundy(x2) XOR …… XOR grundy(xn)

为0必败，为1必胜。

#include <cstdio>

#include <set>

#include <algorithm>

#define maxn 105

#define maxk 105

using namespace std;

int N,K,X[maxn],A[maxk];

int grundy[maxn+];

void solve(){

    //轮到自己剩0的时候必败

    grundy[]=;            

    //计算grundy

    int max_x=*max_element(X,X+N);//找最大值

    for(int j=;j<=max_x;j++){

        set<int> s;                //存储当前的状态

        for(int i=;i<K;i++){

            if(A[i]<=j) s.insert(grundy[j-A[i]]);

        }

        int g=;                //寻找当前状态的最小排斥

        while(s.count(g)!=) g++;

        grundy[j]=g;

    }

    int ans=;

    for(int i=;i<N;i++) ans^grundy[X[i]];

    if(ans!=)    puts("Alice");

    else puts("Bob");

}

int main(){

    scanf("%d%d",&N,&K);

    for(int i=;i<N;i++){

        scanf("%d",&A[i]);

    }

    for(int j=;j<K;j++){

        scanf("%d",&X[j]);

    }

    solve();

    return ;

}

poj2311

题意:给定一张n*m的矩形纸片,定义一个决策为:从所有的纸片中任选一张(初始时仅有1张),沿平行于矩形边剪切,将原矩形分割为2个较小的矩形,双方轮流决策,先剪出1*1纸片者获胜,问先手是否必胜.

经典的组合游戏问题,首先一张纸片经过一次裁剪变为两张,即一个游戏变为两个子游戏,那么子游戏和的sg值=子游戏A的sg值异或子游戏B的sg值,即sg[A∪B] = sg[A] xor sg[B].

很容易想出将(1,1)作为终止条件.但是考虑组合游戏本质为在一张有向图中从S到T双方轮流移动,但此题中只要出现一张(1,1)游戏便结束,以(1,1)作为终止条件可能会产生有向图并没有走完但游戏已经结束的情况.

稍加分析可知,某一方某一次决策之后产生了一张(1,k)的纸片,那么这一方必败(因为另一方将(1,k)裁剪为(1,1)&(1,k-1)可以直接获胜),那么对于(i,j)的纸片,最优决策一定会避免剪出(1,k)的纸片,当纸片无论怎么剪都会出现(1,k),称这张纸片为"不可剪",当某纸片不可剪时,则会选择其他纸片进行裁剪,易证,存在某一个状态,所有的纸片都是"不可剪".

不可剪状态的纸片有:(2,2), (2,3), (3,2), (3,3).

那么只需要将这些纸片作为终止条件问题就解决了.

#include<stdio.h>

#include<set>

#include<string.h>

using namespace std ;

int mem[][];

int grundy(int w , int h)

{

    if(mem[w][h] != -)

    return mem[w][h] ;

    set<int> s;

    for(int i= ; w-i>= ; i++)

    s.insert(grundy(i,h)^grundy(w-i,h));

    for(int i= ; h-i>= ; i++)

    s.insert(grundy(w,i)^grundy(w,h-i));

    int res = ;

    while(s.count(res))

    res++;

    return mem[w][h]=res ;

}

int main( )

{

    int w,h;

    memset(mem,-,sizeof(mem));

    while(scanf("%d%d",&w,&h)!=EOF)

    {

        if(grundy(w,h) != )

        puts("WIN");

        else

        puts("LOSE");

    }

}

<span style="font-size:18px;">#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

#define rep(i, l, r) for (int i = l; i <= r; i++)

#define REP(i, l, r) for (int i = l; i >= r; i--)

#define MAXN 1010

int n, m, sg[MAXN][MAXN];

bool xx[MAXN];

inline int mex() {int i; for (i = ; xx[i]; ++i); return i;}

inline int getsg(int n, int m) {

    if (~sg[n][m]) return sg[n][m];

    memset(xx, , sizeof(xx));

    rep(i, , n-) xx[getsg(i, m) ^ getsg(n-i, m)] = ;

    rep(i, , m-) xx[getsg(n, i) ^ getsg(n, m-i)] = ;

    return sg[n][m] = mex();

}

int main() {

    memset(sg, -, sizeof(sg));

    sg[][] = sg[][] = sg[][] = sg[][] = sg[][] = ;

    while (scanf("%d%d", &n, &m) != EOF)

    cout << (getsg(n, m) ? "WIN" : "LOSE") << endl;

    return ;

}

</span>

深度了解问题

巴特西

Nim && Grundy (基础博弈游戏）

最新文章

热门文章

巴特西

Nim && Grundy (基础博弈游戏 ）

最新文章

热门文章

Nim && Grundy (基础博弈游戏）