α-β搜索中的beta

Question

嗨！我试图实现一个alpha-beta搜索，但是我首先想理解它背后的所有逻辑，而不仅仅是使用某种伪代码来实现它。在

我的理解是：一个白人球员会做出一个动作（我们称之为move1）。第一步被保存为alpha（玩家可以保证的最小值）。现在，如果我们移动到白棋的下一个可能的移动（move2），并且看到黑人玩家的第一个反应结果是比alpha更差的估值，我们可以跳过所有可能的布莱克的反击动作，因为我们已经知道当white进行move2时，最坏可能的结果比move1的最差可能结果更糟糕。在

但是，我不明白的是贝塔变量。我从国际象棋编程wiki上读到：“最小化的玩家可以保证的最大分数”。但我真的搞不懂背后的意思。在

有人能简单地解释一下吗？非常感谢你。在

Answer 1

在国际象棋中，没有简单的方法来判断move1是否比move2好（从您的例子中）。近似值是通过观察“硬”参数来实现的：工件的数量和值，双爪或自由爪的存在。。。通常这种近似值被插入到minimax算法中。在

极小极大

简单地说，其思想如下：首先，所有可能的移动都被扩展（白-黑-白-黑-…），直到达到预定的深度或时间限制。这将创建一个棋盘位置树（以移动作为边），并使用启发式方法（如上所述）评估树叶。然后，树被折叠，最终得到move1和move2的计算结果。在

坍塌是怎么发生的？从每个节点的位置（aka）开始给每个节点赋值。对于所有子节点的值已知的每个节点，子节点的值将被聚合：如果轮到白色，则取白色的最佳值（max）；如果轮到black，则取最差值（min）。因此命名为minimax。重复此操作，直到到达根。在

假设以下董事会位置树：

 A
|  \
B1  B2
|   |  \
A11 A21 A22

现在假设下面的计算：A11=0，A21=-1，A22=+1（正值对白色比较好）。我们从近似值中假设位置A21优于A22（对于黑色），因此我们将-1指定给节点B2。对于B1，这是清楚的，它的值是0。现在我们假设B1比B2更适合白色，因此A的值为0，白色应该移动到B1的位置。在

Alpha-beta pruning

这里的想法不是建立整棵树，而是做一个深度优先搜索更有希望的行动，以实现早期切断。在上面的例子中，如果我们先从左到右遍历树的深度（A-B1-A11-B2-A21-…），我们在计算A21之后知道位置B2比位置B1更差。因此，没有必要再评估A22。Alpha和beta只是将当前已知的最佳可能移动的评估存储为白色，而当前已知的最佳可能回复为黑色。树节点的遍历顺序（初始顺序）决定了是否以及有多少个截断是可能的。来自维基百科：

Normally during alpha-beta, the subtrees are temporarily dominated by either a first player advantage (when many first player moves are good, and at each search depth the first move checked by the first player is adequate, but all second player responses are required to try to find a refutation), or vice versa. ...

如果排序是次优的，则必须完全探索更多的子树。在

另请参见 iterative deepening depth-first search。在

优化

{a3}严格地说，{a3}可以实现不同的位置组合。使用hash table来检测相同的位置，这将节省大量的计算工作量。在

Answer 2

基本的想法是alpha和beta是最优结果的上下界，从你已经探索过的博弈树来看，因此任何超出这些界限的东西都不值得探索。在

我已经有一段时间没有详细了解minimax和alpha-beta剪枝了，但我记得要点如下。在

如你所说，如果我们已经知道怀特的move1得分为10，而在考察move2时，我们发现黑人的反应方式是将白人逼到8的最佳分数，那么就不值得进一步研究move2；我们已经知道，我们能做的最好的结果比我们知道的另一个选项更糟糕。在

但这只是minimax算法的一半。假设我们现在正在检查白人的move3，并观察所有黑人的反应。我们研究了黑人的moveX，发现白人对的一种反应，可以迫使得分至少为15分。如果我们开始探索黑色的moveY（仍然是对白色的原始move3）的响应，并且发现白人对moveY的响应，这将迫使得分至少达到18分，那么我们马上就知道，源于黑人moveY的整个游戏树是没有意义的；黑色永远不会生成{}，因为{}只会迫使黑色允许白色得到15分，而moveY则强制黑色让白色获得18分。在

Alpha代表了我们已经知道的怀特可以通过做出不同的选择来达到我们正在探索的点的最低分数。因此，一旦我们知道不可能获得超过alpha的可能性，就不值得继续探索任何路径，因为白色不允许我们到达该路径。在

Beta代表了我们已经知道的一个最高分数，布莱克可以通过做出不同的选择来达到我们正在探索的目标。因此，一旦我们知道不可能得到小于beta的可能性，就不值得继续探索任何路径，因为黑色不允许我们到达该路径。在