In MCTS, we start at root node R. Then we select some leaf node L. And we expand it by one or more child nodes and simulate from the child to end of game.image link

My question is when to expand? and when to simulate? So why not expand 2 or 3 levels, and simulate from there, then backup values to top? Should we just expand 1 level? why not more? what is the criteria?


The most common strategy is to simply expand exactly one node per iteration; you can view this as expanding the first node of the Play-Out phase ("simulation" in your image), and not expanding any other nodes of the Play-Out phase. This is also what's done in your image.

That is the most common and probably most simple strategy, but it's certainly not the only one. It is pretty much the minimum you have to expand, but you can expand more if you like. The most common approach of only expanding one node per iteration is basically there because it minimizes the risk of running out of memory; when you only add one new node to the tree per iteration, the tree grows relatively slowly, so you'd have to keep the algorithm running for a really long time before you run out of memory.

If you're not afraid of running out of memory, you can choose to expand as many nodes as you like. For example, my General Video Game AI agent expands every single node encountered during the play-out at once, because in that particular domain we only get to run relatively few iterations anyway so I'm not afraid of running out of memory, even if I do expand lots of nodes.

The backpropagation step can only store results (information) from your iterations in nodes that actually exist, nodes that have been expanded. So, the benefit of expanding more (if possible) is that you'll retain more information from early iterations, your backpropagation step immediately gets to store results in all nodes along the path instead of only the top few nodes. Generally, this is a relatively minor benefit; nodes deep in the tree / deep inside the simulations are quite unlikely to ever get visited more than once anyway, and then this doesn't matter. But expanding more can, in theory, result in slightly more accurate value estimates in nodes closer to the root.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.