首页 > 代码库 > 博弈-组合游戏
博弈-组合游戏
组合游戏：
规则1：一个状态是必败的状态，当且仅当它的所有后继状态为必胜状态
规则2：一个状态是必胜的状态，当且仅当它的所有后继状态中至少有一个是必败状态
1.Ferguson游戏：
两个盒子有石子n，m。游戏规则为选择其中一个盒子清空，把另一个盒子的石子拿一些给清空的盒子，但需保证至少都有一个。。终态为[1,1]
状态：
从后向前推，[n,m]状态能推出的有一个为必败，则[n,m]必胜
[n,m]能推出的全为必胜，则[n,m]必败
#include <iostream>
using namespace std;
#define maxn 100
int win[maxn][maxn];
int main(){
win[1][1]=false;
for(int k=3;k<20;k++){
for(int n=1;n<k;n++){
int m=k-n;
win[n][m]=false;
for(int i=1;i<n;i++)
if(!win[i][n-i])win[n][m]=true;
for(int i=1;i<m;i++)
if(!win[i][m-i])win[n][m]=true;
if(n<=m && !win[n][m]) cout<<n<<" "<<m<<endl;
}
}
return 0;}
//两个盒子有石子n，m。游戏规则为选择其中一个盒子清空，把另一个盒子的石子拿一些给清空的盒子，但需保证至少都有一个。。终态为[1,1]
//从后向前推，[n,m]状态能推出的有一个为必败，则[n,m]必胜
// [n,m]能推出的全为必胜，则[n,m]必败Chomp！游戏：
有一个m×n的棋盘，每次可以取走一个方格并它右边和左边的所有棋子，取到最后拿到(1,1)的输
结论：除了（1，1）先手必败，其他情况必胜：
证明：
假设当前先手去了最右上角的那个方格，则后手选择了(k1,k2)进入了必胜状态，则显然先手刚开始也可以取(k1,k2)进入必胜状态。于是矛盾
约数游戏：
有1～n个数，两个人轮流取一个数并它所有的约数抹去，最后取完的胜；
显然先手一直必胜：
证明：假设先手先取了1，然后后手去了k进入必胜状态，显然先手开始也可以取k进入该必胜状态，因此矛盾
nim博弈：
结论：如果有x1^x2^...^xn=X，若X=0则必败，否则必胜
1.对于没有火柴的状态，显然是必败状态
2.对于必胜状态，必能推出必败状态：
证明：假设X不为0，且X的最高位(二进制)在第k位，显然xi中至少会有一个Y，第k位也为1（否则异或运算时，第k位的1没法获得），则第一次取的时候在Y上拿成Z=Y^X
显然Z<Y成立，因为异或运算只改变了Y的第k位的1和后面的部分，前面的高位未动，相比之前变小了。拿成Z之后，在进行运算，即X^Z^Y=X^X=0;
3.对于必败的状态，推出的都是必胜状态
证明：必败时，X=0，因为只能取一堆，因此无论怎么取，都只能使X非0;
组合游戏的和：
假设有K个组合游戏，G1 G2 G3 ... Gn。每次可以选择任一个进行，其他局面不变。
解决办法：SG函数和SG定理：
SG（x）=mex(S),S是x的后继状态的SG函数值集合，mex(S)表示不在S内的最小非负整数；
游戏和的SG函数等于各子游戏SG函数的NIM和
石子游戏：n堆石子，只能取 至少一个，且不能超过一半，最后不能取得输。
1.先算一下SG函数：
#include <iostream>
#include <string.h>
using namespace std;
#define maxn 110
int sg[maxn];
int vis[maxn];
int main(){
sg[1]=0;
for(int i=2;i<maxn;i++){
memset(vis,0,sizeof(vis));
for(int j=1;j*2<=i;j++)vis[sg[i-j]]=1;
for(int j=0;;j++){
if(!vis[j]){
sg[i]=j;
break;
}
}
cout<<sg[i]<<" ";
}
cout<<endl;
return 0;}
(从2开始)
1 0 2 1 3 0 4 2 5 1 6 3 7 0 8 4 9 2 10 5 11 1 12 6 13 3
可以得出结论：
sg(n)=sg(n/2);n为奇数
sg(n)=n/2；n为偶数
于是得到如下程序：
#include <iostream>
#include <string.h>
using namespace std;
#define maxn 110
long long sg(long long x){
return x%2==0? x/2:sg(x/2);
}
int main(){
int t;
cin>>t;
while(t--){
int n;
long long a,v=0;
cin>>n;
for(int i=0;i<n;i++){
cin>>a;
v^=sg(a);
}
if(v)cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
return 0;}
treblecross游戏
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int sg[202];//sg[i]表示连续的x个空格子组成的棋盘的SG值
int vis[202];
void init()
{
int i,j,k;
sg[0]=0;
sg[1]=sg[2]=sg[3]=1;
for(i=4;i<=200;i++)
{
memset(vis,0,sizeof(vis));
for(j=3;j<=5&&i-j>=0;j++) vis[sg[i-j]]=1;
for(j=6;i-j>=0;j++) vis[sg[j-5]^sg[i-j]]=1;
for(j=max(i-5,0);j<=i-3;j++) vis[sg[j]]=1;
for(j=0;j<=200;j++)
if(!vis[j])
{
sg[i]=j;
break;
}
}
}
int e[202],f[202],g[202],n;
int find()
{
int s=0,i,j,k=0;
for(i=0;i<n;i++)
{
if(f[i]==0)
k++;
else
{
s=s^sg[k];
k=0;
}
}
s=s^sg[k];
return s;
}
int main()
{
init();
char a[202];
int T;
cin>>T;
while(T--)
{
cin>>a;
int i,j,k,flag=0,t=0;
n=strlen(a);
for(i=0;i<n;i++)
{
if(i<n-2&&a[i+1]==‘X‘&&a[i+2]==‘X‘){flag=1;e[t++]=i;}
else if(i>0&&a[i-1]==‘X‘&&a[i+1]==‘X‘){flag=1;e[t++]=i;}
else if(i>1&&a[i-1]==‘X‘&&a[i-2]==‘X‘){flag=1;e[t++]=i;}
}
if(flag)
{
cout<<"WINNING"<<endl;
cout<<e[0]+1;
for(i=1;i<t;i++)
cout<<" "<<e[i]+1;
cout<<endl;
}
else
{
memset(g,0,sizeof(g));
for(i=0;i<n;i++)
if(a[i]==‘X‘)
{
for(j=i-2;j<=i+2;j++)
if(j>=0&&j<n)
g[j]=1;
}
memcpy(f,g,sizeof(f));
if(find()==0)
{
cout<<"LOSING"<<endl<<endl;
continue;
}
for(i=0;i<n;i++)
{
if(g[i]==0)
{
memcpy(f,g,sizeof(f));
for(j=i-2;j<=i+2;j++)
if(j>=0&&j<n)
f[j]=1;
if(find()==0)
e[t++]=i;
}
}
cout<<"WINNING"<<endl;
cout<<e[0]+1;
for(i=1;i<t;i++)
cout<<" "<<e[i]+1;
cout<<endl;
}
}
return 0;
}
取石子（十）
- 描述
不知不觉取石子已经到第十道了。地球上的石子也快要取完了！
开个玩笑，当然还是有很多石子的，取石子的题目也是做不完的，今天又来了一道！
有n堆石子，每一堆的规则如下：
第一堆每次只能取2的幂次（即：1，2，4，8，16…）；
第二堆只能取菲波那契数列中的元素（即每次只能取1，2，3，5，8…等数量，斐波那契数即后面的数是前面两个数的和）；
第三堆可以取任意多个，最小1个，最多可以把这一堆石子取完；
第四堆只能取1和偶数个（即：1,2,4,6,8,10...）；
第五堆只能取奇数个（即：1,3,5,7,9.....）；
好吧，这样下去太烦人了，六堆及其以后每堆最多取的数量为堆数编号，即第六堆只能取（1,2,3,4,5,6），第七堆只能取（1,2,3,4,5,6,7）....
别看规则很多，但Yougth和Hrdv都是聪明人，现在由Yougth先取，比赛规定谁先取完所有石子既为胜者，输出胜者的名字。
- 输入
- 有多组测试数据，每组测试数据开始有一个n。
后面有n个数代表每一堆石子的数量，当n为0是表示输入结束。(所有数据小于1000) - 输出
- 假如Yougth赢输出“Yougth”，Hrdv赢输出“Hrdv”。
- 样例输入
6 2 4 2 3 6 7
- 样例输出
Hrdv
首先：第一石子的sg函数：
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
#define maxn 100
int sg[maxn];
int vis[maxn];
int main(){
sg[0]=0;
cout<<0<<" ";
for(int i=1;i<maxn;i++){
memset(vis,0,sizeof(vis));
for(int j=1;j<=i;j*=2){vis[sg[i-j]]=1;}
for(int j=0;;j++){
if(!vis[j]){
sg[i]=j;
break;
}
}
cout<<sg[i]<<" ";
}
return 0;}
得出数据分析规律可知：
sg(i)=i%3;
同理程序计算第二堆
（因为规律较为复杂，于是直接用函数计算，存储下来）
第三堆sg函数为：
sg(i)=i;
第四堆sg函数：
if(i==1 || i==2)
sg(i)= i;
else sg(i)= ((i-2)/6)*3+(i-2)%6-1;
第五堆sg函数为：
sg(i)=i%2;
剩下的第k堆：
sg(i)=(i)%(k+1);
然后套用组合游戏的规律，把每堆的sg函数值进行NIM异或，得到sum，sum==0 后手赢 sum！=0 先手赢
于是可得以下程序：
#include <iostream>
#include <string.h>
#include <cmath>
using namespace std;
#define maxn 1010
int a[maxn];
int sg[maxn];
void fun1(){
//int sg[maxn];
int vis[maxn];
int a[maxn];
a[1]=1;a[2]=2;
for(int i=3;i<maxn;i++)
a[i]=a[i-1]+a[i-2];
sg[0]=0;
for(int i=1;i<maxn;i++){
memset(vis,0,sizeof(vis));
for(int j=1;a[j]<=i;j++){vis[sg[i-a[j]]]=1;}
for(int j=0;;j++){
if(!vis[j]){
sg[i]=j;
break;
}
}
}
}
int fun(int i,int n){
if(n==1) return i%3;
else if(n==2){
if(i==0)
return 0;
// int bb[35]={1 ,2 ,3 ,0 ,1 ,2 ,3, 4 ,5 ,0 ,1 ,2 ,3 ,0 ,1 ,2 ,3 ,4 ,5 ,0 ,1 ,2 ,3 ,0 ,1 ,2 ,3 ,4 ,5 ,0 ,1 ,2 ,3 ,4 ,5};
// return bb[(i-1)%35];
return sg[i];
}else if(n==3){
return i;
}else if(n==4){
if(i==0)
return 0;
if(i==1 || i==2)
return i;
else
return ((i-2)/6)*3+(i-2)%6-1;
}else if(n==5){
return (i)%2;
}else{
return (i)%(n+1);
}
}
int main(){
fun1();
int n;
while(cin>>n,n){
for(int i=0;i<n;i++){
cin>>a[i];
}
int sum=0;
for(int i=0;i<n;i++){
sum^=fun(a[i],i+1);
}
if(sum)cout<<"Yougth"<<endl;
else cout<<"Hrdv"<<endl;
}
return 0;}