C++中的博弈问题

C++中的博弈问题

本文仅讨论符合以下条件的博弈问题
1、当前状态不是先手必胜态就是先手必败态。
2、若当前状态存在一种转化为先手必败态的方式，则当前状态为先手必胜态。
3、若当前状态不存在一种转化为先手必败态的方式，则当前状态为先手必败态。

那么一般的博弈问题，失败条件是已知的，而失败状态就为一种先手必败态。当你知道先手必败态，就可以跟上述3大规则来把跟博弈中的所有状态表示出来。
圆圈表示状态
线条表示转换
1代表胜利
X代表失败
空缺代表未知
则已知一个博弈问题的所有状态如下。

则根据上述3大规则
我们可以推导出所有状态

所以该博弈先手必胜
引出SG函数，

首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

（摘自百度百科）

我们定义每个状态可以延伸到的所有状态的sg函数值，为该点的子集。
该点的sg值为该点的mex值
我们的图就变成

举个例子对于点4，他可以衍生到点1和点2，sg分别为1、0，所以当前点的sg值为2。
我们可以发现，sg值为0的点是先手必败，大于0的点先手必胜。
或许以后会更准确地说明SG函数的用途。

假想有以下情景
A与B玩取石子游戏，已知石子总数为n，每人轮流取石子，每次只能取1或2或3颗石子，不得不取，先把石子取空的一方胜利，A先手。假设A、B都聪明绝顶，问谁胜利。
1、记忆化搜索

#include<iostream>
#include<cstdio>
#include<cstring>
int fsg[1001];
int n;
bool fakesg(int num){
	if(fsg[num]!=-1){
		return fsg[num];
	}
	if((!fakesg(num-1))||(!fakesg(num-2))||(!fakesg(num-3))){
		fsg[num]=1;
	}
	else{
		fsg[num]=0;
	}
	return fsg[num];
	
}

int main(){
	memset(fsg,-1,sizeof(fsg));
	scanf("%d",&n);
	fsg[1]=fsg[2]=fsg[3]=1;
	
	if(fakesg(n)){
		printf("A win");	
	}
	else{
		printf("B win");
	}
	
} 

2、找规律 推导。
以下以1表示先手赢，0表示先手败。
对于n=4
它可以转化为n=1，n=2，n=3，对应的状态为1，1，1.
所以n=4为0，
同样的，我们可以推出
n=5 为1
n=6 为 1
n=7 为 1
n=8 为 0
同时我们发现，推出n=8的状态的过程和n=4相同，皆为（1，1，1）
我们归纳一下，便可知道这个博弈游戏的状态4各一循环。

2、nim游戏（先对异或运算的性质有所了解）
如果是有n堆石子，每堆有若干石子，A与B博弈，每人每轮只能取一堆里面任意石子（不得不取）。先取完所有石子的人胜利，问先手必胜还是必败。
先说如何判断
把n堆棋子依次进行异或运算，如果结果为0，则先手必败，否则先手必胜。
思考一下为什么博弈论会和异或运算这个位运算扯上关系。

理由如下

推论1：所有堆都没有石子时，所有堆石子数异或运算结果为0。

推论2：若当前所有堆石子数异或和不为0，则必定存在一种合法的取法，使得取完后，剩下的石子数异或运算结果为0。
设n=（a_1） XOR （ a_2） XOR （a_3）……XOR （a_m）（（a_i）为第i堆石子的石子数）
证明：由于一个数有且只有与自身相同的数进行异或运算，结果才为0。
即必须要设法使其中一堆的石子数 = 除该堆石子外 其他所有堆石子的异或值。
所以只需证明存在（a_i），使得（a_i）>n XOR （a_i），即第i堆石子能够取走一些石子，使得该堆石子数为n XOR （a_i）。
找到与n相同位数的（a_i），（由于异或运算的性质，（a_i）一定存在）该（a_i）一定满足（a_i）>n XOR （a_i）。
证毕。

由上述两条推论
我们可以推理出：当我们取石子时，如果我们所有堆石子数异或运算结果不为0，那么我们可以一直让对方取石子的状态为所有堆石子数异或运算结果为0。因为失败时，所有堆石子数异或运算结果为0，所以我们永远不会失败。而对方会随着游戏的进行走向失败。
所以把n堆棋子依次进行异或运算，如果结果为0，则先手必败，否则先手必胜。
程序如下

#include<iostream>
#include<cstdio>
using namespace std;
int n;



int main(){
	int i;
	int n,temp;
	int ans;
	scanf("%d",&n);
	ans=0;
	for(i=1;i<=n;i++){
		scanf("%d",&temp);
		ans^=temp;
	}
	if(ans){
		printf("Yesn");
	}
	else{
		printf("Non");
	}


	
} 

或许未完待续

最后

以上就是贪玩面包最近收集整理的关于C++中的博弈问题的全部内容，更多相关C++中内容请搜索靠谱客的其他文章。