What to Do when Monte Carlo Tree Search Hits Memory Limit

Question

I have taken an interest in the monte Carlo tree search applied in games recently.

I have read several papers, but I use "Monte-Carlo Tree Search" A Ph.D. thesis by Chaslot, G as i find it more easy to understand the basics of Monte Carlo tree search

I have tried to code it and stuck on certain problems. The algorithm tries to expand one node into the game tree for every one simulation. This quickly escalates to memory problems. I have quickly read the paper, but it doesn't seem to explain what the technique will do if it hits a certain memory limit.

Can you suggest what should the technique do if it hits a certain memory limit?

you can see the paper here: http://www.unimaas.nl/games/files/phd/Chaslot_thesis.pdf

Answer 1

The solutions to this problem are :

• Stopping: you stop the algorithm when you hit your memory limit

• Stunting: you stop growing the tree when you hit your memory limit (but keep updating it)

• Ensemble: you keep your result and restart the search from an empty tree when you hit your memory limit (fusing the results at the end)

• Flattening: when you hit your memory limit you get rid of all the nodes except the root and its direct children and restart the search from this new basis

• Garbage collection: when you hit your memory limit, you remove all nodes that have not been visited a given number of times

• Recycling: When you add a node, you delete a node that has not been visited for the longest time

For more information regarding the same, refer to the following link: http://mcts.ai/edpowley/papers/powley_aiide17.pdf