博弈SG

三种经典的博弈问题

  • 巴什博弈:只有一堆n个石子,A 和 B 轮流取,每次取1~m个,最后取完者胜
  • 威佐夫博弈:有两堆石子,A 和 B 轮流取,每次可以从某一堆取任意个(至少一个),或同时从两堆中取同样多个,最后取光(两堆同时光)者胜。
  • 尼姆博弈:有多堆石子,A 和 B 轮流取,每次从某一堆取任意个(至少一个),最后取光者胜

巴什博奕引入

有3个石头,A 和 B 玩取石子游戏,A 先手、轮流取,可以取1~2个(不能不取),那么 A 必败(取走1或2个,B 都可以一次取完)。
假如有6个石头,A 必败,取走1或2个,B都可以一次取剩三个。
以此类推,凡是石头数为3的倍数的情况,先手 A 必败,我们称之为“平衡状态”,即 A 每打破平衡后 B 都可以马上把石头数恢复“平衡状态”,直至最后 B 取完石头。

那么假如石头个数不是3的倍数呢?A 可以取走1或2个把石头数变成“平衡状态”,让 B 打破“平衡状态”,A 最后取胜。

重点:$Nim$ 博弈

关键在于找到“平衡状态”,这其实和二进制有关。举个例子:

  • 现有5堆石子,石子数依次为 67,5,7,19,112

1 0 0 0 0 1 1 ---第1堆(67)
0 0 0 0 1 0 1 ---第2堆(5)
0 0 0 0 1 1 1 ---第3堆(7)
0 0 1 0 0 1 1 ---第4堆(19)
1 1 1 0 0 0 0 ---第5堆(112)
$---------------$
2 1 2 0 2 3 4 --- 代表每位有多少个1

我们发现,当某个位上1的数量为偶数个时,对方拿走一个该位上的1后我们可以再拿走该位上的一个1,那么该位上1的数量仍为偶数个,当所有位上1的数量都为偶数时,无论对方怎么拿我们总可以把每个位上1的数量恢复为偶数,也就是说最后拿完石头(恢复到偶数0)的一定是我们。即“所有位上1的数量都为偶数”就是“平衡状态”。
假如我们先手面对的就是“平衡状态”,必败;假如我们先手面对的不是“平衡状态”,我们该如何把情况转化为“平衡状态”呢?看这个例子,找到1的数量为奇数的最高位(即例子中的次高位),随便找到一堆该位为1的石头(例子中的第5堆),把这个1拿掉(拿走32个石头)就可以让这个位上的1的个数变成偶数(1变0);再看看有没有1的数量为奇数的较低位(例子中的次低位),对应到刚刚拿石头的第5堆是个0,那我们把0变成1(还回去2个石头)就可以让这个位上的1的个数变成偶数(3变4),至此成功把情况转变为平衡状态。

我们根据“所有位上1的数量都为偶数为平衡状态“可以快速判断平衡状态——把每堆石头个数取异或和,异或和为0则处于平衡状态(偶数个1异或和为0哦),从而快速判断先手胜负。

例题 1

【题意】
古代的Nim取石子游戏是由两个人面对若干堆石子进行的游戏。
设有n>=1堆石子,各堆分别含有a[1]、a[2]……a[n]个石子。
游戏的目的就是选取最后剩下的石子。游戏规则如下:

  • 1:游戏人交替进行游戏
  • 2:当轮到每个游戏人取子时,选择这些石子中的一堆,并从所选的堆中取走至少一个石子(游戏人也可以取走他所选择的堆中的全部石子,于是留下一个空堆)

当所有的堆都变成空堆时,游戏结束,最后取子(即能够取走最后一堆中剩下的所有石子)的游戏人,视为游戏的胜利者。
现在,对于给定n,与这n堆石子的具体数目,需要你判断先手是否必胜。
(假设游戏人足够聪明,采用的一定是最优策略)

【输入格式】
多组测试数据,每组测试数据的第一行为一个正整数n (0<n<=10000)。
下来的一行共有n个正整数a[i] (0<i<=n,0<a[i]<=2^30)。

【输出格式】
对于每组测试数据,若先手必败,则输出First Lose,
若先手必胜则输出First Win,并且输出在游戏第一轮,
先手可能采取的所有策略x y:表示先手从第x堆石子中取走y个石子。
每种策略占一行,按字典序依次输出。

【样例输入】

4  
7 9 12 15  
2  
6 6

【样例输出】

First Win
2 5
3 11
4 13
First Lose

【解法】
思路如上文,实现即可。

#include<cstdio>
#include<cstring>
#define N 10010
using namespace std;
inline int read()
{
    int x=0;bool f=false;
    char ch=getchar();
    while(ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return f?-x:x;
}
int a[N],s[40];
//a记录每堆石头个数,s记录每个二进制位1的个数
bool f[N][40];
//f[i][j]记录第i堆石头数量的第j个二进制位是否为1
int main()
{
    int n,x,ans;
    while(~scanf("%d",&n))
    {
        memset(s,0,sizeof(s));
        memset(f,false,sizeof(f));
        ans=0;
        for(int i=1;i<=n;i++)
        {
            a[i]=read();x=a[i];
            ans^=a[i];
            for(int j=30;j>=0;j--) if(f[i][j]=(x>=(1<<j))) s[j]++,x-=(1<<j);//判断二进制位是否为1
        }
        if(!ans) {puts("First Lose");continue;}
        puts("First Win");
        for(int i=30;i>=0;i--) if(s[i]&1) {ans=i;break;}
        for(int i=1;i<=n;i++) if(f[i][ans])
        {
            int sum=1<<ans;
            for(int j=ans-1;j>=0;j--) if(s[j]&1) sum+=(f[i][j]?1:-1)*(1<<j);
            printf("%d %d\n",i,sum);
        }
    }
    return 0;
}

评论

暂无评论