Answers.Body: <p><strong>NOTE</strong>: their description of the <em>selection</em> phase actually <strong>does not match</strong> the "standard implementation". They state to traverse the tree according to the selection strategy until a leaf node is reached. I disagree with this. <strong>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</strong> (a node that is not yet "fully expanded"). </p>
  
  <p>These two are only equivalent in the case where the expansion strategy is to immediately fully expand, to immediately create new nodes for <em>all</em> legal actions in <span class="math-container">$L$</span>. With such an expansion strategy, <span class="math-container">$L$</span> 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.</p>
  
  <p>Let <span class="math-container">$L$</span> 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 <span class="math-container">$C$</span> of <span class="math-container">$L$</span>, and then start the playout from <span class="math-container">$L$</span> onwards.</p>
  
  <blockquote>
    <p>And aren't leaves then permanently stuck as leaves, since playouts always start from their children, not them?</p>
  </blockquote>
  
  <p>No, as soon as you add the new child <span class="math-container">$C$</span> to <span class="math-container">$L$</span>, <span class="math-container">$L$</span> 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, <span class="math-container">$L$</span> will be just like any other internal node, <span class="math-container">$C$</span> 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 <span class="math-container">$L$</span> despite it not (anymore) being a leaf, if it still has unexpanded nodes other than <span class="math-container">$C$</span> (to-be-siblings of <span class="math-container">$C$</span>).</p>
  
  <blockquote>
    <p>Why is the playout started from a child of the first leaf, not the leaf itself?</p>
  </blockquote>
  
  <p>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) <strong>playout</strong> mechanism is to select actions uniformly at random <strong>from all legal actions</strong>. The most common (or, at least, most simple and straightforward) mechanism for selecting a new node <span class="math-container">$C$</span> to add to <span class="math-container">$L$</span> is to select uniformly at random <strong>only from those legal actions for which children have not already been added to <span class="math-container">$L$</span></strong>. Due to these mechanisms being different, we cannot initiliase the playout at <span class="math-container">$L$</span> and declare the first action of the playout to be the one that generates the new node <span class="math-container">$C$</span>; we have to use a (slightly) different implementation.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-13T09:04:23.260Z
Answers.LastActivityDate: 2019-07-13T09:04:23.260Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>On Wikipedia, <a href="https://en.wikipedia.org/wiki/Monte_Carlo_tree_search" rel="nofollow noreferrer">the MCTS algorithm</a> is described</p>
  <blockquote>
  <p><strong>Selection</strong>: start from root <span class="math-container">$R$</span> and select successive child nodes until a leaf node <span class="math-container">$L$</span> is reached. A leaf is any node from which no simulation (playout) has yet been initiated.</p>
  <p><strong>Expansion</strong>: create one (or more) child nodes and choose node <span class="math-container">$C$</span> from one of them. Child nodes are any valid moves from the game position defined by <span class="math-container">$L$</span>.</p>
  <p><strong>Simulation</strong>: complete one random playout from node <span class="math-container">$C$</span>.</p>
  </blockquote>
  <p>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 &quot;playout initialised&quot; from it, even though it started at its child?</p>
  
Tags: <monte-carlo-tree-search>
Title: Is the playout started from a leaf or child of leaf in Monte Carlo Tree Search?
UserDisplayName: Charlie
ThreadText: # Is the playout started from a leaf or child of leaf in Monte Carlo Tree Search?
  
  (Asked by: username_0 on 2019-07-13)
  
  On Wikipedia, [the MCTS algorithm](https://en.wikipedia.org/wiki/Monte_Carlo_tree_search) 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?
  
  **Tags:** monte-carlo-tree-search
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-07-13. Score: 1 | Accepted answer
  
  **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.
  
  
  ---
  
  