Alpha-beta剪枝是一种搜索算法,用以减少极小化极大算法(Minimax算法)搜索树的节点数。这是一种对抗性搜索算法,主要应用于机器游玩的二人游戏(如井字棋象棋围棋)。当算法评估出某策略的后续走法比之前策略的还差时,就会停止计算该策略的后续发展。

这是维基百科中对Alpha-Beta剪枝的介绍。事实上,这种算法是一种启发式搜索。启发式搜索在状态空间里进行搜索时会对当前局面进行评估,从算法中认为可以接受的局面开始进行搜索。

Alpha-Beta剪枝是对Minimax算法的一种优化,而后者是一种博弈算法,常用于井字棋等游戏。Minimax算法的核心在于让对手极小,自己极大,简单来理解就是对于一个回合制博弈,让己方博弈局面评估取极大,而敌方取极小。

以下方博弈树为例:

tree.png

可以看到,这棵博弈树每个节点代表了一种局面,其中的值为估价函数所计算出的当前局面的评估值。如果我们想要在这一场博弈中取胜,要做的就是在自己的回合的评估值大于敌方的评估值。

从根节点开始进行k步的深度优先搜索,并在叶子节点处对局面进行评估,回溯时在每个敌方节点取极小,在自己的节点取最大,以达到当前最佳决策。

minimax.png

PS:这不是上面那颗决策树

那么Alpha-Beta剪枝是个什么东西呢?

Alpha($\alpha$)代表下界,Beta($\beta$)代表上界,它们的初始值分别为$-\infty$和$\infty$,对于Min节点,我们可以修改$\beta$值,而对于Max节点,我们可以修改$\alpha$值。当出现$\beta\leq\alpha$时,那么搜索这个节点的子树将毫无意义,此时我们应剪枝,以减少无意义的搜索

首先,我们知道在深度优先搜索时,节点访问顺序是遵从树的dfs序的。

假设当前节点A需要行Max决策(也就是自己的回合),我们希望下一节点的评估值尽可能大。假设在dfs序中我们已经搜索的子树(行Min决策)评估值为最小3,我们就可以确定A节点的下界$\alpha$。我们希望让A节点尽可能大,超过3以影响到$\alpha$,所以这个下界被传递到了下一层子树,对于下一层子树维护$\beta$值,若达到边界条件,则剪枝。

alpha-beta.jpeg

PS:棕色表剪枝

由此我们完成了Alpha-Beta剪枝优化。


参考资料:

Last modification:November 13, 2019
博客维护不易,如果你觉得我的文章有用,请随意赞赏