博弈论-蒲公英云

巴什博奕

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2149

有n个物品，有两个参与者A,B ，每人每次从中取[1,m]个 ,假设每人都取最优策略, 求谁最后取完物品假设A先取

如果n=m+1，显然不管第一次A取多少个，都没办法取完，而剩下的物品B可以一次性取完，所以结果一定是B赢

因此，我们可以发现一个先取者的必胜策略，即对于n=(m+1)*k+s; 我们令A先取s个，那么对于B无论他取多少个，A都可以取一个数，使得A取的物品数+上次B取的物品数=m+1 这样就出现不管B取多少个，到最后总能剩下m+1 所以B一定会输；

int n,m;
int k=n%(m+1);
if(k==0) cout<<"B Win"<<endl;
else cout<<"A Win"<<endl;

斐波那契博弈

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2516

有n个物品，有两个参与者A,B ，每人每次从中取[1,上一个人取物品数的2倍]个 ,假设每人都取最优策略, 求谁最后取完物品假设A先取

应用了斐波那契数列，“Zeckendorf定理”（齐肯多夫定理）：任何正整数可以表示为若干个不连续的Fibonacci数之和。

总结就是一句话：对于n 若是斐波那契数则A赢；否则B赢

sg函数参考链接：https://blog.csdn.net/yizhangbiao/article/details/51992022

一共有n个物品总结 sg[]==0 为必输策略

1 每次取1~m个 sg[x]=n%(m+1);

2 每次取任意个 sg[x]=x;

3每次取一系列不连续中数任意一个 mex(x);

威佐夫博奕（Wythoff Game）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1527

有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

关键在于判断是不是奇异局势

是先手输否先手赢

判断条件 a==|b-a|*((sqrt(5)+1)/2)

那什么叫奇异局势呢？

对于（ak,bk）（ak ≤ bk ,k=0，1，2，…,n) ak 是前面没有出现过的最小的自然数，bk=ak+k;

如：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）

性质1.任何自然数都包含在一个且仅有一个奇异局势中。由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 。所以性质1。成立。 2.任意操作都可将奇异局势变为非奇异局势。

尼姆博奕（Nimm Game）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1850

有m堆各若干个物品，两个人A,B轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

同威佐夫博弈一样也是需要判断奇异局势是先手输否先手赢

判断条件

int ans=0,a[1005];
for(int i=1;i<=m;i++)
  {
     cin>>a[i];
     ans^=a[i]; 
   } 
if(ans==0) cout<<"B Win"<<endl;
else cout<<"A Win"<<endl;

如何将非奇异局势变为奇异局势也就是说 A要赢第一次应怎么取呢？

原理：m=3 时对于（55，81，121），55（+）81=102，121-102=19，所以从121中拿走19个物品就形成了奇异局势（55，81，102）

else{
       int cnt=0;
            for(int i=1;i<=m;i++){
                int k=ans^a[i];
                if(k<a[i]) cnt++;
            } 
            cout<<cnt<<endl;
           }

sg函数的应用

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1847

#include<iostream>
#include<cstring> 
using namespace std;
int n,arr[15],sg[1005];
int mex(int x){
    if(sg[x]!=-1) return sg[x]; //如果sg[x]不为-1  直接输出 
    bool vis[1005];
    for(int i=0;i<1005;i++) 
      vis[i]=false;//初始化标志位 
    for(int i=0;i<=10;i++) {
        int temp=x-arr[i];
        if(temp<0) break;
        sg[temp]=mex(temp);//相当于dfs
        vis[sg[temp]]=true;//该值出现过  标记
    }
    for(int i=0;;i++){
        if(!vis[i]) {
            sg[x]=i;break;//当前sg[]集合中未出现的最小的自然数
        }
    }
    return sg[x];
} 
int main(){
    arr[0]=1;
    for(int i=1;i<=10;i++)
      arr[i]=arr[i-1]*2;//数组arr[]初始化  即每步可选择的牌数 
    while(cin>>n){
        memset(sg,-1,sizeof(sg));//初始化 因为sg函数要求的是大于等于0 所以初始化为-1
        if(mex(n))  cout<<"Kiki"<<endl;//mex 函数是关键 
        else cout<<"Cici"<<endl; 
    } 
    return 0;
}

组合博弈

有n堆石子，每次可以从第1堆石子里取1颗、2颗或3颗，可以从第2堆石子里取奇数颗，可以从第3堆及以后石子里取任意颗……

我们可以把它看作3个子游戏，第1个子游戏只有一堆石子，每次可以取1、2、3颗，很容易看出x颗石子的局面的SG值是x%4。第2个子游戏也是只有一堆石子，每次可以取奇数颗，经过简单的画图可以知道这个游戏有x颗石子时的SG值是x%2。第3个游戏有n-2堆石子，就是一个Nim游戏。对于原游戏的每个局面，把三个子游戏的SG值异或一下就得到了整个游戏的SG值，然后就可以根据这个SG值判断是否有必胜策略以及做出决策了。其实看作3个子游戏还是保守了些，干脆看作n个子游戏，其中第1、2个子游戏如上所述，第3个及以后的子游戏都是“1堆石子，每次取几颗都可以”，称为“任取石子游戏”，这个超简单的游戏有x颗石子的SG值显然就是x。最后的sg值显然就是三个sg值的异或和