3
$\begingroup$

On Wikipedia, the MCTS algorithm is described

Selection: start from root $R$ and select successive child nodes until a leaf node $L$ is reached. A leaf is any node from which no simulation (playout) has yet been initiated.

Expansion: create one (or more) child nodes and choose node $C$ from one of them. Child nodes are any valid moves from the game position defined by $L$.

Simulation: complete one random playout from node $C$.

Why is the playout started from a child of the first leaf, not the leaf itself? And aren't leaves then permanently stuck as leaves, since playouts always start from their children, not them? Or does the leaf get attributed as having had a "playout initialised" from it, even though it started at its child?

$\endgroup$
1
$\begingroup$

NOTE: their description of the selection phase actually does not match the "standard implementation". They state to traverse the tree according to the selection strategy until a leaf node is reached. I disagree with this. The standard implementation is to traverse the tree until a node is reached in which there still are legal actions for which no child node has been created (a node that is not yet "fully expanded").

These two are only equivalent in the case where the expansion strategy is to immediately fully expand, to immediately create new nodes for all legal actions in $L$. With such an expansion strategy, $L$ would immediately turn from a leaf node into a fully expanded node. But that is not the "standard implementation". The most common expansion strategy is to only add a single new node to the tree per iteration.

Let $L$ denote a node that is reached at the end of the selection phase. The standard implementation is indeed to first expand in some way, which results in a new child $C$ of $L$, and then start the playout from $L$ onwards.

And aren't leaves then permanently stuck as leaves, since playouts always start from their children, not them?

No, as soon as you add the new child $C$ to $L$, $L$ is by definition no longer a leaf node; a leaf node is defined as a node with no children. The next time that MCTS decides to traverse the same part of the tree, $L$ will be just like any other internal node, $C$ will be a leaf node, and we may add yet another node below that in a future expansion phase. Or, of course, it is also possible that in a future iteration, our selection phase still ends in $L$ despite it not (anymore) being a leaf, if it still has unexpanded nodes other than $C$ (to-be-siblings of $C$).

Why is the playout started from a child of the first leaf, not the leaf itself?

This is because we typically require a slightly different mechanism for choosing a node to expand than the playout mechanism. The most common (or, at least, most simple and straightforward) playout mechanism is to select actions uniformly at random from all legal actions. The most common (or, at least, most simple and straightforward) mechanism for selecting a new node $C$ to add to $L$ is to select uniformly at random only from those legal actions for which children have not already been added to $L$. Due to these mechanisms being different, we cannot initiliase the playout at $L$ and declare the first action of the playout to be the one that generates the new node $C$; we have to use a (slightly) different implementation.

$\endgroup$

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.