alpha-beta剪枝算法详解

前言

承接极小化极大算法，它穷举了所有的博弈树节点，从而计算出一条最佳路径，但实际上有些分支是没必要计算的。alpha-beta算法就是对博弈树进行剪枝操作，减少计算开销。但其剪枝效率一定程度取决于走步生成算法，这会在后面进行解释。

alpha-beta剪枝

我们构造一个简单的博弈树，如下图所示：

我们无需知道节点的?到底是多少，就可以排除这条路线，无论它值是多少都不影响我们的结果，为什么？由于MIN层寻找的是值最小的节点，如果?值小于-4，其父节点值更小，如果?值大于-4，那么不会改变其父节点的值，所以其父节点值最多是-4。
无论是哪种情况，根节点（位于MAX层）都不会选择最多值是-4的这条路，因为已经出现了比他更大的兄弟节点。

这就是alpha剪枝，于是就可以理解，为什么剪枝效率一定程度取决于走步生成算法。如果将可能较优的走步生成在前面，那么就很有可能完成高效的剪枝，如下图所示。反之，如果走步生成算法，将较差的走步生成在前面，那剪枝的概率就大大减小，提升不了多少效率。

所以，alpha发生在MIN层。同理，beta剪枝发生MAX层，下图是beta剪枝的一个例子。读者可以自行理解，为什么?的值不会影响结果，当作是一个思考小练习。

我们可以简单地总结一下alpha-beta剪枝，忽略一些具体细节，只概括最精髓的思路，使其更好理解和记忆：（max储存当前最大节点值，min储存当前最小节点值）

• 当处于MAX层时，当子节点值大于max时，更新max，否则不考虑
• 当处于MIN层时，当子节点值小于min时，更新min，否则不考虑

我们引入更形式化的数学表示，使其逻辑更加严谨和具体。用一句话来说就是：一个节点具有上下界，产生越界则抛弃该节点。

我们让 $\alpha$ 表示节点下界，$\beta$ 表示节点上界，每个节点都具有上下界，一个节点最终的值一定在上下界范围内。

节点自底向上更新有以下规则：

• MAX层节点更新其父节点的上界，即 $\beta$ 值
  • 如果当前节点小于父节点的 $\beta$ 值，则更新父节点的 $\beta$ 值
• MIN层节点更新其父节点的下界，即 $\alpha$ 值
  • 如果当前节点大于父节点的 $\alpha$ 值，则更新父节点的 $\alpha$ 值
• 如果节点下界大于其上界，则进行剪枝

最后，我们再梳理一遍算法流程：

• 从根节点开始进行深度优先搜索，并将根节点的上下界传递给子节点
• 触底之后自底向上更新父节点的上下界
• 一旦某节点产生越界，其未遍历的子节点不再考虑
• 最终从根节点选择值最大的那个子节点作为行动策略

一个具体的更新过程如下图所示，根节点初始上下界为$[-\infty, +\infty]$

代码实现

alpha-beta核心代码：

void alphabeta(NodeTree root, int level){
    if(root->child.size() == 0) return;
    for(int i = 0; i < root->child.size(); i++){
        //Deliver alpha and beta
        root->child[i]->alpha = root->alpha;
        root->child[i]->beta = root->beta;

        alphabeta(root->child[i], level + 1);
        if(level % 2 == MIN){
            if(root->child[i]->val < root->beta){
                root->beta = root->child[i]->val;
                root->val = root->beta;
            }
        }else if(level % 2 == MAX){
            if(root->child[i]->val > root->alpha){
                root->alpha = root->child[i]->val;
                root->val = root->alpha;
            }
        }
        if(root->alpha > root->beta){
            return;
        }
    }
}

---