蛮力和Minimax/AlphaBeta修剪

Question

蛮力本质上只是搜索每个可能的组合，但minimax如何不同？ Minimax也搜索每个组合，然后返回最佳分数？

我明白，当我们使用alpha beta修剪时，我们会取出那些对我们的最小/最大值没有任何影响的，但是这种情况在我们已经执行minimax之后发生，所以这会被认为是蛮力吗？也许我误解了我到目前为止所阅读的内容，所以任何帮助都会很棒！

谢谢！

Answer 1

Alpha-beta修剪不会发生在“最小”之后，它出现在“最小最大”期间。事实上，修剪确实可以消除大量的“组合” - 在最好的情况下，平均情况下n ^（3/4）可以减少到最小值的最大值的sqrt。

Answer 2

Minimax是一种更为有效的方式来浏览决策树而不是蛮力。由于只有可能包含更好解决方案的节点才会被访问，与蛮力相反，其中所有节点都被访问，而没有任何修剪。

Wiki：

启发式还可以用来做搜索的部分的提前切断。其中一个例子是搜索游戏树的极小极大原理，它在搜索的早期阶段消除了许多子树。

在Minimax中，您根据可用的移动和他们的分数切割了部分树，这意味着您不会覆盖所有可能性，这使得它优于强力方法。