如何將最小最大值算法應用於十六進制遊戲

Question

如何使用最小最大值算法設計高效的十六進制遊戲算法，因爲它的分支因子太高。 使用簡單的最小最大算法，但在這種情況下，對於一個11 * 11棋盤遊戲，我們有121個組合，所以對於這個如何減少組合數量什麼是最小化這種組合方法

Answer 1

遊戲中的動作樹只能完全適用於井字遊戲等簡單的東西。其他遊戲，如國際象棋，將會過於深刻，並且在每次移動時都會有太多選項（較大的分支因素）。

在您的問題的非常一般的層面上，有些措施可以對付這種限制。

最重要的是，您需要啓發式爲中間遊戲位置分配一個值。這使您可以應用極小極小，即使對遊戲結束的所有移動的分析都不可能。這些啓發式可能非常簡單。例如，在國際象棋中，你可以給棋子一個值（棋子1，騎士3等等）並簡單地加起來。考慮到電路板上的位置等，您可能會稍微複雜一些，但這裏的性能會有所折衷。這是許多AI系統的基礎。

一個經典的改進叫做alpha-beta pruning。這是基於以有序的方式評估運動樹的節點，以便可以省略已經保證比其他分支更差的分支，從而提高效率。 （例如，考慮一個分支，其中一個玩家可以強制獲勝運動：該分支內的這種運動的替代物並不重要，因爲如果遊戲以這種方式進行，該玩家將總是強制獲勝運動）。

其他算法改變了我們探索運動樹的方式。 Monte-Carlo tree search就是一個例子。這裏的核心思想是評估節點並以協調的方式探索樹（與之前相反，我們首先儘可能深入地探索樹，然後評估樹葉）。在這裏，我們有一個探索 - 開發平衡（你必須決定是否想要開發更有前途的職位，或者如果你想贊成探索新的，可能令人失望的運動）。