alpha-beta 剪枝

上一篇文章的最后提到，当minimax算法的搜索深度增加时，其计算复杂度会急剧上升。如果有办法去掉一些分支，算法的效率会更高，而且会轮到-剪枝。但是我们先不讨论算法。让我们先玩上一篇文章中的游戏。

上一篇文章只是粗略地介绍了如何玩这个游戏。在这里，让我们一步步来。

有两个包。第一个包里，有一个小米9和一个华为p30。在第二个袋子里，有一个螺丝钉、一颗芝麻和一个苹果Pro。但是你和你的朋友都不知道袋子里是什么。游戏规则是你选一个包，你的朋友给你选一个物品，你想得到最有价值的物品，而你的朋友却想尽办法阻止你(这样的朋友还是早点抛弃比较好)。如果两个人都盲目选择就没意思了，所以你和朋友们讨论一下，大家可以尽量多尝试几次再做最后的选择。游戏开始：

你：选包一。

朋友：从包里拿出第一件，发现是华为p30。临时决定：如果你选包一，我给你华为p30。放回去。

朋友：从包里拿出第二件，发现是小米9。和华为p30对比后，暂时决定，如果你选择Bag One，我给你小米9。放回去。

朋友：我在包里没有发现其他东西。最后决定：如果你选择了包一，我就给你小米9。

你：记录一下，可用的物品暂时是小米9。

你：选二号包。

朋友：从包里拿出第一件东西，发现是螺丝。和暂时可以买到的物品小米9对比后，你的朋友决定直接告诉你：如果你选择Bag 2，我会给你一个螺丝。为什么我们可以在这里省略对比包2中的其他项目？为什么一颗芝麻价值更低？因为包二中第一件物品的价值已经小于你可以暂时获得的物品价值，这个信息足够让你放弃选择包二。

经过这些尝试，你最终选择了包一，然后你的朋友给了你小米9。

上面的过程其实就是max-min算法加上alpha-beta剪枝。在选择第二个包包时，你的朋友试图放弃包包中的其他物品，这反映了alpha-beta修剪的想法。我们来谈谈-修剪。

在-修剪算法中，我们定义：

alpha记录是最高级别中节点当前可用的最高分数，beta记录是最低级别中节点当前可用的最低分数。当最小级别的一个节点的beta小于alpha时，可以停止该节点的其他子节点的搜索。当最大级别中某个节点的alpha大于beta时，可以停止搜索该节点的其他子节点。

这个我肯定看不懂，下面就用下面的例子进行实战吧。

将根节点alpha初始化为-，beta初始化为，然后通过路径一直传递到倒数第二行左边的节点。

遍历第一个子节点，将alpha更新为4，并将当前节点更新为4。确定是否需要剪枝(比较当前节点的alpha和beta，发现4小于，所以不允许剪枝)。

遍历第二子节点，将alpha更新为6，并将当前节点更新为6。确定是否需要剪枝(比较当前节点的alpha和beta，发现6小于，所以不允许剪枝)。

6返回上一级，最小级别左边第一个节点的beta更新为6，当前节点值更新为6。确定是否需要修剪(比较当前节点的beta和alpha，发现6大于-，所以不允许修剪)。

将alpha=-，beta=6传递给右边的子节点，继续遍历7所在的节点，将alpha更新为7，将值更新为7。确定是否需要修剪(比较当前节点的beta和alpha，发现6小于7，满足修剪条件。

//p6.toutiaoimg.com/origin/pgc-image/bfd255da9d09433f8f7609233b6bbab9?from=pc">

返回 7 到上一层，无需更新。

接下来就不一一赘述了，读者可以自己试试把剩下的完成，最后的结果是这样的：

结合代码看可以更好的理解：

function alphabeta(node, depth, α, β, maximizingPlayer) is if depth = 0 or node is a terminal node then return the heuristic value of node if maximizingPlayer then value := −∞ for each child of node do value := max(value, alphabeta(child, depth − 1, α, β, FALSE)) α := max(α, value) if α ≥ β then break (* β cut-off *) return value else value := +∞ for each child of node do value := min(value, alphabeta(child, depth − 1, α, β, TRUE)) β := min(β, value) if α ≥ β then break (* α cut-off *) return value 复制代码

这就是 alpha-beta 剪枝的规则，别看只是减去了几个分支不计算而已，如果每层每个节点都可以排除掉几个分支的话，对速度的优化还是非常明显的。

并行搜索

另外一个优化的思路是并行计算，把每次产生的走法平均分成多个任务并行处理，每个并行的任务分别产生局部的最优解，最后汇总得到全局的最优解即可。每一个走法对应一个子任务是最快的，不过如果每一层都这样的话，最后的子任务数量也会非常巨大，不管是多进程还是多线程实现都是很不现实的，所以需要限制并行处理的深度。即便仅在第一层开启并行计算，理论上也可以使得计算速度快 30 倍（假设每一层平均产生 30 种走法）。

总结

利用最大最小值和 alpha-beta 算法就可以实现简单的象棋 AI 程序，不过该 AI 的棋力仅够应付入门级的玩家。一个原因是尽管采取了前面所说的优化方法后，实践发现当搜索深度达到 5 以后，算法的计算时间就慢得不能接受了，无法继续提高搜索的深度；另外一个原因是局势判断的方法略显简单，可以考虑加入一些象棋特有的“套路”来提高局势判断的准确性。后面针对这些问题再优化一下。

参考

Alpha–beta pruning

象棋ai算法(泓弈网页象棋)

alpha-beta 剪枝

并行搜索

总结

参考