遊戲搜索樹，我必須先建樹嗎？

Question

在遊戲搜索樹中有很多算法來獲得最優解，如minimax算法。我開始學習如何用minimax算法解決這個問題，算法清晰。但我對樹本身感到困惑，在像tic tac toe節點的遊戲節點數量不是很大的遊戲中，但在像棋等其他節點上有很多節點。我認爲這需要記憶中的大空間。那麼是否有算法在同一時間評估和構建樹？

Answer 1

遊戲狀態的樹通常不會建成一個完整的數據結構。相反，狀態會在創建時進行評估，並且大多數狀態在過程中被丟棄。通常情況下，狀態的鏈接列表會被評估回當前的遊戲狀態。但是如果一個舉動表現出比另一個好得多，那麼整個窮人行動將被放棄，所以它將不會佔用記憶空間。尋找像國際象棋比賽的狀態空間

一個簡單的方法是遞歸地進行搜索，以給定的深度。在這種情況下，實際上只有很少的遊戲狀態存在，而那些確實存在的遊戲狀態只是在調用堆棧中被引用。更復雜的算法會創建一個更大的樹，但是（特別是國際象棋）沒有人會維護一個包含所有可能狀態的樹。對於象棋，廣度優先搜索可能會更好，使用隊列而不是堆棧，並且這將只保留樹中特定深度的狀態。更好的是優先級隊列，其中存儲最佳狀態用於進一步評估，並且最壞狀態完全丟棄。