CCF认证 棋局评估(博弈对抗搜索)

题意

传送门

思路

典型博弈里的对抗搜索。
1.Alice得分为正数,Bob赢得分为负数
2.对于当前的一个状态,如果是Alice赢那么他一定会让自己得到的分数最大
3.对于当前的一个状态如果Bob赢那么他一定也会让自己得到的分数最大,这里Bob得分为负数所以可以变为Bob让自己得分最小。(最大最小的意思就是找自己能赢状态里的最)
4.这里因为是$3 \times 3$的格子复杂度为$O(9!)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>

using namespace std;
const int maxn = 10;
int a[5][5],n;
int Count()
{
int cnt = 0;
for(int i = 1;i <= 3;++i)
for(int j = 1;j <= 3;++j)
if(!a[i][j])
cnt++;
return cnt;
}
int hang(int id,int num)
{
return a[id][1] == num && a[id][2] == num && a[id][3] == num;
}
int lie(int id,int num)
{
return a[1][id] == num && a[2][id] == num && a[3][id] == num;
}
int check(int num)
{
int win = 0;
if(hang(1,num) ||hang(2,num) ||hang(3,num)) win = 1;
if(lie(1,num) || lie(2,num) || lie(3,num)) win = 1;
if(a[1][1] == num && a[2][2] == num &&a[3][3] == num)
win = 1;
if(a[1][3] == num && a[2][2] == num && a[3][1] == num)
win = 1;
if(!win) return 0;
int ans = Count() + 1;
return (num == 1)? ans:-ans;
}
int dfs(int cur)
{
if(!Count()) return 0;
int mi = 20,ma = -20;
for(int i = 1;i <= 3;++i)
{
for(int j = 1;j <= 3;++j)
{
if(a[i][j]) continue;
a[i][j] = cur;
int flag = check(cur);
if(flag)
{
a[i][j] = 0;
return (cur == 1)?max(ma,flag):min(mi,flag);
}
if(cur == 1)
ma = max(ma,dfs(2));
else
mi = min(mi,dfs(1));
a[i][j] = 0;
}
}
return (cur == 2)?mi:ma;
}
int main()
{
cin >> n;
while(n--)
{
for(int i = 1;i <= 3;++i)
for(int j = 1;j <= 3;++j)
scanf("%d",&a[i][j]);
int x = check(1),y = check(2);
if(x){cout << x << endl;continue;}
if(y){cout << y << endl;continue;}
cout << dfs(1) << endl;
}
return 0;
}

-------------本文结束感谢您的阅读-------------


本文标题:CCF认证 棋局评估(博弈对抗搜索)

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2018年09月19日 - 21:09

最后更新:2018年12月20日 - 21:12

原始链接:https://statusrank.xyz/articles/13e90b65.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!

相关文章: