蒙地卡羅樹搜索改進

Question

我試圖在遊戲上實現MCTS算法。我每次只能使用大約0.33秒。在這個時候，我可以從每個孩子的起始狀態產生一到兩個遊戲，其中包含大約500個子節點。我的模擬不是隨機的，但當然我不能根據1或2模擬做出正確的選擇。在遊戲中，樹越來越小，我可以根據更多的模擬進行選擇。

所以我的問題是在前幾個步驟。有沒有辦法改進MCTS算法，以便它可以模擬更多的遊戲，或者我應該使用其他算法？

Answer 1

是否有可能爲狀態提出一些啓發式評估函數？我意識到MCTS的主要好處之一就是理論上你不需要這個，但是：如果你可以創建一個合理的評估函數，這將允許你在到達終端遊戲狀態之前儘早停止模擬。然後，您可以備份對這種非終極遊戲狀態的評估，而不僅僅是一場勝利或一場損失。如果你像這樣早點停止你的模擬，你可能能夠運行更多的模擬（因爲每個單獨的模擬需要更少的時間）。

除此之外，你會想嘗試找到'概括'的方法。如果你運行一次模擬，你應該試着看看你是否也可以從樹中爲樹中其他沒有經過的節點提取一些有用的信息。您可能需要考慮的增強功能有AMAF，RAVE，Progressive History，N-Gram Selection Technique。

您是否碰巧知道瓶頸在哪裏？你可以使用探查器來調查這一點。如果大部分處理時間花在與遊戲有關的功能上（移動代，從一個狀態前進到下一個等等），你肯定知道你將會限制你可以執行的模擬次數。然後，您應該嘗試實施增強功能，使每個單獨的模擬信息儘可能地豐富。例如，這可能意味着使用非常好的，計算成本較高的評估函數。如果遊戲代碼本身已經非常優化並且速度很快，那麼將額外的計算時間移到諸如評估函數之類的東西將會對您的模擬計數造成更大的傷害，並且可能會減少支付。

想了解更多關於這最後一個想法，看看我在我的MCTS-based agent in General Video Game AI上寫的一些東西可能會很有趣，這也是一個實時環境，其計算量非常昂貴，這意味着模擬計數受到嚴重限制（但分支因素遠遠小於你的情況）。我的出版物的pdf文件也可以在線獲得。