在我的AI算法上設置內存限制？

Question

我正在開發一個Tetris AI實現。它是一個自己玩遊戲的GUI應用程序。用戶可以操縱一些影響AI做出的決定的參數。基本算法如下：

• 開始一個新線程並克隆當前遊戲狀態以避免過度鎖定。
• 生成所有可能的未來遊戲狀態列表。這些成爲當前遊戲狀態的子節點。
• 對於每個子節點生成未來的遊戲狀態。
• 繼續執行此操作直至達到預定深度。
• 一旦達到要求的深度，找到最好的結束節點，並遞歸查找它的父節點，直到你有第一級別的孩子。
• 刪除不在子節點和結束節點之間的路徑上的所有子節點。
• 此路徑現在是預先計算的移動列表。
• 主遊戲執行預先計算的動作列表（帶有一些花哨的動畫）。

這是工作得很好直到搜索深度4.之後，我開始得到內存問題。可能的遊戲狀態的數量可以從9到34.因此，針對4級搜索的最壞情況將是34^4個遊戲狀態。 Windows XP似乎無法處理5級搜索（它掛在2+ GB）。

所以如果我想使用更深入的搜索，我需要使用一種策略，我刪除非有前途的分支並繼續那些會導致好分數的分支。但是這使得估計最大可接受的搜索深度變得更困難。因此，我認爲我會更好地指定內存限制而不是深度限制。

我正在考慮使用內存池並使用「放置新」來在池的內存段上創建我的對象。然而，遊戲網格被實現爲STL向量。所以爲了在池上分配它，我需要實現一個自定義分配器。

這似乎是一個很大的挑戰，也許我忽略了一個更簡單的解決方案。所以我希望你對如何最好地解決這個問題的見解。

可以提升或其他圖書館爲我提供這些設施嗎？ （我已經找到Poco的MemoryPool。）有沒有什麼好的在線資源可以幫助我開始？

供參考：這是source code和sample binary for Windows。

Answer 1

你可以創建一個內存池等，但這並不會讓它更容易或更難計算遊戲狀態實例。您確實需要確保您不會在決策樹中超過一定數量的活動狀態，無論是否有池。而且Boost確實有一個：http://www.boost.org/doc/libs/1_44_0/libs/pool/doc/index.html

聽起來好像你並沒有真的在修剪這棵樹，這會讓你變得更深。評估每個未來的遊戲狀態，並刪除不可能發展成任何有用的遊戲狀態，並且不要浪費時間沿着該分支行進。

Answer 2

儘管沒有上下文[你在做什麼樣的搜索問題？深度第一，幅度第一，A *？....]我的建議是：

使用信號量來限制一次完成的處理量，然後在處理完成後進行釋放。我不能真正推薦一個包含信號量的特定庫，因爲線程不是內置在C++中的，但請檢查您的框架文檔。