Minimax vs Alpha Beta Pruning算法

我最近实现了Minimax和Alpha Beta Pruning算法，我％100确定（autograder）我正确实现了它们。但是当我执行我的程序时，他们的行为有所不同。我％99确定minimax和Alpha beta的最终状态应该是相同的。我对吗？他们可以在实现结果的路上有所不同吗？因为我们忽略了一些值，min将选择哪个不会被max或vica选中。Minimax vs Alpha Beta Pruning算法

来源

2016-11-08 Prethia

它们都应该给出相同的结果。在alpha-beta中进行修剪涉及到无法在搜索树上提供更好结果2级别的分支。 – trincot

Autograder是来自[UC Berkeley AI Course]（http://ai.berkeley.edu/multiagent.html）的软件工具。 Minimax和Alpha beta prunning的实施是Pacman示例的一个挑战。目前还不清楚OP是否问及如何在学术课程上取得成功或如何使用人工智能玩游戏。 –

我没有要求输入密码。我已经实现了这些算法，并在我提到的不同场景下对它们进行了测试（这就是为什么我百分之百肯定，autograder给了我全分，所以这个问题与获得更好的成绩无关。）但即使autograder给了我全部点我认为有什么不对，这就是为什么我问。 – Prethia

我知道这不过是一个老问题....

是α-β和极小返回相同的答案。所有Alpha-Beta所做的都是防止极大极小的计算被100％保证不会成为当前玩家的最佳状态（MAX或MIN）。

然而，您可能对给定状态有相同的操作。您的算法如何决定返回哪个等效操作取决于实现方式。如果集合/无序列表在某处使用，评估的顺序可能会改变。

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

来源

2018-02-14 21:19:00

Minimax vs Alpha Beta Pruning算法

回答

相关问题