1
$\begingroup$

I am trying to implement a Monte-Carlo-Tree-Search algorithm. My question is, during the simulation/playout/rollout phase, are new nodes added as children to the node C from which the simulation occurs, or is the only impact (on the tree) the change on score? Wikipedia says:

Simulation: Complete one random playout from node C. This step is sometimes also called playout or rollout. A playout may be as simple as choosing uniform random moves until the game is decided (for example in chess, the game is won, lost, or drawn).

Which I believe is ambiguous as to whether child nodes are created of C.

$\endgroup$

1 Answer 1

1
$\begingroup$

You will always need at least some mechanism for creating new nodes somewhere in your MCTS. If you have do not have this anywhere at all, your tree will never grow beyond the root node, and you're really just doing a flat Monte-Carlo search rather than MCTS.

Exactly where, when, and how often you create nodes can differ between different implementations and problems.

Usually, I will at some point have my Selection strategy picking an action for which no node exists in my tree yet. When this happens, I create a new node for that action to lead to, add that node to the tree, and start running the Play-out from that state onwards. This means that I add almost exactly one new node to the tree per iteration (where with "iteration" I refer to the whole Selection --> Expansion --> Play-out --> Backpropagation thing). I say "almost exactly one" rather than "exactly one", because the Selection phase might just end up traversing to a node that already represents a truly terminal game state, and then there's nothing more to add in that iteration.

Sometimes, people will use a threshold of a certain minimum number of times that an action must have been picked (for example, $10$ or $20$ or $30$ or whatever) before you actually create a new node. This would result in a much slower-growing tree, you'd be adding way less than 1 node per iteration. People do this usually to avoid running out of memory when using very long search times and/or highly efficient game implementations.

It is also sometimes useful to add more than one node per iteration. You can usually only afford this (without risk of running out of memory) if you're running extremely short searches. For example, you could immediately add nodes for all states encountered during your entire Play-out. I have done this myself when using MCTS in the "General Video Game AI" framework, where search times are extremely short due to the real-time nature of these video games (max 40milliseconds per search).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .