α-β 剪枝

Alpha-beta剪枝是一种搜索算法，可减少在双人博弈的极小化极大算法中评估的节点数量。通过维护两个值（alpha和beta），分别表示最大化玩家可保证的最小分数和最小化玩家可保证的最大分数，我们可以安全地剪枝那些不会影响最终决策的分支。

基本想法

在博弈树中，并非每个节点都需要评估。如果我们知道某个走法导致的结果比已经检查过的走法更差，就可以完全跳过探索其子节点。Alpha-beta剪枝通过跟踪边界来实现这一点：alpha（最大化者可以保证的最佳值）和beta（最小化者可以保证的最佳值）。当beta ≤ alpha时，我们进行剪枝。

该算法通过对博弈树进行深度优先搜索来工作。在每个MAX节点，我们用迄今为止看到的最大值更新alpha。在每个MIN节点，我们用迄今为止看到的最小值更新beta。如果在任何时候beta变得小于或等于alpha，我们就知道当前分支不能产生比我们已经找到的更好的结果，因此停止探索它。

Alpha-beta剪枝的有效性在很大程度上取决于走法排序。在完美排序（最佳走法首先评估）的情况下，alpha-beta可以剪枝掉极小化极大算法将评估的多达一半的节点，有效地将相同时间内可实现的搜索深度加倍。在随机排序的情况下，好处不太明显，但仍然显著。

节点n的极小化极大值V(n)是递归定义的。对于终端节点，V(n)等于其效用。对于MAX节点，V(n) = max(V(c))，对所有子节点c。对于MIN节点，V(n) = min(V(c))，对所有子节点c。

Alpha-beta剪枝在搜索期间维护两个参数：α表示最大化者在当前级别或更高级别可以保证的最佳值（最高），β表示最小化者在当前级别或更高级别可以保证的最佳值（最低）。最初，α = -∞且β = +∞。

在MAX节点，评估值为v的子节点后，我们更新α = max(α, v)。如果β ≤ α，我们剪枝剩余的子节点。在MIN节点，评估值为v的子节点后，我们更新β = min(β, v)。如果β ≤ α，我们剪枝剩余的子节点。剪枝条件β ≤ α称为截断。

在最佳走法排序下，评估的节点数为O(b^(d/2))，而不是纯极小化极大的O(b^d)，其中b是分支因子，d是深度。这意味着我们可以在相同时间内有效地搜索两倍深度，这在游戏中转化为明显更强的游戏水平。

Step: 0 / 5

Game tree at step 0

Pruned branches hidden

Best move ordering enabled

Step 0, without move ordering.

逐步查看博弈树上的alpha-beta剪枝

使用步进器查看alpha和beta值如何在树中向上传播并触发截断。注意哪些子树被剪枝以及走法排序如何影响评估的节点数量。

COMP30024（2022）。对抗搜索和博弈树算法。Russell & Norvig《人工智能：现代方法》（2020），第5章。

初稿于2023，2026年重写。