Alpha–Beta 剪枝 · aiwiki.page

Alpha–Beta 剪枝是一种算法，用于减少极小化极大算法搜索所需的工作量。一旦已有信息表明博弈树中的某些分支无法改善相应的决策，它就不再探索这些分支。对于给定的树和叶节点评估值，该算法保持根节点的极小化极大值不变，同时可能大幅减少需要考察的局面数量。它是人工智能中用于对抗性博弈的标准技术。(cs.cornell.edu)

极小化极大算法的应用背景

标准应用场景是具有完全信息的确定性双人零和博弈。分值统一从其中一名玩家的角度表示：MAX 选择值最高的后续走法，MIN 则选择值最低的后续走法。极小化极大算法从叶节点局面开始，将这些选择的结果逐层向上传递，从而确定根节点的值。(aima.cs.berkeley.edu)

搜索可以一直进行到终局，此时分值表示博弈结果；也可以在达到深度限制时停止。在后一种情况下，使用启发式评估函数估计非终局局面的值。Alpha–Beta 剪枝保持这种深度受限的极小化极大计算结果不变，但不会使估计值变得精确，也不能据此确定整个博弈的最优策略。(cs.cornell.edu)

界限与剪枝

算法沿当前搜索路径维护两个界限：

**Alpha（(\alpha)）**记录迄今为止已确定的 MAX 最佳备选方案的值，即最高值。
**Beta（(\beta)）**记录迄今为止已确定的 MIN 最佳备选方案的值，即最低值。

初始时，(\alpha=-\infty)，(\beta=+\infty)。在 MAX 节点，新发现的值可能增大 alpha；在 MIN 节点，新发现的值可能减小 beta。当 (\alpha\geq\beta) 时，可以跳过剩余子节点：某个祖先节点已经有一个备选方案，其效果至少不逊于当前后续走法所能提供的任何结果。(aima.cs.berkeley.edu)

例如，假设 MAX 已经找到一个值为 5 的走法。另一个走法通向一个 MIN 节点，而该节点第一个被考察的子节点值为 3。无论其余子节点的值如何，这个 MIN 节点的值都不会大于 3。因此，MAX 不可能通过这个走法获得比 5 更好的结果，也就无需考察那些剩余子节点。这个例子说明，剪枝不需要确定被舍弃节点的精确值。(cs.cornell.edu)

算法

深度受限的实现可以使用递归，交替处理 MAX 和 MIN。以下伪代码假定每个非终局节点都有合法的后继节点，并且所有评估都以 MAX 的视角进行。(cs.cmu.edu)

alpha_beta(node, depth, alpha, beta, maximizing):
    if terminal(node):
        return utility(node)
    if depth == 0:
        return evaluate(node)

    if maximizing:
        value = -infinity
        for child in successors(node):
            score = alpha_beta(child, depth - 1,
                               alpha, beta, false)
            value = max(value, score)
            alpha = max(alpha, value)
            if alpha >= beta:
                break
    else:
        value = +infinity
        for child in successors(node):
            score = alpha_beta(child, depth - 1,
                               alpha, beta, true)
            value = min(value, score)
            beta = min(beta, value)
            if alpha >= beta:
                break

    return value

初始调用使用不受限制的窗口 ((-\infty,+\infty))。采用更窄窗口的调用可能只能确定一个界限，而非精确值。因此，发生剪枝时返回的结果不能直接视为该内部节点的真实极小化极大值。(webdocs.cs.ualberta.ca)

复杂度与走法排序

时间复杂度很大程度上取决于后继节点的搜索顺序。对于分支因子为 (b)、深度为 (d) 的均匀树，最坏情况下的复杂度仍为 (O(b^d))：节点值的排列可能使搜索无法进行任何有效剪枝。在最优排序下，需要评估的叶节点数量为

[ b^{\lceil d/2\rceil}+b^{\lfloor d/2\rfloor}-1. ]

当深度为偶数时，该数量为 (2b^{d/2}-1)，通常用大O记号概括为 (O(b^{d/2}))。上述精确表达式也体现了奇数深度与偶数深度之间的差异。(webdocs.cs.ualberta.ca)

良好的排序会优先考察有希望的走法，即 MAX 的高值走法和 MIN 的低值走法，以便更早获得有用的界限。在排序有利的情况下，Alpha–Beta 剪枝可以在工作量相近的条件下，达到普通极小化极大算法约两倍的搜索深度；但这并不是最坏情况下的保证。(aima.cs.berkeley.edu)

历史分析

唐纳德·E. 高德纳和罗纳德·W. 摩尔于 1975 年发表的论文《Alpha–Beta 剪枝分析》（An Analysis of Alpha-Beta Pruning）介绍了这一算法，证明了其正确性，讨论了其历史发展，并在关于博弈树节点值的若干假设下分析了算法的行为。(sciencedirect.com)

参考来源

Minimax search and alpha-beta pruningcs.cornell.edu
Chapter 6: Adversarial Searchaima.cs.berkeley.edu
Alpha-beta searchcs.cmu.edu
An Analysis of Alpha-Beta Pruningwebdocs.cs.ualberta.ca