棋局评估(不常见的搜索)

棋局评估(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;
}