【学习笔记】对抗搜索与Alpha-Beta剪枝

Posted on Edited on In , Comments: Views:

学了一下比较简单的博弈模型的常规求解方式，发现就是爆搜。顺便学了有启发式思想的 Alpha-Beta 剪枝，现在觉得是玄学……可能还是记搜比较靠谱？

1 对抗搜索

……然而其实就是搜索。每次大概就是记录一下双方的决策结果和（哈希之后的）局面，然后改谁走谁走就完了。伪代码大概可以这么写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Function doMax(State S){
	Value res = -Inf ;
	State Moveable_Set = calc(S) ;   
	for : s in Moveable_Set{
		Value now = evaluate(doMin(S)) ;
		if [now > res] res = now ; 
	} 
	return res ;
}
Function doMin(State S){
	Value res = Inf ;
	State Moveable_Set = calc(S) ;   
	for : s in Moveable_Set{
		Value now = evaluate(doMax(S)) ;
		if [now < res] res = now ; 
	} 
	return res ;	
}

大概就是交替迭代的思想。

考虑一棵博弈树，节点承载的信息是局面 。那么对于一个零和博弈游戏，双方必然是让自己得益更多，于是考虑转化一下，令局面的分数为「先手的分数 - 后手的分数」，那么先手就是最大化局面分数，后手则是最小化。

于是定义轮到最大化局面分数一方走的局面节点叫做 $\boldsymbol{Max}$节点，轮到最小化局面分数一方走的局面节点叫做 $\boldsymbol{Min}$节点 。那么显然在博弈树上同类节点集合是一个独立集。这种博弈也叫做 零和博弈完全信息公平博弈 ，双方的目的均是 最值化局面分数。

2 Alpha-Beta 剪枝

然后这东西就是一个剪枝，给每个节点一个 $\alpha$ 下界和 $\beta$ 上界。类比状态转移，考虑相邻的状态，大致如下：

  • 假设当前节点为 $\boldsymbol{Max}$ 节点，那么如果存在一种决策使得该 $\boldsymbol{Max}$ 状态的分数 $>$ 上一层决策的分数上限 $\beta’$，那么当前节点的父亲节点，$\boldsymbol{Min}$ 状态，就一定不会做出某些决策，使得局面变成当前的 $\boldsymbol Max$ 决策。

  • 假设当前节点为 $\boldsymbol{Min}$ 节点，那么如果存在一种决策使得该 $\boldsymbol{Min}$ 状态的分数 $<$ 上一层决策的分数下限 $\alpha’$，那么当前节点的父亲节点，$\boldsymbol{Max}$ 状态，就一定不会做出某些决策，使得局面变成当前的 $\boldsymbol Min$ 决策。

  • 于是我们记录 $\alpha$ 值为每个 $\boldsymbol{Max}$ 状态的得分下界，$\beta$ 值为每个 $\boldsymbol{Min}$ 状态的得分下界。初始为 $\alpha=-\infty,\beta=+\infty$

  • 考虑优化的意义。当前状态的分支可能有很多，但是如果在搜第一个分支的时候就发现已经有 $\alpha_n>\beta_{fa_n}$ 了，那么 $fa_n$ 就一定不会走这个决策（毕竟最次也可以让对方得益），于是剩下的分支就不用再搜了。

  • 显然，这种决策是启发性的。同时有以下特点：

    • 决策顺序影响时间效率。如果每次搜都在第一次跳出自然可以让时间上做到最优，但是如果每次都在最后一次跳出就是压根没剪。

    • 不可以裸的记忆化。考虑每个节点如果要记忆化，记下来的应该是当前状态能扩展到的最优局面。但是 Alpha-Beta 剪枝的目的就是在未得到这个点的最优决策时，已经知道该不该继续走。

然后就是伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Function doMax(State S, Value alpha, Value beta){
	State Moveable_Set = calc(S) ;   
	for : s in Moveable_Set{
		Value now = evaluate(doMin(S)) ;
		if [now > alpha] alpha = now ;
		if [alpha >= beta] return alpha ;  
	} 
	return alpha ;
}
Function doMin(State S, Value alpha, Value Beta){
	State Moveable_Set = calc(S) ;   
	for : s in Moveable_Set{
		Value now = evaluate(doMax(S)) ;
		if [now < beta] beta = now ; 
		if [alpha >= beta] return beta ;  
	} 
	return beta ;	
}

但是这样的话，我们顶多是能快速计算谁赢谁输而不是赢多少/输多少。于是考虑魔改一下：

版本一：某一方获利最多。参考题目：[九省联考]一双木棋，可以拿到 $70pts$

其实就是修改一下终态的返回值。

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
int battle(int dep, int x, int y, int alp, int bet, int sa, int sb){
//    cout << x << " " << y << endl ;
    if (dep >= N * M) return sa - sb ; int val, b = dep & 1;
//    memset(R[b], 0, sizeof(R[b])) ;
    if (!b){
           for (int i = 1 ; i <= N ; ++ i)
               for (int j = R[i] + 1 ; j <= M ; ++ j){
//                    cout << "A" << " " << dep << ".." << i << " " << j << endl ;
                   if (!base[i][j] && base[i][j - 1] && base[i - 1][j]){
                       base[i][j] = 1 ; R[i] = j ;
                       val = battle(dep + 1, i, j, alp, bet, sa + A[i][j], sb) ;
                       base[i][j] = 0 ; alp = max(val, alp) ;
                       R[i] = 0 ; if (alp >= bet) return alp ;
                   }
               }
           return alp ;
       }
       else {
           for (int i = 1 ; i <= N ; ++ i)
               for (int j = R[i] + 1 ; j <= M ; ++ j){
//                    cout << "B" << " " << dep << ".." << i << " " << j << endl ;
                   if (!base[i][j] && base[i][j - 1] && base[i - 1][j]){
                       base[i][j] = 1 ; R[i] = j ;
                       val = battle(dep + 1, i, j, alp, bet, sa, sb + B[i][j]) ;
                       base[i][j] = 0, bet = min(val, bet) ;
                       R[i] = 0 ; if (alp >= bet) return bet ;
                   }
               }
           return bet ;
       }
}

版本二：败方存活时间最长。参考题目：[CQOI2013]棋盘游戏，可以拿到 $40pts$

这种的话就直接返回 $-1^{\text{胜方}}\times \text{深度}$ 即可，最大化的就是败方存活的最大深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int dfs(int xa, int ya, int xb, int yb, bool w, int step, int alp, int bet){
    if (step > 3 * N) return _d_a_y ;
    if (xa == xb && ya == yb) return w ? -step : step ; int val ;
    if (!w){
        for (int i = 0 ; i < 4 ; ++ i){
            int kx = xa + dx[i], ky = ya + dy[i] ;
            if (kx <= N && ky <= N && kx >= 1 && ky >= 1){
                val = dfs(kx, ky, xb, yb, w ^ 1, step + 1, alp, bet) ;
                alp = max(alp, val) ; if (alp >= bet) return alp ;
            }
        }
        return alp ;
    }
    for (int i = 7 ; i >= 0 ; -- i){
        int kx = xb + dx[i], ky = yb + dy[i] ;
        if (kx <= N && ky <= N && kx >= 1 && ky >= 1){
            val = dfs(xa, ya, kx, ky, w ^ 1, step + 1, alp, bet) ;
            bet = min(val, bet) ; if (bet <= alp) return bet ;
        }
    }
    return bet ;
}

3 两道例题

uva好啊。

$(1$ UVA10111 Find the Winning Move

两人下 $4\times 4$ 的井字棋，给出一个残局，问是否有先手必胜策略。

井字棋：必须要四子连珠才能赢。

这东西只问赢没赢，于是就可以愉快地把局面分数赋为 $1/-1$。搜就完事了233

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

bool check(int x){
    int res ;
    for (int i = 1 ; i <= 4 ; ++ i){
        res = 0 ;
        for (int j = 1 ; j <= 4 ; ++ j)
            res += (bool)(base[i][j] == x) ;
        if (res >= 4) return 1 ; res = 0 ;
        for (int j = 1 ; j <= 4 ; ++ j)
            res += (bool)(base[j][i] == x) ;
        if (res >= 4) return 1 ; res = 0 ;
    }
    for (int i = 1 ; i <= 4 ; ++ i)
        res += (bool)(base[i][i] == x) ;
    if (res >= 4) return 1 ; res = 0 ;
    for (int i = 1 ; i <= 4 ; ++ i)
        res += (bool)(base[i][5 - i] == x) ;
    if (res >= 4) return 1 ; return 0 ;
}
int battle(int step, int alp, int bet){
    int st = (ans - step) & 1, val ;
    if (!st){
        if (check(2) || !step) return -check(2) ;
        for (int i = 1 ; i <= 4 ; ++ i)
            for (int j = 1 ; j <= 4 ; ++ j)
                if (!base[i][j]){
                    base[i][j] = 1 ;
                    val = battle(step - 1, alp, bet) ;
                    base[i][j] = 0 ;
                    if (val > alp){
                        alp = val ;
                        if (step == ans)
                            resx = i - 1, resy = j - 1 ;
                        if (alp >= bet) return alp ;
                    }
                }
        return alp ;
    }
    else{
        if (check(1) || !step) return check(1) ;
        for (int i = 1 ; i <= 4 ; ++ i)
            for (int j = 1 ; j <= 4 ; ++ j)
                if (!base[i][j]){
                    base[i][j] = 2 ;
                    val = battle(step - 1, alp, bet) ;
                    base[i][j] = 0, bet = min(val, bet) ;
                    if (alp >= bet) return bet ;
                }
        return bet ;
    }
}
int main(){
    while (cin >> (s + 1)){
        if (s[1] == '$') return 0 ; ans = 0 ;
        for (int i = 1 ; i <= 4 ; ++ i) scanf("%s", bc[i] + 1) ;
        for (int i = 1 ; i <= 4 ; ++ i)
            for (int j = 1 ; j <= 4 ; ++ j){
                base[i][j] = bc[i][j] == 'x' ? 1
                          : (bc[i][j] == '.' ? 0 : 2) ;
                ans += (!base[i][j]) ;
            }
        if (ans >= 12) { puts("#####") ; continue ;}
        ans = battle(ans, -1, 1) ;
        if (ans > 0) printf("(%d,%d)\n", resx, resy) ;
        else puts("#####") ;
    }
}

$(2$ UVA751 Triangle War

给出 $10$ 个点，共有 $18$ 条边，每次 $A,B$ 两个人轮流加入一条边。A先加。

如果形成一个三角形，则三角形归他所有，而且还必须再走一步。最后三角形多的人胜。

现在已经给出一部分已经完成的步数，由于两位玩家都是最聪明的，他们都会走为自己带来最大优势的步数。你需要判断谁会赢得游戏。

一道憨憨题。发现可以直接状压且每个询问图不变，所以果断打开题解找到思路差不多的把打的表copy过来手推。然后其实就是一开始先把初始状态走完，然后因为一共九个三角形，所以如果一方比另一方多 $5$ 个游戏就结束了，于是发现可以把这个差值当做局面分数，搜就完事了。

还有一个烂大街的 $trick$，按秩转移每条边于是想到 $\rm lowbit$。

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

int Q, T, M, A[N][N], st[2] ;
const int e[11][11]={
    {0,0,0,0,0,0,0,0,0,0,0},{0,0,0,2,0,0,0,0,0,0,0},
    {0,0,0,1,3,5,0,0,0,0,0},{0,2,1,0,0,6,8,0,0,0,0},
    {0,0,3,0,0,4,0,9,11,0,0},{0,0,5,6,4,0,7,0,12,14,0},
    {0,0,0,8,0,7,0,0,0,15,17},{0,0,0,0,9,0,0,0,10,0,0},
    {0,0,0,0,11,12,0,10,0,13,0},{0,0,0,0,0,14,15,0,13,0,16}, {0,0,0,0,0,0,17,0,0,16,0},
} ;
const int t[9] = {7, 56, 98, 448, 3584, 6160, 28672, 49280, 229376} ;
int calc(const int &p, const int &q){
    rg int ret = 0 ;
    for (rg int i = 0 ; i <= 8 ; ++ i)
        if (((p & t[i]) != t[i]) && ((q & t[i]) == t[i])) ++ ret ;
    return ret ;
}
int battle(int n, int s, int alp, int bet){
    if (st[0] >= 5) return 1 ;
    if (st[1] >= 5) return -1 ;
    int O = (1 << 18) - 1, ss ;
    int _rest = s ^ O, now, val ;
    for ( ; _rest ; _rest -= low(_rest)){
        now = calc(s, ss = s | low(_rest)) ;
        if (n)
            st[n] += now,
            val = battle(n ^ (((bool)now) ^ 1), ss, alp, bet),
            bet = min(bet, val), st[n] -= now ;
        else
            st[n] += now,
            val = battle(n ^ (((bool)now) ^ 1), ss, alp, bet),
            alp = max(alp, val), st[n] -= now ;
        if (alp >= bet) break ;
    }
    return n ? bet : alp ;
}

int main(){
    cin >> T, Q = T ;
    while (T --){
        scanf("%d", &M) ;
        st[0] = st[1] = 0 ;
        int _state = 0, n = 0 ;
        for (int x, y, z, i = 1 ; i <= M ; ++ i){
            scanf("%d%d", &x, &y), 
            z = calc(_state, _state | (1 << e[x][y])) ;
            _state |= (1 << e[x][y]), st[n] += z, n ^= (((bool)z) ^ 1) ;
        }
        //cout << _state << " " << n << endl ;
        printf("Game %d: ", Q - T) ;
        if (battle(n, _state, -23333, 23333) >= 0)
            printf("A wins.\n") ; else printf("B wins.\n") ;
    }
    return 0 ;
}

总结

学这个就图一乐。想得高分请记搜/kel。