Nim 游戏

Nim游戏是组合游戏(Combinatorial Games)的一种,准确来说,属于“Impartial Combinatorial Games”(以下简称ICG)。满足以下条件的游戏是ICG(可能不太严谨):1、有两名选手;2、两名选手交替对游戏进行移动(move),每次一步,选手可以在(一般而言)有限的合法移动集合中任选一种进行移动;3、对于游戏的任何一种可能的局面,合法的移动集合只取决于这个局面本身,不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素; 4、如果轮到某名选手移动,且这个局面的合法的移动集合为空(也就是说此时无法进行移动),则这名选手负。根据这个定义,很多日常的游戏并非ICG。例如象棋就不满足条件3,因为红方只能移动红子,黑方只能移动黑子,合法的移动集合取决于轮到哪名选手操作。

经典Nim游戏

通常的Nim游戏的定义是这样的:有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗(不能不拿)”,如果轮到某个人时所有的石子堆都已经被拿空了,则判负(因为他此刻没有任何合法的移动)。 我们定义Position: P:表示当前局面下先手必败 N:表示当前局面下先手必胜 结论:(Bouton’s Theorem): 对于一个Nim游戏的局面(a1,a2,…,an),它是P-position(后手必胜)当且仅当 a1^a2^…^an=0,其中^表示异或(xor)运算。 可以利用二进制来证明,详细证明过程:https://blog.csdn.net/Summer\_\_show\_/article/details/70185470 如果Nim游戏中的规则稍微变动一下,每次最多只能取K个,怎么处理? Ans:将每堆石子数mod (k+1).

Nim的各种变形

Moore’s Nimk

n堆石子,每次从不超过k堆中取任意多个石子,最后不能取的人失败。

这是一个nim游戏的变形,也是有结论的。 结论为:把n堆石子的石子数用二进制表示,统计每个二进制位上1的个数,若每一位上1的个数mod(k+1)全部为0,则必败,否则必胜。

anti-nim(反Nim游戏)

正常的nim游戏是取走最后一颗的人获胜,而反nim游戏是取走最后一颗的人输。

一个状态为必胜态,当且仅当: 1)所有堆的石子个数为1,且NIM_sum=0 2)至少有一堆的石子个数大于1,且 NIM_sum≠0 例子:Bzoj1022 : https://www.lydsy.com/JudgeOnline/problem.php?id=1022

#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
    int t,i,j,k,n;
    cin>>t;
    while(t--){
        cin>>n;
        bool onlyone=true;
        int sum=0;
        while(n--){
            scanf("%d",&j);
            if(j!=1)onlyone=false;
            sum^=j;
        }
        if((onlyone&&!sum)||(!onlyone&&sum)){
            puts("John");
        }
        else puts("Brother");
    }

    return 0;
}

威佐夫博弈

两堆石子,每次可以从一堆或两堆中取任意数目的石子,从两堆中取得时候,从不同堆取的石子个数必须相同,先取完的获胜。

这种情况下是颇为复杂的。我们用(ak,bk)(ak ≤ bk ,k=0,1,2,…,n)表示两堆物品的数量并称其为局势,如果甲面对(0,0),那么甲已经输了,这种局势我们 称为奇异局势。前几个奇异局势是:(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)。 奇异局势的3条性质: 1.任何自然数都包含在一个且仅有一个奇异局势中。 2.任意操作都可将奇异局势变为非奇异局势。 3.采用适当的方法,可以将非奇异局势变为奇异局势。 假设面对的局势是(a,b): 1.若 b = a,则同时从两堆中取走 a 个物体,就变为了奇异局势(0,0); 2.如果a = ak ,b > bk,那么,取走b – bk个物体,即变为奇异局势; 3.如果 a = ak , b < bk ,则同时从两堆中拿走 ak – ab – ak个物体,变为奇异局 势( ab – ak , ab – ak+ b – ak); 4.如果a > ak ,b= ak + k,则从第一堆中拿走多余的数量a – ak 即可; 5.如果a < ak ,b= ak + k,分两种情况,第一种,a=aj (j < k),从第二堆里面拿走 b – bj 即可;第二种,a=bj (j < k),从第二堆里面拿走 b – aj 即可。 从如上性质可知,两个人如果都采用正确操作,那么面对非奇异局势,先拿者必胜 ;反之,(面对奇异局势)则后拿者取胜。 任给一个局势(a,b),判断它是不是奇异局势(先手负): $a_k =[k\times \frac{(1+√5)}{2}], b_k= a_k + k $ (k=0,1,2,…,n ,方括号表示向下取整函数) 其中k由bk-ak求得,如果两个数不符合这样的形式,则不是奇异局势 注意一定要满足a<=b,不满足时对调a,b 例子:http://poj.org/problem?id=1067

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    double t=(1+sqrt(5.0))/2;//系数
    int a,b,k;
    while(cin>>a>>b){
        if(a>b)swap(a,b);
        k=b-a;
        if(a==(int)(k*t)){//计算a是否符合该形式
            cout<<0<<endl;
        }
        else cout<<1<<endl;
    }

    return 0;
}

巴什博奕

只有一堆石子共n个。每次从最少取1个,最多取m个,最后取光的人取胜。

如果$n=(m+1)* k+s (s!=0)$ 那么先手一定必胜,因为第一次取走s个,接下来无论对手怎么取,我们都能保证取到所有(m+1)倍数的点,那么循环下去一定能取到最后一个。(也就是说只要n不是m+1的倍数先手必胜)

staircase nim

顾名思义就是在阶梯上进行,每层有若干个石子,每次可以选择任意层的任意个石子>将其移动到该层的下一层。最后不能操作的人输。

(这个博弈的解释不是特别明白QAQ) 阶梯博弈经过转换可以变为Nim,把所有奇数阶梯看成N堆石子做nim。把石子从奇数堆移动到偶数堆可以理解为拿走石子,就相当于几个奇数堆的石子在做Nim。 结论:所有奇数阶梯(奇数堆)的石子的Nim sum如果不为0,先手胜,否则后手胜 (以下仅供参考,没太看懂)

假设我们是先手,所给的阶梯石子状态的奇数堆做Nim先手能必胜.我就按照能赢的步骤将奇数堆的石子移动到偶数堆.如果对手也是移动奇数堆,我们继续移动奇数堆.如果对手将偶数堆的石子移动到了奇数堆..那么我们紧接着将对手所移动的这么多石子从那个奇数堆移动到下面的偶数堆.两次操作后.相当于偶数堆的石子向下移动了几个。而奇数堆依然是原来的样子,即为必胜的状态。就算后手一直在移动偶数堆的石子到奇数堆,我们就一直跟着他将石子继续往下移,保持奇数堆不变。我可以跟着后手把偶数堆的石子最终移动到0,然后对手就不能移动这些石子了.所以整个过程.将偶数堆移动到奇数堆不会影响奇数堆做Nim博弈的过程..整个过程可以抽象为奇数堆的Nim博弈. 为什么是只对奇数堆做Nim就可以而不是偶数堆呢?因为如果是对偶数堆做Nim,对手移动奇数堆的石子到偶数堆,我们跟着移动这些石子到下一个奇数堆。那么最后是对手把这些石子移动到了0,我们不能继续跟着移动,就只能去破坏原有的Nim而导致胜负关系的不确定。所以只要对奇数堆做Nim判断即可知道胜负情况。

例子:http://poj.org/problem?id=1704 ( POJ1704) (可参考挑战程序设计竞赛P312) 本题的做法与上面描述的又不完全一致。我们把棋子按位置升序排列后(没有保证一定按升序给出),从后往前把他们两两绑定成一对。如果总个数是奇数,就把最前面一个和边界(位置为0)绑定。 在同一对棋子中,如果对手移动前一个,你总能对后一个移动相同的步数,所以一对棋子的前一个和前一对棋子的后一个之间有多少个空位置对最终的结果是没有影响的。于是我们只需要考虑同一对的两个棋子之间有多少空位。 这样一来就成了N堆取石子游戏了.

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,k;
int s[1010];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
            scanf("%d",&s[i]);
        sort(s+1, s+n+1);
        int ans;
        if(n%2 == 0)
        {
            ans = s[2]-s[1]-1;
            for(int i=4; i<=n; i+=2) ans ^= (s[i]-s[i-1]-1);
            if(ans == 0) cout<<"Bob will win"<<endl;
            else cout<<"Georgia will win"<<endl;
        }
        else
        {
            ans = s[1]-1;
            for(int i=3; i<=n; i+=2) ans ^= (s[i]-s[i-1]-1);
            if(ans == 0) cout<<"Bob will win"<<endl;
            else cout<<"Georgia will win"<<endl;
        }
    }
    return 0;
}