一、 对抗搜索的适用范围
在博弈论题目中，如果决策双方的获胜条件是截然相反的，即一方要求得分越高越好，另一方要求得分越低越好，这时我们就可以用上对抗搜索算法。
二、对抗搜索的主要思想
对抗搜索的核心思想就是dfs遍历一遍博弈树。
不难想到，如果博弈树非常庞大，在不加优化的情况下，对抗搜索的时间效率是十分低下的。
因此，我们就需要对对抗搜索进行一定的优化。
三、对抗搜索的优化
对抗搜索的优化一般来讲有两种：记忆化和Alpha−Beta剪枝 。
https://blog.csdn.net/chenxiaoran666/article/details/82809890
#include <iostream> //#include <bits/stdc++.h> #include <string> using namespace std; int isWin(int &score); int M[3][3]; int main() { int number; cin>>number; for(int k=0;k<number;k++) { int score=1; for(int i=0;i<3;i++) { cin>>M[i][0]>>M[i][1]>>M[i][2]; } int flag=isWin(score); if(flag==1) cout<<score; else if(flag==2) cout<<"-"<<score; else cout<<"0"; cout<<endl; } } int isWin(int &score) { int flag=0; for(int i=0;i<3;i++) { if(M[i][0]==M[i][1]&&M[i][0]==M[i][2]) { if(M[i][0]==1) flag=1; else if(M[i][0]==2) flag= 2; } else if(M[i][0]!=2&&M[i][1]!=2&&M[i][2]!=2&&M[i][0]+M[i][1]+M[i][2]==2) { flag=1; score--; } } for(int i=0;i<3;i++) { if(M[0][i]==M[1][i]&&M[0][i]==M[2][i]) { if(M[0][i]==1) flag= 1; else if(M[0][i]==2) flag= 2; } else if(M[0][i]!=2&&M[1][i]!=2&&M[2][i]!=2&&M[0][i]+M[1][i]+M[2][i]==2) { flag=1; score--; } } if( (M[0][0]==M[1][1]&&M[1][1]==M[2][2]) ||(M[2][0]==M[1][1]&&M[1][1]==M[0][2]) ) { if(M[1][1]==1) flag= 1; else if(M[1][1]==2) flag= 2; } else if((M[0][0]!=2&&M[1][1]!=2&&M[2][2]!=2&&M[0][0]+M[1][1]+M[2][2]==2) ||(M[2][0]!=2&&M[1][1]!=2&&M[0][2]!=2&&M[2][0]+M[1][1]+M[0][2]==2) ) { flag=1; score--; } for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { if(M[i][j]==0) score++; } } return flag; }
#include <iostream>
//#include <bits/stdc++.h>
#include <string>
using namespace std;
int mp[4][4];
bool hok(int h,int f)
{
return mp[h][0]==f&&mp[h][0]==mp[h][1]&&mp[h][1]==mp[h][2]; //判断行是否三颗相连
}
bool lok(int l,int f)
{
return mp[0][l]==f&&mp[0][l]==mp[1][l]&&mp[1][l]==mp[2][l]; //判断列是否三颗相连
}
int spa()
{
int res=0;
for(int i=0; i<3; i++)
for(int j=0; j<3; j++)
if(!mp[i][j])res++;
return res;
}
int win(int f) //判断当前局面胜负情况
{
int wi=0,ans=1;
if(hok(0,f)||hok(1,f)||hok(2,f))wi=1;
if(lok(0,f)||lok(1,f)||lok(2,f))wi=1;
if(mp[0][0]==f&&mp[0][0]==mp[1][1]&&mp[1][1]==mp[2][2])wi=1;
if(mp[0][2]==f&&mp[0][2]==mp[1][1]&&mp[1][1]==mp[2][0])wi=1;
if(!wi)return 0;
ans+=spa();
return (f==1)?ans:-ans;
}
int dfs(int peo) //对抗搜索
{
if(!spa())return 0;
int Max=-10,Min=10;
for(int i=0; i<3; i++)
{
for(int j=0,w; j<3; j++)
{
if(!mp[i][j]) //未放子处 //枚举可以落棋的位置
{
mp[i][j]=peo+1;
w=win(peo+1);
if(w)//分出胜负
{
mp[i][j]=0;
return w>0?max(Max,w):min(Min,w);
}
if(!peo)Max=max(Max,dfs(1));//递归
else Min=min(Min,dfs(0));
mp[i][j]=0;
}
}
}
return peo?Min:Max; //0-Alice-Max，1-Bob-Min
}
int main()
{
int t;
cin>>t;
while(t--)
{
for(int i=0; i<3; i++)
for(int j=0; j<3; j++)
cin>>mp[i][j];
int x=win(1),y=win(2);
if(x)
{
cout<<x<<endl;
continue;
}
if(y)
{
cout<<y<<endl;
continue;
}
cout<<dfs(0)<<endl; //0表示Alice下，1表示Bob下
}
return 0;
}