几种基础的博弈

巴什博奕

巴什博奕：

两个顶尖聪明的人在玩游戏，有n

巴什博奕是博弈论问题中基础的问题

它是最简单的一种情形对应一种状态的博弈

首先我们明显可以知道当石子剩下m+1个的时候，先手必胜

我们把n写成这种形式： n = (m+1)*k + r

每个人都是最聪明的他们都想让自己拿的时候是 (m+1)*k 的这种形势因为这样他们是必胜的

所以我们只要判断 n%(m+1) == 0?first:second

1 #include<cstdio>
2 int main()
3 {
4     int n,m;
5     scanf("%d%d",&n,&m);
6     if(n % (m+1) !=0) printf("first win");
7     else printf("second win");
8     return  0;
9 }

斐波那契博奕

斐波那契博弈

斐波那契博弈是一种经典的博弈问题

有一堆石子，两个顶尖聪明的人玩游戏，先取者可以取走任意多个，但不能全取完，以后每人取的石子数不能超过上个人的两倍

先直接上结论吧：

先手必败，当且仅当石子数为斐波那契数

证明的话可以看这个博客：https://www.cnblogs.com/henry-1202/p/9744678.html

 1 #include<cstdio>
 2 #include<map>
 3 int fib[233],x;
 4 std::map<int,bool>mp;
 5 int main()
 6 {
 7     fib[1]=1;fib[2]=1;
 8     for(int i=3;i<=50;i++) fib[i]=fib[i-1]+fib[i-2],mp[fib[i]]=1;
 9     while(scanf("%d",&x)&&x!=0)
10         puts(mp[x]==1?"Second win":"First win");
11     return 0;
12 }

威佐夫博弈

威佐夫博弈是一类经典的博弈问题

有两堆石子，两个顶尖聪明的人在玩游戏，每次每个人可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子，不能取得人输，分析谁会获得胜利

这里就直接给出结论：

证明的博客：

https://www.cnblogs.com/zwfymqz/p/8469863.html

 1 #include<cstdio>
 2 #include<cmath> 
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int main(){
 7     int a,b;
 8     while(~scanf("%d%d",&a,&b)){
 9         if(a>b) swap(a,b);
10         int k=b-a;
11         int tmp=(int)(k*(sqrt(5)+1)/2.0);
12         if(tmp==a)
13             puts("0");
14         else
15             puts("1");
16     } 
17 }

这里插一个比较经典的题目可以更加加深对威佐夫博弈的理解

HDU 2177 取(2堆)石子游戏

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

题目大意：游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。如果先手胜，那先手第1次该怎样取子，如果在任意的一堆中取走石子能胜同时在两堆中同时取走相同数量的石子也能胜，先输出取走相同数量的石子的情况。

解题思路：对应上面的第二类威佐夫问题。当先手会赢时，假设（a,b）&&a<b，分两种情况讨论：

　　　　　①两堆取相同数量石子，因为同时取，所以k=b-a的值时不变的，ak是固定的，只要a>ak，那就可以有一种取石子的方案。

　　　　　②在其中一堆取任意数量的石子，可以知道差值k在0~b之间，我们通过枚举差值计算ak会有以下几种情况是符合的：

　　　　　　　　　1）a=ak，b>ak+k，取b堆里的石子，可使b=ak+k

　　　　　　　　　2）a=ak+k，取b堆里的石子，可使b=ak

　　　　　　　　　3）b=ak+k，a>ak，取a堆里的石子，可使a=ak

　　　　　　　　　4）b=ak，a>ak+k，这是不可能的，a>ak+k=b+k>a自相矛盾

　　　　　所以枚举时满足以上三种情况的，即为解决方案。

 1 #include<cstdio>
 2 #include<cmath> 
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int main(){
 7     int a,b;
 8     while(~scanf("%d%d",&a,&b)&&(a||b)){
 9         if(a>b) swap(a,b);
10         int k=b-a;
11         int tmp=(int)(k*(sqrt(5)+1)/2.0);
12         if(tmp==a)
13             puts("0");
14         else{
15             puts("1");
16             //两堆同时取，k不变，判断ak是否小于a 
17             if(a>tmp){
18                 printf("%d %d\n",tmp,b-(a-tmp));
19             }
20             //取一堆，枚举0~b所有的差值 
21             for(int i=0;i<=b;i++){
22                 int tmp2=(int)(i*(sqrt(5)+1)/2.0);
23                 //防止重复,例如7 10取两堆或一堆都会有4 7 
24                 if(tmp2==tmp)
25                     continue;
26                 if(tmp2==a&&b>tmp2+i||tmp2+i==a||tmp2+i==b&&a>tmp2){
27                     printf("%d %d\n",tmp2,tmp2+i);
28                 }        
29             }    
30         } 
31     }
32     return 0; 
33 }

尼姆博弈

尼姆博弈模型，大致上是这样的：

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

分析

1、首先自己想一下，就会发现只要最后剩两堆物品一样多(不为零)，第三堆为零，那面对这种局势的一方就必败

那我们用(a,b,c)表示某种局势，首先(0,0,0)显然是必败态，无论谁面对(0,0,0) ，都必然失败；第二种必败态是(0,n,n)，自己在某一堆拿走k（k ≤ n）个物品，不论k为多少，对方只要在另一堆拿走k个物品，最后自己都将面临(0,0,0)的局势，必败。仔细分析一下，(1,2,3)也是必败态，无论自己如何拿，接下来对手都可以把局势变为(0,n,n)的情形

那这种奇异局势有什么特点呢？

也不知谁这么牛逼，竟然能把这种局势和二进制联系在一起

这里说一种运算符号， 异或'^',a^b=a'b+ab'（a'为非a）

我们用符号XOR表示这种运算，这种运算和一般加法不同的一点是1 XOR 1 = 0。先看(1,2,3)的按位模2加的结果：

1 = 二进制01

2 = 二进制10

3 = 二进制11 XOR

———————

0 = 二进制00 (注意不进位)

对于奇异局势(0,n,n)也一样，结果也是0

任何奇异局势(a,b,c)都有a XOR b XOR c = 0

如果我们面对的是一个非必败态(a,b,c)，要如何变为必败态呢？

假设 a < b < c，我们只要将 c 变为a XOR b，即可。因为有如下的运算结果：

a XOR b XOR (a XOR b)=(a XOR a) XOR (b XOR b) = 0 XOR 0 = 0

要将c 变为a XOR b，只要对 c进行 c-(a XOR b)这样的运算即可

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn = 1e5+5;
 8 
 9 int arr[maxn];
10 
11 int main()
12 {
13     int n,ans,cnt;
14     while (~scanf("%d",&n) && n)
15     {
16         ans = cnt = 0;
17         for (int i=0;i<n;i++)
18         {
19             scanf("%d",&arr[i]);
20             ans^=arr[i];
21         }
22         if (ans == 0)
23             puts("0");
24         else
25         {
26             for (int i=0;i<n;i++)
27             {
28                 int k = ans^arr[i];  // k是arr[i]和除arr[i]之外的异或
29                 if (arr[i]>k)  // 想满足奇异局势的话就让arr[i] = k
30                 {
31                     cnt++;
32                 }
33                 
34             }
35             printf("%d\n",cnt);
36         }
37     }
38     return 0;
39 }

SG函数和SG定理

必胜点和必败点的性质：

1、所有终结点是必败点 P 。（我们以此为基本前提进行推理，换句话说，我们以此为假设）

2、从任何必胜点N 操作，至少有一种方式可以进入必败点 P。

3、无论如何操作，必败点P 都只能进入必胜点 N。

首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如

mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Grundy函数g如下：g(x)=mex{ g(y) | y是x的后继},这里的g（x）即

sg[x]。

例如：取石子问题，有1堆n个的石子，每次只能取{1，3,4}个石子，先取完石子者胜利，那么各个数的SG值为多少？

sg[0]=0，f[]={1,3,4},

x=1时，可以取走1-f{1}个石子，剩余{0}个，mex{sg[0]}={0}，故sg[1]=1;

x=2时，可以取走2-f{1}个石子，剩余{1}个，mex{sg[1]}={1}，故sg[2]=0；

x=3时，可以取走3-f{1,3}个石子，剩余{2,0}个，mex{sg[2],sg[0]}={0,0}，故sg[3]=1;

x=4时，可以取走4-f{1,3,4}个石子，剩余{3,1,0}个，mex{sg[3],sg[1],sg[0]}={1,1,0},故sg[4]=2;

x=5时，可以取走5-f{1,3,4}个石子，剩余{4,2,1}个，mex{sg[4],sg[2],sg[1]}={2,0,1},故sg[5]=3；

以此类推.....

x 0 1 2 3 4 5 6 7 8....

sg[x] 0 1 0 1 2 3 2 0 1....

计算从1-n范围内的SG值。

f(存储可以走的步数，f[0]表示可以有多少种走法)

f[]需要从小到大排序

1.可选步数为1~m的连续整数，直接取模即可，SG(x) = x % (m+1);

2.可选步数为任意步，SG(x) = x;

3.可选步数为一系列不连续的数，用getSG()计算

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn = 1e5+5;
 8 
 9 int sg[maxn],vis[maxn];
10 int arr[maxn];
11 
12 void SG(int n) //求SG函数
13 {
14     memset(sg,0, sizeof(sg));
15     memset(vis,0, sizeof(vis));
16     int temp = 1;
17     for (int i=1;i<=n;i++,temp++)
18     {
19         for (int j=0; j<=10 && arr[j]<=i;j++)
20             vis[sg[i-arr[j]]] = temp;
21         for (int j=0;j<=n;j++)
22         {
23             if (vis[j]!=temp)
24             {
25                 sg[i] = j;
26                 break;
27             }
28         }
29     }
30 }
31 
32 int main()
33 {
34     int n;
35     arr[0] = 1;
36     for (int i=1;i<=10;i++)
37         arr[i] = arr[i-1]*2;
38     while (~scanf("%d",&n))
39     {
40         SG(n);
41         if (sg[n])
42             puts("Kiki");
43         else
44             puts("Cici");
45     }
46     return 0;
47 }

解决组合博弈我就直接上结论了