Minimax 与 Alpha Beta 剪枝算法
Minimax vs Alpha Beta Pruning algorithms
我最近实现了 Minimax 和 Alpha Beta Pruning 算法，我 100% 确定（autograder）我正确地实现了它们。但是当我执行我的程序时，它们的行为有所不同。我 99% 确定 minimax 和 Alpha beta 的最终状态应该是一样的。我对吗？他们能否在实现结果的道路上有所不同？因为我们忽略了一些值 min will select which will not be selected by max 反之亦然。
不过我知道这是一个老问题....
是的 Alpha-beta 和 minimax return是相同的答案。 Alpha-Beta 所做的只是防止 minimax 进行 100% 保证不是当前玩家最佳状态的计算（MAX 或 MIN）。
然而，对于给定的状态，您可能有等效的操作。您的算法如何决定 return 的等效操作取决于它的实现方式。如果某处使用 sets/unordered 列表，则计算的顺序可能会改变。
如果 Alpha/Beta 值等于当前最佳选项，这也可能取决于您的操作。由于相等的值不会产生更好的结果，因此进一步探索该路径没有意义。因此，您只需保留 "first best action encountered"。然而，对于 Minimax，您无论如何都要探索一切，因此您可能决定保留 "last best" 值。在这种情况下，Minimax 会 return 采取与 Alpha-Beta 不同的行动。但就您的评分功能而言，它们仍然是等价的...
我最近实现了 Minimax 和 Alpha Beta Pruning 算法，我 100% 确定（autograder）我正确地实现了它们。但是当我执行我的程序时，它们的行为有所不同。我 99% 确定 minimax 和 Alpha beta 的最终状态应该是一样的。我对吗？他们能否在实现结果的道路上有所不同？因为我们忽略了一些值 min will select which will not be selected by max 反之亦然。
不过我知道这是一个老问题....
是的 Alpha-beta 和 minimax return是相同的答案。 Alpha-Beta 所做的只是防止 minimax 进行 100% 保证不是当前玩家最佳状态的计算（MAX 或 MIN）。
然而，对于给定的状态，您可能有等效的操作。您的算法如何决定 return 的等效操作取决于它的实现方式。如果某处使用 sets/unordered 列表，则计算的顺序可能会改变。
如果 Alpha/Beta 值等于当前最佳选项，这也可能取决于您的操作。由于相等的值不会产生更好的结果，因此进一步探索该路径没有意义。因此，您只需保留 "first best action encountered"。然而，对于 Minimax，您无论如何都要探索一切，因此您可能决定保留 "last best" 值。在这种情况下，Minimax 会 return 采取与 Alpha-Beta 不同的行动。但就您的评分功能而言，它们仍然是等价的...