u1s1，评论了为啥不点赞（
淦，别都忙着留名啊，都点进来了为啥不点个赞啊/kel
# 1 对抗搜索
……然而其实就是搜索。每次大概就是记录一下双方的决策结果和（哈希之后的）局面，然后改谁走谁走就完了。伪代码大概可以这么写：
```cpp
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 剪枝的目的就是在未得到这个点的最优决策时，已经知道该不该继续走。
然后就是伪代码：
```cpp
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$
其实就是修改一下终态的返回值。
```cpp
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{深度}$ 即可，最大化的就是败方存活的最大深度。
```cpp
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$。
```cpp
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 ;
}
```
# 总结
还是记搜好。