What to Do when Monte Carlo Tree Search Hits Memory Limit

Question

I have taken interest into monte carlo tree search applied in games recently.

I have read several papers, but i use "Monte-Carlo Tree Search" A Phd 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 problem. The algorithm tries to expand one node into the game tree for every one simulation. This quickly escalates to memory problem. I have quickly read the paper, but it doesnt seem to explain what the technique will do if it hits certain memory limit.

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

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

Answer 1

One very effective approach is to grow the tree more slowly. That is, instead of expanding the tree every time you reach a leaf node, you expand it once it has at least k visits. This will significantly slow the growth of the tree, and often does not reduce performance. I was told by one of the authors of the Fuego Go program that he tried the approach, and it worked well in practice.

This idea was originally described in this paper:

Remi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In Computers and games, pages 72–83. Springer, 2007.

It was also used in:

Max Roschke and Nathan Sturtevant. UCT Enhancements in Chinese Checkers Using an Endgame Database, IJCAI Workshop on Computer Games, 2013.

Answer 2

The paper Memory Bounded Monte Carlo Tree Search evaluates a variety of solutions for this problem :

• 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 exept 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 the node that has not been visited for the longest time