algorithm - Minimax 的 Alpha-beta 剪枝

Question

我花了一整天的时间在没有真正理解的情况下尝试实现 minimax。现在，我想我了解 minimax 的工作原理，但不了解 alpha-beta 剪枝。

这是我对极小极大的理解:

1. 生成所有可能移动的列表，直到深度限制。

2. 评估游戏 field 对底部每个节点的有利程度。

3. 对于每个节点(从底部开始)，如果层数最大，则该节点的分数是其子节点的最高分数。如果该层为 min，则该节点的分数是其子节点的最低分数。

4. 如果您想获得最高分数，请执行得分最高的 Action ；如果您想要最低分数，请执行最低分数。

我对alpha-beta剪枝的理解是，如果parent layer是min，你的node的score比minimum score高，那你就可以prune了，不会影响结果。

但是，我不明白的是，如果你能计算出一个节点的分数，你将需要知道比该节点低一层的所有节点的分数(我对minimax的理解)。这意味着您仍将使用相同数量的 CPU 能力。

谁能指出我错在哪里？这个答案 ( Minimax explained for an idiot ) 帮助我理解了 minimax，但我不明白 alpha beta 修剪会有什么帮助。

谢谢。

Answer 1

要理解 Alpha-Beta，请考虑以下情况。轮到白棋了，白棋试图最大化分数，黑棋试图最小化分数。

白方评估 A、B 和 C 步，发现 C 的最佳分数是 20。现在考虑评估步 D 时会发生什么:

如果白棋选择D，我们需要考虑黑棋的反棋。早期，我们发现黑色可以捕获白色皇后，并且由于丢失皇后，该子树的 MIN 得分为 5。然而，我们并没有考虑所有的黑人反击。是否值得检查其余部分？没有。

我们不关心黑方是否可以得到低于 5 的分数，因为白方走“C”可以将分数保持在 20。黑方不会选择得分高于 5 的反击，因为他试图最小化得分并且已经找到得分为 5 的着法。对于白色，一旦 D 的 MIN(目前为 5)低于 C 的 MIN(肯定是 20)，着法 C 优于移动 D。所以我们在那里“修剪”树的其余部分，弹出一个级别并评估白色移动 E、F、G、H .... 到最后。

希望对您有所帮助。