python - beta in alpha beta 搜索

Question

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

我的理解是:一个白人玩家下了一步棋(我们称它为 move1)。第一步被保存为 alpha(玩家确信的最小值)。现在，如果我们移动到下一个可能的白棋(move2)，并且看到黑棋手的第一个 react 导致估值比 alpha 差，我们可以跳过所有可能的黑棋反棋，因为我们已经知道当白棋走 move2 ，最坏的可能结果比 move1 的最坏可能结果更糟。

但是，我不明白的是那个 beta 变量。从国际象棋编程维基我读到:'最小化玩家可以保证的最高分数'。但我真的无法理解它背后的想法。

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

Answer 1

在国际象棋中，没有简单的方法可以判断 move1 是否优于 move2(根据您的示例)。近似值是通过查看“硬”参数实现的:棋子的数量和值(value)、双兵或空兵的存在……通常这种近似值被插入到极小极大算法中。

极小极大

简单来说，思路如下:首先，展开所有可能的走法(白-黑-白-黑-...)，直到达到预定的深度或时间限制。这创建了一个棋盘位置树(移 Action 为边缘)，并且使用启发式方法评估叶子(如上所述)。然后，树被折叠，最终导致对移动 1 与移动 2 的评估。

折叠是如何工作的？它从树的叶子开始，并为每个节点(又名棋盘位置)分配一个值。对于所有子节点的值已知的每个节点，子节点的值被聚合:如果轮到白人，则采用白人的最佳值(最大)；如果轮到黑色，则最差(最小)。因此得名极小极大。重复此操作，直到到达根为止。

假设以下棋盘位置树:

 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 .

优化

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