概述

对抗搜索又称极大极小搜索(minimax search),是对于sg搜索的推广。
适用于完全信息,无概率因素,轮流操作的双人零和(即双方利益完全对立)博弈

但是双人麻将(非完全信息,因为不能看到对方的牌),大富翁(存在概率因素),石头剪刀布(同时操作)等不在讨论范围内。

我们将有利的一方称为MAX游戏者,另一方为MIN游戏者
二者完全对立,分数越高对MAX越有利,对MIN越不利

MAX 和 MIN 轮流做出决策,扩展出所有有可能的子局面,然后做出选择。
我们画出一颗博弈树

minimax
好吧,不要吐槽,用google doc画的-_-||

每个结点代表该局面的得分,MAX游戏者的得分为所有子节点中的最大值,MIN游戏者为所有子节点中的最小值
不难发现,最优策略的所有局面分数相同。

α-β剪枝

在实际应用中,博弈树往往很大,我们无法扩展出整棵博弈树,所以minimax search 常常要用到α-β剪枝
其思想如下:

  • 每个MAX结点设置一个目前已知下界 alpha
  • 每个MIN结点设置一个目前已知上界 beta
  • 当计算到一般MAX结点时,若其beta小于等于其父节点(MAX结点)的alpha值时 (α剪枝)
  • 当计算到一般MAX结点时,若其alpha大于等于其父节点(MIN结点)的beta值时,不再扩展 (β剪枝)

alpha-beta
这就是上面博弈树的剪枝
上面子树子节点的扩展是从左至右进行的(有时候对子节点排序可以加快剪枝效率,即优先考虑更有利于剪枝的节点)

框架

这类题目一般很固定,只需要设计状态即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void minimax(State& s,int player,int alpha,int beta)
{
if(s.isFinal()) return s.score;

vector<State> sons;
s.expend(player,sons);

int n = son.size();
for(int i=0;i<n;++i)
{
int v = minimax(son[i],player^1,alpha,beta);
if(!player)
alpha = max(alpha,v);
else
beta = min(beta,v);
if(beta <= alpha) break;
}

return !player ? alpha:beta;
}

1
2
// ( 0 MAX  1 MIN ) is the first player
minimax(start,player,-INF,INF);

题目

uva1085(la4451)

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>

using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 100;
const int UP = 0,FLOOR = 1,DOWN = 2;
// / up \ down _ floor
int deck[maxn],n;

struct State
{
int card[8],type[8];
int hold[2];
int pos;
int score;

State()
{
for(int i=0;i<8;++i)
{
card[i] = deck[i];
type[i] = i&1 ? DOWN:UP;
}
hold[0] = hold[1] = score = 0;
pos = 8;
}

bool IsFinal()
{
if(pos == 2*n)
{
score += hold[0] + hold[1];
hold[0] = hold[1] = 0;
return true;
}
return false;
}

int getScore(int a,int b,int c) const
{
int S = abs(a) + abs(b) + abs(c);
int cnt = 0;
if(a>0) ++cnt;
if(b>0) ++cnt;
if(c>0) ++cnt;
return cnt>=2 ? S:-S;
}

State son() const
{
State s;
memcpy(&s,this,sizeof(s));
s.pos = pos + 1;
return s;
}

void expend(int player,vector<State>& res) const
{
int cur = deck[pos];

//1. hold in hand
if(hold[player] == 0)
{
State s = son();
s.hold[player] = cur;
res.push_back(s);
}

//2. new ceil
for(int i=0;i<7;++i) if(type[i] == DOWN && type[i+1] == UP)
{
//use cur;
State s = son();
s.score += getScore(card[i],card[i+1],cur);
s.type[i] = s.type[i+1] = FLOOR;
s.card[i] = s.card[i+1] = cur;
res.push_back(s);

if(hold[player] != 0)
{
//use held card;
State s = son();
s.score += getScore(card[i],card[i+1],hold[player]);
s.type[i] = s.type[i+1] = FLOOR;
s.card[i] = s.card[i+1] = hold[player];
s.hold[player] = cur;
res.push_back(s);
}
}

//3. new peak
if(hold[player] != 0)
{
for(int i=0;i<7;++i) if(type[i] == FLOOR && type[i+1] == FLOOR && card[i] == card[i+1])
{
State s = son();
s.score += getScore(card[i],hold[player],cur);
s.type[i] = UP;
s.type[i+1] = DOWN;
s.card[i] = cur ;
s.card[i+1] = hold[player];
s.hold[player] = 0;
res.push_back(s);

swap(s.card[i],s.card[i+1]);
res.push_back(s);
}
}

}

};

int maxmin(State& S,int player,int alpha,int beta)
{
if(S.IsFinal()) return S.score;

vector<State> sons;

S.expend(player,sons);

int n = sons.size();
for(int i=0;i<n;++i)
{
int v = maxmin(sons[i],player^1,alpha,beta);
if(!player)
alpha = max(alpha,v);
else
beta = min(beta,v);
if(beta <= alpha) break;
}
return !player? alpha : beta;
}

int main()
{
//freopen("test.txt","r",stdin);
char name[10];
int kase = 0;
while(scanf("%s",name)==1 && name[0]!='E')
{
scanf("%d",&n);
for(int i=0;i<n*2;++i)
{
char ch;
scanf("%d%c",deck+i,&ch);
if(ch == 'B') deck[i] = -deck[i];
}
State start;
int first_player = deck[0]>0? 0 : 1;
int score = maxmin(start,first_player,-INF,INF);

if(name[0] == 'B') score = -score;
printf("Case %d: ",++kase);
if(score == 0) puts("Axel and Birgit tie");
else if(score > 0) printf("%s wins %d\n",name,score);
else printf("%s loses %d\n",name,-score);
}
return 0;
}