u1s1，评论了为啥不点赞（

淦，别都忙着留名啊，都点进来了为啥不点个赞啊/kel

1 对抗搜索

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

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 剪枝的目的就是在未得到这个点的最优决策时，已经知道该不该继续走。

然后就是伪代码：

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

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

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{深度} 即可，最大化的就是败方存活的最大深度。

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

(2 UVA751 Triangle War

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

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

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

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

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

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 ;
}

总结

还是记搜好。