极大极小搜索以及alphabeta剪枝优化

缘起

在棋类等博弈游戏中, 极大极小搜索是常用的博弈搜索算法. 比如：围棋，五子棋，象棋等。 遂来学习之. 本文是吸收了【1】的营养写下的。

分析

我们来看看国际象棋游戏. 假设白方先走. 则其实下棋的过程就是一棵巨大的状态树（据说国际象棋平均每一步大约有35种可行走法）. 计算机的算力基本不可能对于每个局面遍历该局面对应子树的所有根节点. 所以一般的AI下棋程序的深搜的深度都是有限的（也就是江湖上说的——仅仅算几步棋）. 后来，因为蒙特卡洛算法等随机算法的涌现, 使得AI下棋程序可以大大加深深搜的深度，这是后话了.

对于每个局面, 我们都可以站在白方的角度上来评估当前局面——如果对白方越有利, 则局面的得分越高. 反之, 得分越低（反过来理解就是对黑方越有利）. 例如, 如果当前局面轮到白方走，而且只需要一步就能将黑方将死, 则得分是inf, 反之如果当前局面是黑方走, 黑方只需要一步就能将白方将死, 则当前局面的得分是 -inf.

所以我们就明白了——所谓下棋, 就是白方（确切讲, 是先行方）拼死想提高当前局面的得分，而黑方（确切讲，是后行方）拼死想降低当前局面的得分 的一个过程.

至于当前局面的评分，或者说估价函数，对于不同的游戏（甚至对于同一个游戏）都是不同的，是仁者见仁智者见智的事情, 我们不去过度的评论. 只需要符合直觉（确切讲是具备启发性）就行.

那么，什么叫做每位棋手都按照对自己最有利的方式去行事呢? 就是这样. 白方不是先行吗?假设白方走这一步棋之前的局面是R, 白方可行的所有走法我们可以遍历出来. 令 N是白方所有走法的集合. 则每个N中的元素都是R的子节点. 则对于每个 $n\in N$, 黑方就要在n的基础上走一步. 令 f(n) 是黑方在n的基础上能将评分降到的最小值（事实上，因为黑方也是一位理智的棋手, 所以黑方也会这么做的）. 则令 F(n0) = max{f(n) | $n\in N$ }, 即n0是黑方能搞差的最大值 . 那作为一名理智的棋手, 白方显然会选择n0作为此步的走法（因为白方的目的是想搞大棋局的评分）.

然后黑方在n0的基础上走下一步. 和分析白方的走法一样, 显然首先将黑方可行的走法遍历出来, 令 Q 是黑方所有可行走法的集合, 则对每个 $q\in Q$ ， 令 F(q) 是白方在q的基础上能搞出的棋局最大评分值（因为黑方的目的是提高棋局评分）. 令 F(q0)=min{F(q) | $q\in Q$ }, 则作为一名理智的棋手, 黑方显然应该选择q0作为它的走法——因为黑方的目的不就是想搞低局面评分吗? 所以当然要选取最小值.

上面的博弈过程四不四给我们一种——树的节点一层是求子节点最大, 一层是求子节点最小, 然后下一层又是求子节点最大, 再下一层又是求子节点最小…. 这样的树~ 没错, 如果假设博弈双方都是理智棋手（再强调一次, 所谓理智棋手, 就是在固定的搜索深度上, 只选取对自己最有利的走法）的话, 则整个棋局的搜索树长下面的样子

​ 图1

第一层是求极大节点, 第二层是求极小节点, 第三层又是求极大节点. 当然, 上面的搜索树展示的是搜索深度固定为3.

所以我们就明白了为什么这种博弈叫做 极大极小搜索（树）

先行方（上面的例子是白方）想搞大局面评分，而后行方（上面的例子是黑方）想搞小局面评分.

纵观上面的博弈过程, 我们意识到, 对于当前走棋的人, 最重要的是能立刻知道当前局面在固定搜索深度（下同, 不再说了）下的评分（它必定是子节点的极大或者极小, 所以我们在求出评分的过程中可以顺便维护一下取得这个评分的走法, 它其实就是当前走棋的人的走法）. 那么利用我们在树上dfs方面的造诣. 不难写下如下极大极小搜索的代码

int MinMax(int depth, int state) {  // state是当前状态
　if (SideToMove() == WHITE) {　// 白方走棋 （即极大节点）,获取局面最大评分, 这个评分是站在白方角度看的
　　return Max(depth,state); 
　} else {　　　　　　　　　　　// 黑方走棋 （即极小节点）,获取局面最小评分（注意, 这个最小评分依旧是站在极大方, 也就是白方来看的）,如果要算黑方的最大得分, 其实就是这个局面最小得分的相反数.
　　return Min(depth,state); 
　} 
} 　 

int Max(int depth, int state) {  // 白方调用,即极大节点调用
　if (depth <= 0 || gameover) {  // 递归出口, 即搜索深度到了或者游戏结束, 就不再去搜索了
　　return Evaluate(state);  // 返回局面评分,对于游戏尚未结束仅仅是因为到了搜索深度而停止搜索, 则Evaluate是启发式的, 对于终局, 是精确的评分
　} 
　int ans = -inf;  // 因为当前节点state是是求最大的节点
　while (int nxtState = MovesLeft()) {  // 遍历产生所有下一步的合法状态nxtState
　　MakeNextMove();  // 走棋
　　val = Min(depth - 1,nxtState);  // 黑方能最差搞成什么评分
　　UnmakeMove();   // 因为是搜索, 所以要undo
　　ans = max{ans, val}; // 最大节点求最大
　} 
　return ans; 
} 　 
int Min(int depth, int state) {  // 黑方调用,即极小节点调用
　if (depth <= 0 || gamerover) { 
　　return Evaluate(state); 
　}  
　int ans = inf;　// 注意这里不同于Max函数
　while (int nxtState = MovesLeft()) { 
　　MakeNextMove(); 
　　val = Max(depth - 1,nxtState); 
　　UnmakeMove(); 
　　ans = min{ans, val}; // 注意这里不同于Max函数
　} 
　return ans; 
}
调用方法:
int val = MinMax(5, state);
这样可以返回对当前局面state的评价，它是算5步棋的结果。

但是上面的算法有一个致命的缺陷——并没有降低树的大小——即状态树的空间还是太大太大了（导致算法的可行性依旧不是很高）~ 降低dfs的复杂度我们靠什么?

无他, 唯剪枝尔

所以alphabeta剪枝横空出世~ alphabeta剪枝就是为了降低极大极小搜索算法复杂度而诞生的技巧.

alphabeta剪枝其实是alpha剪枝+beta剪枝的复合体. 我们先来看alpha剪枝. 还是上面那张图

​ 图2

回顾一下, 第一层是求极大的节点, 第二层是求极小的节点, 第三层是求极大的节点. 那么一旦我们求到了绿2节点的第一个子节点（即蓝2节点）的评分是2这个答案之后, 我们还需要求A~B的评分吗? 显然不用! 因为绿2节点是求极小, 所以绿2节点最终的评分不可能超过蓝2节点的评分2, 而绿7节点先于绿2节点的搜索, 绿7节点的评分7已经导致了求极大的红7节点的评分变成7了, 那A~B节点的评分无论是什么都不可能改变绿2节点的评分<=2<绿7节点的评分7<=红7节点的评分. 所以A~B节点我们可以不需要考察了. 即求极大的节点A~B被剪掉了. 可能是剪掉的是求极大的节点吧, 所以叫做alpha剪枝. 所谓的alpha就是求极大的节点.

理解了alpha剪枝, 那么beta剪枝就完全类似了——就是剪掉求极小节点.

​ 图3

上图求极小的节点A~B 就应该被剪掉, 因为极大层的偏右的节点的评分一定 >=5>偏左的极大层节点的评分2.

理解了极大极小搜索中的alphabeta剪枝, 我们来看看alphabeta优化的极大极小搜索的代码该怎么写. 注意, 不建议使用wiki上的alphabeta合并在一起写的代码（即【1】中最后给的伪代码,我吃了那个伪代码的大亏）. 比较乱~ 而且不利于后面和记忆化搜索结合进行优化. 而且和上面图2和图3展示的剪枝不一样. 可以讲是十分混乱的代码

写法其实就是在上面极大极小加入alphabeta剪枝（下简称ab剪枝）

int MinMax(int depth, int state, int alpha, int beta) {
　if (SideToMove() == WHITE) {
　　return Max(depth,state, alpha); 
　} else {
　　return Min(depth,state, beta); 
　} 
} 　 

int Max(int depth, int state, int alpha) { // 入参alpha是当前节点state的父节点(一个求极小的节点)的精确评分或者上界,函数返回当前节点state(求极大的节点)的精确评分或者评分的下界.
　if (depth <= 0 || gameover) {
　　return Evaluate(state); 
　} 
　int ans = -inf; // 因为当前节点state是求极大的子节点
　while (int nxtState = MovesLeft()) { 
　　MakeNextMove(); 
　　val = Min(depth - 1,nxtState, ans); // ans作为state的求极小的子节点的父节点的精确评分或者下界传入 
　　UnmakeMove();  
　　ans = max{ans,val}  // 最大节点求最大
　　if(ans>=alpha) { // 如果最大节点求最大的过程中超出了父节点的精确评分(或者其上界),则因为父节点是求最小的节点, 当前节点后面的子节点(用于继续参与max的当前节点的极小子节点)就不用求了, 即剪掉了极小子节点, 是beta剪枝, 即图3的情形,当前节点state对应的是图3中间层的绿色节点,剪掉的是图3底层的黄色节点
　　	return ans;
　　}
　} 
　return ans; 
} 　 
int Min(int depth, int state, int beta) {  // 入参beta是当前节点state的父节点(一个求极大的节点)的精确评分或者下界,函数返回当前节点state(求极小的节点)的精确评分或者评分的上界.
　if (depth <= 0 || gamerover) { 
　　return Evaluate(state); 
　}  
　int ans = inf; // 因为当前节点是求极小的节点
　while (int nxtState = MovesLeft()) { 
　　MakeNextMove(); 
　　val = Max(depth - 1,nxtState, ans);  // ans作为state的求极大的子节点的父节点的精确评分或者上界传入 
　　UnmakeMove(); 
　　ans = min{ans, val}; // 最小节点求最小
　　if(ans<=beta) { // 如果最小节点求最小的过程中不及父节点的精确评分(或者其下界),则因为父节点是求最大的节点, 当前节点后面的子节点(用于继续参与min的当前节点的极大子节点)就不用求了, 即剪掉了极大子节点, 是alpha剪枝,即图2的情形,当前节点state对应的是图2中间层的黄色节点,剪掉的是图2底层的蓝色节点.
　　	return ans;
　　}
　} 
　return ans; 
}
调用方法:
int val = MinMax(5, state, +inf, -inf);
这样可以返回对当前局面state的评价，它是算5步棋的结果。

关于上面的伪代码, 想说4点

1. 关于传入的alpha、beta初始值. 一般不要传alpha=inf, beta=-inf , 而是尽量传精确的上下界. 例如白方胜就是1, 黑方胜就是-1, 平局就是0（注意, 1,-1,0都是站在白方的评分角度来看的~ 黑方胜, 站在白方的角度来看, 白方得分就是-1分）, 则比较好的传入的alpha就是1， beta是-1, 不然的话, 注意代码的第19行和第35行. 如果真的运气足够好, 例如函数刚进去（即递归的最表层）第19行求出的ans就是1, 则就可以立马剪枝返回答案是1了~ 但是因为alpha=inf导致不能直接返回了~ 不是说-inf、inf不行，-inf、inf并不会造成算法错误, 而是会造成多余的搜索而已（即必须遍历完所有的子节点）.

2. 什么时候函数返回的是精确的值, 什么时候返回的是极大（小）节点评分的下(上)界?

   答: 如果发生剪枝的话, 返回的就不是精确评分而是下(上)界, 反之，如果没有发生剪枝, 而是老老实实遍历了所有节点得到的结果, 那么返回的就是精确值. 这不难理解吧? 如果老老实实求完了当然是精确值咯~ 如果因为剪枝提前结束了求解, 那自然不是精确值咯~ 求min的提前结束了（极小节点的Min方法）, 返回的自然是个上界估计, 求max的提前结束了（极大节点的Max方法）, 返回的自然是个下界估计咯~ 但是注意, 对于根节点而言, 传入的alpha、beta已是极值, 所以根节点返回的一定是精确值.

3. 当然, 实际做题的时候, 一般是不会设置深度的（即没有depth入参）, 因为你设置了深度的话, 求的就是近似最优解而非最优解. 所以一般题目也不会设置太深的深度. 因为不设置搜索深度, 都是一搜到底的（即搜到终局为止）, 所以局面的评估函数不需要启发式, 就是精确的评估即可.

4. 上面的Min、Max方法的入参未必仅仅有上述的入参, 可以根据题目需要加一些入参, 例如为了便于终局评分的入参.

关于上面的第二点, 我们其实就可以使用记忆化打表来加速极大极小搜索~ 即我们可以这个样子

int MinMax(int depth, int state) {
　if (SideToMove() == WHITE) {　
　　return Max(depth,state); 
　} else {　
　　return Min(depth,state); 
　} 
} 　 
int dp[all state] // 记忆化打表, 伊始全部初始化为-inf 这种非法值
int Max(int depth, int state) {
  if(dp[state]!=-inf) {
  	return dp[state] // 记忆化加速搜索
  }
　if (depth <= 0 || gameover) {  
　　return dp[state] =  Evaluate(state); 
　} 
　int ans = -inf; 
　while (int nxtState = MovesLeft()) { 
　　MakeNextMove();  
　　val = Min(depth - 1,nxtState);
　　UnmakeMove(); 
　　ans = max{ans, val};
　} 
　return dp[state] = ans; 
} 　 

int Min(int depth, int state) { 
　if(dp[state]!=-inf) {
  	return dp[state] // 记忆化加速搜索
  }
　if (depth <= 0 || gamerover) { 
　　return dp[state] = Evaluate(state); 
　}  
　int ans = inf;
　while (int nxtState = MovesLeft()) { 
　　MakeNextMove(); 
　　val = Max(depth - 1,nxtState); 
　　UnmakeMove(); 
　　ans = min{ans, val};
　} 
　return dp[state] = ans; 
}
调用方法:
int val = MinMax(5, state);
这样可以返回对当前局面state的评价，它是算5步棋的结果。

上述伪代码没有一点问题~ 是正确的. 于是我们就好奇, 能不能更进一步, 把ab剪枝也弄进去, 使得我们的极大极小搜索快到极值呢? 很遗憾, 记忆化不能和ab剪枝联用. 也就是下面的伪代码是错误的

int MinMax(int depth, int state, int alpha, int beta) {
　if (SideToMove() == WHITE) {
　　return Max(depth,state, alpha); 
　} else {
　　return Min(depth,state, beta); 
　} 
} 　 
int dp[all state]
int Max(int depth, int state, int alpha) {
  if(dp[state]!=-inf) {
  	return dp[state]
  }
　if (depth <= 0 || gameover) {
　　return dp[state] = Evaluate(state); 
　} 
　int ans = -inf; 
　while (int nxtState = MovesLeft()) { 
　　MakeNextMove(); 
　　val = Min(depth - 1,nxtState, ans);
　　UnmakeMove();  
　　ans = max{ans,val} 
　　if(ans>=alpha) {
　　	return dp[state] = ans;    // 错在这里!!! ab剪枝不能和记忆化联合使用
　　}
　} 
　return dp[state] = ans; 
} 　 
int Min(int depth, int state, int beta) { 
  if(dp[state]!=-inf) {
  	return dp[state]
  }
　if (depth <= 0 || gamerover) { 
　　return dp[state] = Evaluate(state); 
　}  
　int ans = inf; 
　while (int nxtState = MovesLeft()) { 
　　MakeNextMove(); 
　　val = Max(depth - 1,nxtState, ans); 
　　UnmakeMove(); 
　　ans = min{ans, val};
　　if(ans<=beta) {
　　	return dp[state] = ans; // 错在这里!!! ab剪枝不能和记忆化联合使用
　　}
　} 
　return dp[state] = ans; 
}
调用方法:
int val = MinMax(5, state, +inf, -inf);
这样可以返回对当前局面state的评价，它是算5步棋的结果。

为什么记忆化不能和ab剪枝联合使用呢? 因为上面第二点已经讲到原因了——对于剪枝的情况, 返回的仅仅是个上下界而非精确评分, 但是在博弈树中, 一个状态P未必只有一个前驱!!! 如果一个前驱到P发生了剪枝尔返回的是P的一个界估计而被记忆化了的话, 另一个前驱到P如果要用的不是P的估计而要用的是P的精确值的话, 但是已经被记忆化了, 则就拿来直接用岂不是错误了?

所以正确的记忆化+ab剪枝+极大极小搜索的伪代码如下

int MinMax(int depth, int state, int alpha, int beta) {
　if (SideToMove() == WHITE) {
　　return Max(depth,state, alpha); 
　} else {
　　return Min(depth,state, beta); 
　} 
} 　 
int dp[all state]
int Max(int depth, int state, int alpha) {
  if(dp[state]!=-inf) {
  	return dp[state]
  }
　if (depth <= 0 || gameover) {
　　return dp[state] = Evaluate(state); 
　} 
　int ans = -inf; 
　while (int nxtState = MovesLeft()) { 
　　MakeNextMove(); 
　　val = Min(depth - 1,nxtState, ans);
　　UnmakeMove();  
　　ans = max{ans,val} 
　　if(ans>=alpha) {
　　	return ans;    // ab剪枝不能和记忆化联合使用,因此仅仅单纯的返回而没有记忆
　　}
　} 
　return dp[state] = ans; 
} 　 
int Min(int depth, int state, int beta) { 
  if(dp[state]!=-inf) {
  	return dp[state]
  }
　if (depth <= 0 || gamerover) { 
　　return dp[state] = Evaluate(state); 
　}  
　int ans = inf; 
　while (int nxtState = MovesLeft()) { 
　　MakeNextMove(); 
　　val = Max(depth - 1,nxtState, ans); 
　　UnmakeMove(); 
　　ans = min{ans, val};
　　if(ans<=beta) {
　　	return ans; // ab剪枝不能和记忆化联合使用,因此仅仅单纯的返回而没有记忆
　　}
　} 
　return dp[state] = ans; 
}
调用方法:
int val = MinMax(5, state, +inf, -inf);
这样可以返回对当前局面state的评价，它是算5步棋的结果。

据网友说, alphabeta剪枝可以有效的将平均35种走法降低到6种, 可见alphabeta剪枝对于极大极小搜索的优化程度有多么的巨大~

参考

【1】https://www.cnblogs.com/pangxiaodong/archive/2011/05/26/2058864.html