Minimax vs Alpha Beta修剪算法

我最近实现了Minimax和Alpha Beta修剪算法,我100%肯定(自动编程器)我正确实现了它们 . 但是当我执行我的程序时,他们的行为却不同 . 我确定minimax和Alpha beta的最终状态应该相同 . 我对吗?他们在实现结果的道路上有所不同吗?因为我们忽略了一些值,所以min将选择哪个不会被max选择,反之亦然 .

回答(1)

3 years ago

我知道这是一个古老的问题....

是的Alpha-beta和minimax返回相同的答案 . 所有Alpha-Beta都可以防止minimax进行100%保证的计算,使其不是当前玩家的最佳状态(MAX或MIN) .

但是,对于给定的州,您可能有相同的行动 . 您的算法如何决定返回哪些等效操作取决于它的实现方式 . 如果在某处使用了集/无序列表,则进行评估的顺序可能会发生变化 .

这可能还取决于您在Alpha / Beta值等于当前最佳选项时所执行的操作 . 由于相等的值不会产生更好的结果,因此没有必要进一步探索这条路径 . 因此,您只需保持“遇到的第一个最佳动作” . 然而,对于Minimax,您无论如何都要探索一切,因此您可能决定保持“最佳”值 . 这是Minimax将返回与Alpha-Beta不同的行为的一个案例 . 但就你的得分功能而言,它们仍然是等价的......