秒懂算法 | 围棋中的Alpha-Beta剪枝算法

01、Alpha-Beta剪枝算法

极小化极大算法会遍历所有的可能性，但是根据经验可以知道，并不是所有的选项都需要进行深入的考虑，存在着某些明显不利的选项，当出现这种选项时就可以换一种思路进行考虑了。Alpha-Beta剪枝算法的出现正是为了减少极小化极大算法搜索树的节点数。1997年5月11日，击败加里·卡斯帕罗夫的IBM公司“深蓝”就采用了这种算法。

以井字棋为例，先来看看在下棋的过程中是否有优化空间。参考图1，当前轮到画○方，如果不在虚线圈上落棋，下一步画×方画在虚圈处，游戏就结束了。当发现这类问题时，再去思考其他5个△标注的位置上的落子收益其实是没有意义的，白白浪费了计算资源。

■ 图1 画○方的回合

再来看一个象棋的例子。如图2所示，此时轮到执“帅”的一方走子。将炮横在中路是一种非常具有杀伤力的下法，后续可能可以配合自己的马走出“马后炮”的杀招。但是如果走了这一步，自己的马将会被对方的车立即吃掉，这一损失实在是太大了，所以面对此局面，实战时基本只会考虑如何走马以避免被车吃掉，其他的走子都不会再深入考虑。

■ 图2 执红方的选择

在行棋的过程中，当发现己方会出现极大损失或者极大获利时，仅考虑这些收益显著的情况而忽略掉其他可选项的行为就是剪枝算法的基本思想，而Alpha-Beta剪枝算法就是专门设计用来减少极小化极大算法搜索树节点数的搜索算法。它的基本思想是根据上一层已经得到的当前最优结果，决定目前的搜索是否要继续下去，当算法评估出某策略的后续走法比之前策略的还差时，就会停止计算该策略的后续发展。Alpha-Beta剪枝算法将搜索时间用在“更有希望”的子分支上，继而提升搜索深度，则同样时间内搜索深度平均来说可达极小化极大算法的两倍多。

根据算法介绍可知，如果要使用Alpha-Beta剪枝算法就会额外需要一套局面价值评估系统来决定哪些搜索分支是有希望的，而哪些是没有希望的。所谓局面价值，就是指当前盘面的胜负概率，胜率越高则价值越大，反之则价值越小，甚至是负价值。各种采用Alpha-Beta剪枝算法的人工智能程序之间的实力差距其实就是由于局面价值评估系统的不同所造成的。局面价值评估系统带有很强的主观性，对于如何评估棋局的价值有点像莎士比亚说的，“一千个观众眼中有一千个哈姆雷特”。下面将继续使用井字棋来演示Alpha-Beta剪枝算法。为了省去设计井字棋的价值函数，代码片段1粗暴地认为除了赢和输，其他所有盘面(包括和棋)的价值均为零，赢棋的盘面价值为1，输棋的盘面价值为-1。如果读者想自己在围棋游戏上尝试一下这个算法，最简单的局面评估算法之一就是计算当前双方在棋盘上剩余棋子的差额。不过实战中很少会有棋手主动提取对方已经穷途末路的棋子，所以也许这种评估方法得到的高价值局面反而会带来更加不利的影响。

【代码片段1】得到对弈的评估结果。

MyGo tic - tac - toe ttt.py
def evl game(game) :
if getResult(game.board.board)[1] != None: 
if game.player == getResult(game.board.board) == (0,1)[1]: 
return 1 
else:
return - 1                  
else:
return 0

说明 /
(1) 判断盘面结果，按照约定，对于井字棋，只有当棋局胜负已分时才对盘面价值进行判断，否则盘面价值为零。
(2) 判断当前进行价值评估的棋手是否是棋局的胜利方。
(3) 如果胜利方是当前棋手，则盘面价值为1；如果胜利方是当前棋手的对手，则盘面价值为-1，其他情况的价值按约定默认是0。
引入了对棋局盘面的价值评估表明在使用Alpha-Beta剪枝算法时并不需要执着于搜索时穷尽棋局，即在模拟思考行为时未必非要下到棋局结束时才停止。通常在使用这种算法时会设置一个搜索深度参数来控制算法仿真思考的回合数。从本质上来说，Alpha-Beta剪枝算法是通过价值评估函数来控制算法的搜索广度，用参数设置来控制算法的搜索深度。
同极小化极大算法相比，Alpha-Beta剪枝算法并不是要等到棋局下到结束才给出对局面的评估，每个不同可选项得到的评估结果会由价值评估函数给出不同的数值结果，不尽相同的评估结果(极小化极大算法只有胜、负、和三种评估结果)导致Alpha-Beta剪枝算法在使用过程中需要记录博弈双方在搜索过程中所能取得的最佳价值，可以把双方记录的最佳价值等价地看作是极小化极大算法中的胜利结果。传统上把一方所能搜索到的当前盘面最佳价值叫作Alpha，另一方的最佳价值称为Beta，这种叫法也正是这个算法名称的由来。对于井字棋，将其简记为best_o和best_x。代码片段2演示了Alpha-Beta剪枝算法是如何实现的。

【代码片段2】Alpha-Beta减枝算法的代码框架。

MyGo tic - tac - toe ttt.py
if self.mode == 'ab':
move = self.game.getLegalMoves()
best_moves = []
best_socre = None
best_o = manValue
best_x = minValue
for move in moves:
new game = self.game.simuApplyMove(move)
op_best_outcome = alpha beta prune(new_game, max_depth,best_o, best_x,evl_game)
my best outcome = -1 * op_best outcome
if (not_best_moves) or my_best_outcome > best_score:
best_moves = [move]
best_score = my_best_outcome
if self.game.player == player_x:
best_x = best_score
elif self.game.player == player_o:
best_o = best_score
elif_my_best_outcome == best_score:
best_moves.append(move)
return random.choice(best_moves)

说明 /

(1) 模式ab代表Alpha-Beta剪枝算法。
(2) 获取当前盘面上符合游戏规则的可选项。
(3) 存放最佳的落子选项。
(4) best_score存放当前盘面在搜索过程中得到过的最高选项价值，这个值在搜索过程中会不断地被更高的值所替换。将执○方和执×方的Beta值初始化为最低的价值，并在后面用搜索到的best_score值来更新。
(5) 逐个搜索可选项。
(6) 仿真一下当前选项的落子。
(7) 仿真对手在当前落子下能取得的最佳价值。
(8) 己方能取得的最佳价值是对方能取得的最佳价值的反面。
(9) 只对当前价值高于已有记录的落子步进行处理。
(10) 搜索到了更高的价值，于是需要更新最佳落子。
(11) 更新已有记录的最佳落子价值。
(12) 将最佳价值更新给当前棋盘盘面的实际落子方。
(13) 如果搜索到的价值和记录的最高价值一致，则仅补充最佳落子的可选范围，通过随机抽取高价值落子使得下棋过程中棋局更多变，也更贴近人类行为。
代码片段3-11和代码片段3-8的极小化极大算法在框架上是非常相似的，如果读者仔细思索就会发现，虽然算法的定性描述介绍好像有点玄乎，但是实现上Alpha-Beta剪枝算法和极小化极大算法并没有本质上的区别，仅仅是将胜负结果的判断用一个价值判断函数替代了。既然Alpha-Beta剪枝算法是对极小化极大算法的优化，它也只能通过递归的方式来实现。alpha_beta_prune()函数是整个递归方法的核心，读者可以将极小化极大算法中的bestResultForOP()和这个alpha_beta_prune()比较着来看。代码片段3演示了算法的核心递归方法是如何实现的。

【代码片段3】通过减枝算法查找对方的最优着法。

MyGo\tic-tac-toe\ttt.py
max depth =4
def alpha_beta_prune(game, max_depth,best_o,best_x,evl_fn):
if game.state == GameState.over :
if game.winner == game.player:
return maxValue
elif game.winner == None:
return 0
else:
return minValu
elif max depth == 0:
return evl fn(game)
best so_far = minValue
for move in game.getLegalMoves():
next_game = game.simuApplyMove(move):
op_best_result = alpha_beta_prune(
next_game，max_depth - 1,
best_o，best_x,
evl_fn)
my_result = -1 * op_best_result
if my_result > best_so_far:
best_so_far = my_result
if game.player == plaver_o:
if best_so_far > best_o:
best_o = best_so_far
outcome_for_x = -1 * best_so_far
if outcome_for_x < best_x:
break
elif game.player == player_x:
if best_so_far > best_x:
best_x = best_so_far
outcome_for_o = -1 * best_so_far
if outcome_for_o < best_o:
break
return best_so_far

说明 /
(1) 控制搜索深度。由于人为定义平局和进行中的棋局的价值设置为0，而井字棋一共就9步落子，所以当这个搜索深度设置得比较浅时，算法在开头的几步和随机落子并没有什么区别。如果随机落子法在前3步完成了横竖相连，就可以击败剪枝算法。这也从侧面说明了一个好的价值评估算法对于剪枝算法的重要性。
(2) 由于采用价值评估函数来对胜负的可能性进行评估，这里用一个极大数字或极小数字来表示明确的输赢胜负。
(3) 控制搜索深度，如果到达一定深度游戏还没有结束，就用价值评估函数的值来代替胜负的判断。
(4) 和极小化极大算法一样，初始化当前盘面能取得的最佳价值。
(5) 这几步和bestResultForOP()中的写法是几乎相同的。
(6) 如果结果比之前记录的好则更新最佳价值。极小极大化算法中的最佳价值就是赢棋，所以没有更新最佳价值这一步，而Alpha-Beta剪枝中因为是通过价值评价函数来估计胜负结果的，这个值可能会有很多不同的值，所以可能需要不停地更新最大的值。
(7) 根据当前执棋者是谁，将上一步得到的最佳值更新给不同的对象的最佳值。
(8) 如果当前玩家是画○方，当前搜索值大于画○方记录的最大值，则更新其记录的最大值。下面对画×方的判断后也使用了类似的操作步骤，就不再赘述了。
(9) 一方的最佳进行反操作就是另一方的最差。
(10) 如果当前的一方最佳操作可以使得对方的最佳降低，那么就可以认为找到了一步必胜棋，并退出，当然也可以继续搜索不退出，但是由于已经找到了，再多找几个意义不大，反而浪费了计算资源，这个在bestResultForOP()中也有相似的对应操作。
(11) 返回当前玩家所能取得的最佳结果。
搜索选项时算法会根据棋盘局面上的可落子顺序进行搜索。如果碰巧在一开始就找到了一个最好的选项，在搜索其他后续选项时会由于剩下的选项收益较低而被迅速地剪枝掉，如果运气不好，最好的选项在最后才被搜索到，那么Alpha-Beta剪枝算法的速度并不会比极小化极大算法快。但是数学期望上，Alpha-Beta剪枝算法的消耗时间会是极小化极大算法的一半。如果在搜索开始前引入一些启发性的算法先从最有潜质的着法开始搜索，也许可以缓解算法对着法寻找顺序的依赖并使得算法能有很大的改进。