蠻力和Minimax/AlphaBeta修剪

Question

蠻力本質上只是搜索每個可能的組合，但minimax如何不同？ Minimax也搜索每個組合，然後返回最佳分數？

我明白，當我們使用alpha beta修剪時，我們會取出那些對我們的最小/最大值沒有任何影響的，但是這種情況在我們已經執行minimax之後發生，所以這會被認爲是蠻力嗎？也許我誤解了我到目前爲止所閱讀的內容，所以任何幫助都會很棒！

謝謝！

Answer 1

Alpha-beta修剪不會發生在「最小」之後，它出現在「最小最大」期間。事實上，修剪確實可以消除大量的「組合」 - 在最好的情況下，平均情況下n ^（3/4）可以減少到最小值的最大值的sqrt。

Answer 2

Minimax是一種更爲有效的方式來瀏覽決策樹而不是蠻力。由於只有可能包含更好解決方案的節點纔會被訪問，與蠻力相反，其中所有節點都被訪問，而沒有任何修剪。

Wiki：

啓發式還可以用來做搜索的部分的提前切斷。其中一個例子是搜索遊戲樹的極小極大原理，它在搜索的早期階段消除了許多子樹。

在Minimax中，您根據可用的移動和他們的分數切割了部分樹，這意味着您不會覆蓋所有可能性，這使得它優於強力方法。