假设您已经搜索了完整搜索树的一部分，例如完整的左半部分。这可能还没有为您提供根节点的真正博弈论值，但它已经可以为您在根节点中玩的玩家（假设是最大玩家）可以保证的博弈论值提供一些界限通过移动到搜索树的那一部分。这些界限/保证是：

• $\alpha$：最大化玩家已经知道的最小分数，如果我们移动到到目前为止搜索到的搜索树部分，它可以保证。也许它仍然可以通过进入未搜索部分做得更好（获得更高的值），但它肯定已经可以得到这个值。
• $\beta$：最小化玩家已经知道的最大分数，如果我们移动到到目前为止搜索到的搜索树部分，它可以保证。也许它仍然可以通过移动到未搜索的部分来做得更好（获得更低的值），但它肯定已经可以得到这个值。

alpha-beta 修剪背后的直观想法是修剪搜索树中对任一玩家都不感兴趣的块，因为他们已经知道他们可以根据$\alpha$或者$\beta$界限。

---

举个简单的例子，假设$\alpha = 1$，这意味着最大化玩家已经探索了搜索树的一部分，因此它可以保证至少一个值$1$通过在该部分内播放（最小化玩家在整个树内没有选项来减少下面的值$1$，如果最大化玩家在该部分发挥最佳）。

假设在当前的搜索过程中，我们已经到达了一个最小化玩家要玩的节点，并且它有一个很长的子节点列表。我们评估这些孩子中的第一个，并找到一个值$0$. 这意味着，在我们到达这个节点的假设下，最小化玩家已经可以保证$0$（可能会更低，我们还没有评估其他孩子）。但这比（对于最大化玩家）更糟糕$\alpha = 1$绑定我们已经有了。在不评估任何其他孩子的情况下，我们已经可以看出搜索树的这一部分是无趣的，最大化玩家将确保我们永远不会在这里结束，因此我们可以修剪剩余的孩子（每个孩子都可能有大子树在他们下面）。

极小极大

正如问题作者可能已经理解的那样，极小极大在成为算法之前是一种方法。目标是最小化挑战者的优势并最大化当前应用极小极大方法的参与者的优势。这是将收益相加并减去成本总和以得出净值的更广泛策略的子集。

Alpha-beta 修剪

alpha beta 剪枝的战略目标是用更少的工作做出不妥协的决策。这个目标通常是由计算资源的成本、等待结果的人的不耐烦或错过最后期限的惩罚所驱动的。

所涉及的原则是，如果在搜索中遍历任何子树，可以聚合的净增益的范围有限。可以使用不等式代数证明，如果子树在任何条件下都不能显示出比其他选项具有任何净优势，则不会在搜索中丢失任何知识。

一些图论来阐明剪枝

顶点是通常称为树节点的图论名称。它们表示为$\nu$下面，它们对应于状态。顶点之间的连接在图论中称为边。它们表示为$\epsilon$下面，它们对应于动作。

到目前为止，在一个顶点处累积的最小最大净增益可以在遍历树时计算出来。

由于在更深的深度对净增益的限制应用于这些中间净增益值，因此可以推断出一个边缘（动作）在任何情况下都将优于另一边缘。如果一种算法揭示了一条边在所有可能的情况下都会导致劣势，那么就不需要遍历该边。这种对从不有利的边缘的消除节省了计算资源，并可能减少了搜索时间。使用修剪一词是因为边缘就像果园中的树枝。

剪枝条件及实现算法

算法的初始化首先将两个希腊字母变量设置为其最坏情况值。

$$\alpha = - \infty \\ \beta = \infty$$

边缘的修剪规则$\epsilon$通向顶点$\nu$就是这个。

$$\alpha_\nu \geq \beta_\nu \Rightarrow \text{prune}(\epsilon_\nu)$$

源代码通常不直接实现这个声明，而是在算法中产生它的效果，可以用简化的伪代码来表示。一旦理解了递归，执行此操作的算法就很简单。这是一个概念上的先决条件，所以如果还不知道，请先了解递归。

ab_minimax ν, α, β

    if ν.depth = search.max_depth or ν.is_leaf
        return ν.value

    if ν.is_maximizing
        for ε in ν.edges
            x = max(β, ab_minimax ε.child, α, β)
            if α ≥ β
                ν.prune ε
                return α
        return α
    else
        for ε in ν.edges
            x = min(α, ab_minimax child, α, β)
            if α ≤ β
                ν.prune ε
                return β
        return β