这个题一开始被上学期人工智能写的五子棋ai迷惑了，想了半天不知道怎么设置局面估分才能保证着法最优，后来发现这题就\(3\times 3\)的棋盘，剪个锤子的alpha-beta剪枝...直接爆搜到底就好。最优走法就是对于当前局面每种可能的落子处进行落子然后搜索，得到的分数最优的就是当前局面的最佳着法。题目很贴心的让bob的分数是负数，alice的是整数，正好方便我们的搜索。
#include <bits/stdc++.h>
using namespace std;
int mp[5][5];
int countblank() {//统计空格
int ans = 0;
for(int i = 1; i <= 3; i++) {
for(int j = 1; j <= 3; j++) {
if(mp[i][j] == 0) ans++;
}
}
return ans;
}
bool row3(int x, int num) {//判断每个横行
for(int i = 1; i <= 3; i++) {
if(mp[x][i] != num) return 0;
}
return 1;
}
bool col3(int y, int num) {
for(int i = 1; i <= 3; i++) {
if(mp[i][y] != num) return 0;
}
return 1;
}
bool alicewin() {//判断alice是否能赢
for(int i = 1; i <= 3; i++) {
if(row3(i, 1)) return 1;
}
for(int i = 1; i <= 3; i++) {
if(col3(i, 1)) return 1;
}
if(mp[1][1] == mp[2][2] && mp[1][1] == mp[3][3] && mp[1][1] == 1) return 1;
if(mp[1][3] == mp[2][2] && mp[1][3] == mp[3][1] && mp[1][3] == 1) return 1;
return 0;
}
bool bobwin() {
for(int i = 1; i <= 3; i++) {
if(row3(i, 2)) return 1;
}
for(int i = 1; i <= 3; i++) {
if(col3(i, 2)) return 1;
}
if(mp[1][1] == mp[2][2] && mp[1][1] == mp[3][3] && mp[1][1] == 2) return 1;
if(mp[1][3] == mp[2][2] && mp[1][3] == mp[3][1] && mp[1][3] == 2) return 1;
return 0;
}
int dfs(int curplayer) {//当前为1表示alice落子，为2表示bob落子
//cout << curplayer << endl;
int blank = countblank();
if(alicewin()) {
return blank + 1;
} else if(bobwin()) {
return -(blank + 1);
} else if(blank == 0) {
return 0;//平局
}
int maxx = -0x3f3f3f3f, minn = 0x3f3f3f3f;
for(int i = 1; i <= 3; i++) {
for(int j = 1; j <= 3; j++) {
if(mp[i][j] == 0) {
mp[i][j] = curplayer;
int tmp = dfs(3 - curplayer);//更换执子方继续搜索
maxx = max(maxx, tmp);
minn = min(minn, tmp);
mp[i][j] = 0;//回溯
}
}
}
if(curplayer == 1) return maxx;//是alice的话找到得分最正的走法的局面
else return minn;//是alice的话找到得分最负的走法的局面
}
int main() {
int t;
cin >> t;
while(t--) {
memset(mp, 0, sizeof(mp));
for(int i = 1; i <= 3; i++) {
for(int j = 1; j <= 3; j++) {
cin >> mp[i][j];
}
}
cout << dfs(1) << endl;
}
return 0;
}