组合博弈问题（巴什博弈，威佐夫博弈，尼姆博弈）

文章目录

• 组合博弈
• 一、巴什博弈
• • 1.引例——取石子
  • 2.分析
  • 3.提高题
• 二、威佐夫博弈
• • 1.引例——取石子
  • 2.分析
  • 3.推广
• 二、尼姆博弈
• • 1.引例——Matches Game
  • 2.分析
  • 3.异或和处理的正确性证明
  • • 1.终止状态下，满足异或和为0的平衡态
    • 2.由非平衡态存在一种方式可以变为平衡态（先手必胜分析）
    • 3.由平衡态只能变为非平衡态（先手必败分析）
    • 4.小结
  • 4.例题——如何在非平衡态下进行第一次选择使得变为平衡态

组合博弈

两名玩家交替行动，均采取最优操作，但有一方不能继续操作时判定为输。

具体的游戏形式是取石子，两个玩家轮流对石子堆进行操作，直至有玩家无法继续操作时游戏结束。

一、巴什博弈

1.引例——取石子

经典取石子

在这道题里面，总共有n颗石头，每次至少取一颗，最多取m颗，在双方均采取最优解的情况下，问先手胜负情况

2.分析

思路一（直接判断）：

先手必输：

只要石子个数为（m+1）的倍数，先手无法在一次操作内取尽，若先手拿了k颗石子（1<=K<=m），而对方却可以拿（m+1-k）枚石子，将石子个数重新构造为（m+1）的倍数，故此时先手必输。

先手必胜：

当石子总数为（m+1）*r+s，先手拿了s颗石子后，剩余（m+1)*r颗石子，而此时也轮到了后手操作，根据上方的结论，可知此时后手必输，即先手必胜。

思路二（递推）：

必胜状态：

先手进行操作后，石子数将发生变化，根据操作的不同，石子数的变化也不同，若变化后的石子数有一种可能对于后手来说为必败，那么此时可视为必胜状态；

必败状态：

此时已经无法操作，或者经过操作后只有必胜状态，那么此时即为必败状态；

由此，我们通过已知推未知，可以对每个状态都进行判断，直至得出结果，对于这道题来说其实还是有点浪费的。

//思路一————直接判断
#include<bits/stdc++.h> 
using namespace std; 
int t;
int m,n;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        int s=n%(m+1);
        if(s==0)cout<<"second"<<endl;
        else cout<<"first"<<endl;
    }
}
           

//思路二————递推
#include<bits/stdc++.h> 
using namespace std; 
int t;
int m,n;
int a[1005];
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
       for(int i=1;i<=m;i++)a[i]=1;
       for(int i=m+1;i<=n;i++){
    	int ans=1;
       	for(int j=1;j<=m;j++){
       		ans=(ans&&a[i-j]);
		   }
		a[i]=!ans;
	   }
	   if(a[n])cout<<"first"<<endl;
	   else cout<<"second"<<endl;
    }
}
           

3.提高题

Public Sale

注意空格，注意题目要求还要输出必胜时第一次出价

#include<bits/stdc++.h> 
using namespace std; 
int m,n;
int main(){
    while(cin>>m>>n){
        if(n>=m){
            for(int i=m;i<=n;i++){
                cout<<i;
                (i<n)?cout<<" ":cout<<endl;
            }
        }
        else if(m%(n+1)==0)cout<<"none"<<endl;
        else{
            cout<<(m%(n+1))<<endl;
        }
    }
}
           

Good Luck in CET-4 Everybody!

//思路一
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	while(cin>>n) {
		if(n%3==0)
			cout<<"Cici"<<endl;
		else
    		cout<<"Kiki"<<endl;
 	}
 	return 0;
}
           

//思路二————递推
#include<bits/stdc++.h> 
using namespace std; 
int a[1025];
int n;
int main(){
    for(int i=0;i<=10;i++){
        a[(int)(pow(2,i))]=1;//必胜状态 
    }
    for(int i=1;i<=1000;i++){
        if(!a[i]){
            int ans=1;
            for(int j=0;pow(2,j)<i;j++){
                ans=(ans&&a[i-(int)(pow(2,j))]);
            }
            a[i]=!ans;
        }
    }
    while(cin>>n&&n){
        if(a[n])cout<<"Kiki"<<endl;
        else cout<<"Cici"<<endl;
    }
}
           

二、威佐夫博弈

1.引例——取石子

取石子

这道题中，仍然是两方交替操作，不过此时的区别为：

1.初始有两堆石子；

2.两种操作，要么选择一堆从中取任意颗石子，或者从两堆中取出相同石子个数的石子，要求石子个数要大于等于1，不设上限；

2.分析

先手必输：

若为（0，0），此时先手无法操作，为输；

若为（1，2），先手有四种操作：

左侧取一枚石子，后手可取完右侧，先手输；

右侧取一枚石子，后手可两堆各取一个，先手输；

右侧取两枚石子，后手可取完左侧，先手输；

两侧各取一枚石子，后手可取完右侧，先手输；

故此时先手必输。

通过模拟，可以发现先手必输的情况为：

（0，0）

（1，2）

（3，5）

（4，7）

（6，10）

（8，13）

（9，15）·········

我们将先手必输的情况叫做奇异局势，而且在其中有一个规律，以（a，b）为例，

若min（a，b）==(int)(abs(a-b)*(sqrt(5)+1)/2)，则此时为一个奇异局势，即先手必输。

至于具体的理解，还可以借助一个二维棋盘，一开始位于右下角，此时操作为沿一个方向走任意格，或者沿对角线移动，直至走到左上角判定为获胜。

#include<iostream>
#include<math.h>
#include<stdlib.h>
using namespace std;
int n,m;
double tmp=(sqrt(5)+1)/2;
int main(){
	while(cin>>n>>m){
		if(min(n,m)==(int)(abs(n-m)*tmp))cout<<0<<endl;
		else cout<<1<<endl;
	}
}
           

3.推广

有时我们不止需要判断先手胜负情况，我们还需要输出在先手必胜的前提下，先手可以进行的操作，我觉得只需要依次枚举操作，只有操作结束，后手进行操作时处于奇异局势下即后手必输，说明该操作可使得先手必胜。

二、尼姆博弈

1.引例——Matches Game

Matches Game

两方交替操作，均采取最优策略，无法操作即为失败，有n堆石子，每次操作需要选择一堆石子，并且从中拿出任意颗石子，可以一次性拿光。

2.分析

若为一堆：直接取完，先手必胜。

若为两堆：相等则先手必败；否则先手必胜。

当两堆石子个数相同时，先手必败，因为先手只能对一堆石子进行操作，要么取完，后手直接取另外一堆，即先手失败，；要么选择一堆不取完，而后手可令另外一堆减少相同数目石子，此时先手重新面临了两堆个数相同的石子。

若石子个数不等，反过来说即可通过操作使后手面临以上局面，即先手必胜。

若为三堆：若其中存在两堆石子个数相等，则先手必胜。

若三堆石子个数分别为a，b和c，且a==b，那么当先手拿光第三堆石子c时，后手面临着上方必败的情况。

如果三堆石子数均不相等，那么又需要怎么判断呢？

与二进制的联系（向n堆石子的推广）：

子堆划分：以石子数为7的一堆石子为例，我们根据它的二进制（111）视其为三个子堆，个数分别为4、2、1。

数据处理：对于三堆石子，分别为4（100），6（110），7（111），

可划分为石子个数为1的堆数为1，石子个数为2的堆数为2，石子个数为4的堆数为3.

结果判定：4（100）^ 6（110）^ 7（111）！=0；

若n个数异或和结果为0，则被称为平衡态，平衡态下先手必败；

若不为0，则为非平衡态，此时先手必胜。

#include<iostream>
using namespace std;
int p;
int n;
int main(){
	while(cin>>n&&n){
		int tmp=0;
		for(int i=0;i<n;i++){
			cin>>p;
			tmp^=p;
		}
		if(!tmp)cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
	}
}
           

3.异或和处理的正确性证明

1.终止状态下，满足异或和为0的平衡态

当选手面临无法操作的情况，就判定为失败，也就是所有堆都为0，异或和为0，满足平衡态。

2.由非平衡态存在一种方式可以变为平衡态（先手必胜分析）

以 a 1 a_1 a1​、 a 2 a_2 a2​… a n a_n an​表示所有堆的石子数，以sum表示 a 1 a_1 a1​^ a 2 a_2 a2​^ …^ a n a_n an​，分析sum二进制中的最高位的1，设其为第k位，这个1意味着在 a 1 a_1 a1​、 a 2 a_2 a2​… a n a_n an​中，至少存在一个数在这一位的值同样为1，不妨令这个数为 a i a_i ai​。

此时必定存在关系：sum ^ a i a_i ai​ < a i a_i ai​

sum ^ a i a_i ai​ 将 a i a_i ai​中的第k位置为0，对更高位无影响，那么可知此时的 a i a_i ai​必定小于原来的值。

根据异或的知识，sum ^ a i a_i ai​ 的结果其实就是原来所有元素除去 a i a_i ai​的异或和，若此时 a i a_i ai​变为了sum ^ a i a_i ai​（一个小于 a i a_i ai​的数，可以通过操作来实现），那么接下来所有元素的异或和就是：sum ^ a i a_i ai​ ^ sum ^ a i a_i ai​，即0.

由上可知，由非平衡态存在一种方式可以变为平衡态。

3.由平衡态只能变为非平衡态（先手必败分析）

反证：若由平衡态可以变为平衡态，此时仍然对 a i a_i ai​进行处理，此时sum为0，tmp = sum ^ a i a_i ai​

处理之后，tmp不发生变化，而sum仍然为0，那么 a i a_i ai​= tmp^sum，可知 a i a_i ai​其实没有发生变化，然而这是不满足题目要求的，所以不成立。

由上可知，由平衡态只能变为非平衡态

4.小结

由上可知，掌握着非平衡态的选手总有办法使对方陷入平衡态，一步一步下去，对方也无法摆脱这种身份，只会最终走向终止状态。

故证明了异或和方法的正确性。

4.例题——如何在非平衡态下进行第一次选择使得变为平衡态

此时只能选择一堆进行操作，我们的目标是通过修改这一堆的值（只能减少）使结果变成平衡态。

事实上先不管我们选择的这一堆，而将其余的堆之间进行异或和处理，我们设这个异或和为tmp,而我们令选择的那一堆为A，我们需要确定有无一个值a（a<A，因为a要是A通过减少石子可以变为的状态）可以使得a^tmp结果为0。

我们可以得知其实在tmp确定的前提下，其实这个a值其实是确定的，所以我们只需要判断这个a与A的大小关系，就可以得知该操作是否合法。

a的确定也只需要借助异或操作的性质，一开始我们会用sum来存所有数的异或和，而sum^A即tmp，因为tmp=tmp ^ A ^ A= sum ^ A; 而a^tmp等于0，说明了a==tmp

所以我们只要比较sum^A跟A的大小关系

例题：Being a Good Boy in Spring Festival

#include<iostream>
using namespace std;
int p[105];
int n;
int main(){
	while(cin>>n&&n){
		int tmp=0;
		for(int i=0;i<n;i++){
			cin>>p[i];
			tmp^=p[i];
		}
		if(!tmp)cout<<0<<endl;
		else {
			int cnt=0;
			for(int i=0;i<n;i++){
				if(p[i]>(tmp^p[i]))cnt++;
			}
			cout<<cnt<<endl;
		}
	}
}