Setting a memory limit on my AI algorithm?

Question

I am working on a Tetris AI implementation. It is a GUI application that plays the game by itself. The user can manipulate a few parameters that influence the decisions made by the AI. The basic algorithm goes as follows:

• Start a new thread and clone the current game state to avoid excessive locking.
• Generate a list of all possible future game states. These become child nodes of the current game state.
• For each child node generate it's future game states.
• Keep doing this recursively until a predefined depth has been reached.
• Once the requested depth has been reached, find the best end node and recursively find it's parent node until you have the first level child.
• Delete all child nodes that are not on the path between the child node and the end node.
• This path is now the list of precalculated moves.
• The main game executes the list of precalculated moves (with some fancy animation).

This is working pretty well up until search depth 4. After that I start to get memory problems. The number of possible game states can go from 9 to 34. So the worst case scenario for a level 4 search would be 34^4 game states. Windows XP seems unable to deal with level 5 searches (it hangs at 2+ GB).

So if I want to use deeper searches I'll need to use a strategy where I delete the non-promising branches and continue with the ones that will lead to a good score. But this makes it harder to estimate a maximum acceptable search depth. Therefore I think that I would be better to specify a memory limit instead of a depth limit.

I considering to use a memory pool and use "placement new" to create my objects on the pool's memory segments. However the game grid is implemented as a STL vector. So in order to allocate it on the pool I need to implement a custom allocator.

This seems quite a challenge and perhaps I'm overlooking a simpler solution. So I'd like your insights on how to best deal with this.

Can boost, or another library, provide me some of these facilities? (I already found Poco's MemoryPool.) Are there any good online resources to help me get going?

FYI: here's the source code and a sample binary for Windows.

Answer 1

You can create a memory pool, etc, but that won't really make it any easier or harder to count game state instances. You do need to make sure you don't go over a certain number of active states in your decision tree, with or without a pool. And Boost does have one: http://www.boost.org/doc/libs/1_44_0/libs/pool/doc/index.html

It sounds like you're not really doing any pruning of the tree, which would allow you to get much deeper. Evaluate each future game state and drop ones unlikely to develop into anything useful, and don't waste your time going down that branch.

Answer 2

Despite the lack of context [what kind of search problem are you doing? Depth first, breadth first, A*?....] My suggestion is:

Use semaphores to limit the amount of processing that is done at one time, and then release it once the processing has been evaluated. I can't really recommend a specific library that includes Semaphores, as that threading is not built in to C++, however check with your framework's documentation.