Juw*_*wan 7 algorithm artificial-intelligence minimax alpha-beta-pruning
我最近实现了 Minimax 和 Alpha Beta 剪枝算法，我 100% 确信（自动分级器）我正确地实现了它们。但是当我执行我的程序时，他们的行为有所不同。我 99% 肯定 minimax 和 Alpha beta 的最终状态应该相同。我对吗？他们在实现结果的道路上会有所不同吗？因为我们忽略了一些值 min 会选择 max 不会选择的值，反之亦然。
我知道这是一个老问题，但是......
是的 Alpha-beta 和 minimax 返回相同的答案。Alpha-Beta 所做的只是阻止 minimax 进行 100% 保证不是当前玩家的最佳状态（MAX 或 MIN）的计算。
但是，对于给定的状态，您可能有等效的操作。您的算法如何决定返回哪些等效操作取决于它的实现方式。如果在某处使用了集合/无序列表，则进行评估的顺序可能会改变。
如果 Alpha/Beta 值等于当前最佳选项，这也可能取决于您的操作。由于相等的值不会产生更好的结果，因此没有必要进一步探索该路径。因此，您只需保留“遇到的第一个最佳操作”。但是，对于 Minimax，您无论如何都要探索一切，因此您可能决定保留“最后一个最佳”值。在这种情况下，Minimax 将返回与 Alpha-Beta 不同的操作。但是就您的评分功能而言，它们仍然是等效的......