棋局评估(MINMAX搜索+α-β剪枝)
这是一个博弈的问题,在这里,你的对手希望他得高分,你希望你得高分,可是你分数高了他的分就低了。下棋的时候,你希望走出最好的局面,即使输也要分数最高,而你的对手恰恰相反,他要走出他的最好局面,也就是你的最坏局面,让你分数最低。这样交替行棋,也就完成了对棋局的推演,得出高手的最终局势。需要用到一种博弈搜索的算法MINMAX搜索,这道题还可以用一下 α-β 剪枝算法,但这题的数据量不大,也可以不用。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=4;
const int INF=0x3f3f3f3f;
int D[maxn][maxn];//棋盘
int check(int x)//看看这个人是否获得胜利
{
for(int i=1;i<=3;i++)//横竖
{
if(D[i][1]==x&&D[i][2]==x&&D[i][3]==x)return true;
if(D[1][i]==x&&D[2][i]==x&&D[3][i]==x)return true;
}
//对角线
if(D[1][1]==x&&D[2][2]==x&&D[3][3]==x)return true;
if(D[3][1]==x&&D[2][2]==x&&D[1][3]==x)return true;
return false;
}
int blank()
{
int sum=0;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
if(D[i][j]==0)sum++;
return sum;
}
int MINMAX_DFS(int X,int value)//轮到谁下棋
{
int num=blank();//现在是你下棋,检查一下上一个下棋的人赢了没有
if(X==1&&check(2))return -num-1;//这里是估值函数,一般是别人定的,也是决定这个算法强弱的关键要素
if(X==2&&check(1))return num+1;//这里主要是避免和0重复,冲突;
if(num==0)return 0;//平局的情况
if(X==1){
int max_value=-INF;//要找最大,初始化为-INF
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
if(!D[i][j]){
D[i][j]=1;
max_value=max(MINMAX_DFS(2,max_value),max_value);
D[i][j]=0;
if(max_value>value)return max_value;//剪枝
}
return max_value;
}else{
int min_value=INF;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
if(!D[i][j]){
D[i][j]=2;
min_value=min(MINMAX_DFS(1,min_value),min_value);
D[i][j]=0;
if(min_value<value)return min_value;
}
return min_value;
}
}
int main(void)
{
int T;scanf("%d",&T);
while(T--)
{
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
scanf("%d",&D[i][j]);
int ans=MINMAX_DFS(1,INF);//要找最大的,所以上一个是无限大
cout<<ans<<endl;
}
return 0;
}
标签:剪枝,棋局,int,value,搜索,include,评估
From: https://www.cnblogs.com/WUTONGHUA02/p/16653830.html