alpha beta搜索中的beta

Question

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

我所理解的是:一个白人玩家下了一步棋(让我们称之为move1)。第一步保存为alpha (玩家确信的最小值)。现在，如果我们移动到白色的下一个可能的移动( move2 )，并且看到黑人玩家的第一个响应结果的估值比阿尔法更差，我们可以跳过所有可能的黑色的反转，因为我们已经知道，当白色做出move2时，最坏的可能结果比Move1的最坏的可能结果更差。

但是，我不理解的是beta变量。我从国际象棋编程维基上读到：“最小化的棋手得到的最高分数”。但我真的不能理解它背后的想法。

有人能用非常简单的术语解释一下吗？非常感谢。

Answer 1

在国际象棋中，没有简单的方法来判断move1是否比move2更好(从您的示例中看)。近似是通过查看“硬”参数来实现的:棋子的数量和价值，双兵或空兵的存在，……通常，这样的近似被插入到极小极大算法中。

极小极大

简单地说，这个想法是这样的:首先，所有可能的动作都被扩展(白-黑-白-黑-...)直到达到预定义的深度或时间限制。这将创建一个棋盘位置树(以移动为边)，并使用启发式算法(如上所述)评估树叶。然后，树被折叠，最终导致对move1与move 2的评估。

折叠是如何工作的？它从树的叶子开始，并为每个节点分配一个值(也称为板位)。对于每个已知所有子节点的值的节点，都会聚合childs的值:如果轮到白色，则取白色的最佳值(max)；如果轮到黑色，则取最差的值(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只存储当前已知的白色最佳可能移动和黑色当前已知最佳可能回复的评估。遍历树的节点的顺序(初始顺序)决定了是否以及有多少截断是可能的。来自维基百科：

通常在α-beta期间，子树暂时由第一玩家优势(当许多第一玩家移动是好的，并且在每个搜索深度由第一玩家检查的第一移动是足够的，但需要所有第二玩家响应以试图找到反驳)或反之。..。

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

另请参见iterative deepening depth-first search。

优化

严格地说，树是一个DAG，因为相同的棋盘位置可以通过不同的移动组合(例如，transpositons)来实现。使用hash table来检测相同的位置，这将节省大量的计算工作量。

Answer 2

基本上，我们的想法是，alpha和beta是最优结果的上下限，来自您已经探索过的博弈树，所以超出这些界限的任何东西都不值得探索。

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

正如你所说的，如果我们已经知道白色的move1的分数是10，并且在检查move2时，我们发现黑色可以以这样一种方式做出响应，即白色被强制为最佳分数8，那么就不值得进一步研究move2；我们已经知道，我们所能做的最好的结果是比我们所知的另一种选择更糟糕。

但这只是极小极大算法的一半。假设我们现在正在检查白色的move3，并查看所有黑色的响应。我们探索黑人的moveX，发现白人对此的反应之一可以强制得分至少为15。如果我们随后开始探索黑人的moveY (仍然是对白色原始move3的回应)，并发现白人对moveY的回应将强制得分至少为18，那么我们立即知道，由黑人的moveY产生的整个博弈树是毫无意义的；黑人永远不会成为moveY，因为moveX只迫使黑人允许白色得分15分，而moveY迫使黑人允许白色得分18分。

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

Beta代表了我们已经知道的最高分数，黑色可以通过做出不同的选择来强制到达我们正在探索的点。因此，一旦我们知道不可能得到低于beta的结果，就不值得继续探索任何道路，因为black不允许我们走上这条道路。