Answers.Body: <p>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.</p>
  <p>Exactly where, when, and how often you create nodes can differ between different implementations and problems.</p>
  <p>Usually, I will at some point have my <em>Selection strategy</em> 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 <em>Play-out</em> from that state onwards. This means that I add almost exactly one new node to the tree per iteration (where with &quot;iteration&quot; I refer to the whole <em>Selection</em> --&gt; <em>Expansion</em> --&gt; <em>Play-out</em> --&gt; <em>Backpropagation</em> thing). I say &quot;almost exactly one&quot; rather than &quot;exactly one&quot;, because the <em>Selection</em> 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.</p>
  <p>Sometimes, people will use a threshold of a certain minimum number of times that an action must have been picked (for example, <span class="math-container">$10$</span> or <span class="math-container">$20$</span> or <span class="math-container">$30$</span> 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.</p>
  <p>It is also sometimes useful to add <em>more</em> 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 <em>all states</em> encountered during your entire <em>Play-out</em>. I have done this myself when using MCTS in the &quot;General Video Game AI&quot; framework, where search times are extremely short due to the real-time nature of these video games (max 40milliseconds per search).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-11T11:25:06.433Z
Answers.LastActivityDate: 2024-02-11T11:25:06.433Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>The norm is to expand only when you reach a node with N=1, after a simulation as N and S values are updated via backpropagation, you should re run the selection phase from the the head of the tree.</p>
  <p>When stumbling upon a N=1 node, then you should expand, some implementations only expand one node from the start, others all of them and others a specific amount that works for that particular game. Either way you have to run a simulation in any random node of the ones you generate.</p>
  <p>In a recent Gomoku Agent I made, I had a list of all possible plays and extended one node from the list onexpansion (N=1) and per selection if I had plays left to create nodes from I would extend a node from them.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-30T13:29:26.453Z
Answers.LastActivityDate: 2024-09-30T13:29:26.453Z
Answers.UserDisplayName: ModderG
Body: <p>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:</p>
  <blockquote>
  <p>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).</p>
  </blockquote>
  <p>Which I believe is ambiguous as to whether child nodes are created of C.</p>
  
Tags: <monte-carlo-tree-search>
Title: In MCTS, does a simulation create new nodes
UserDisplayName: JohnT
ThreadText: # In MCTS, does a simulation create new nodes
  
  (Asked by: username_0 on 2024-02-10)
  
  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.
  
  **Tags:** monte-carlo-tree-search
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2024-02-11. Score: 1
  
  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).
  
  
  ---
  
  ### Answer by username_2 on 2024-09-30. Score: 0
  
  The norm is to expand only when you reach a node with N=1, after a simulation as N and S values are updated via backpropagation, you should re run the selection phase from the the head of the tree.
  
  When stumbling upon a N=1 node, then you should expand, some implementations only expand one node from the start, others all of them and others a specific amount that works for that particular game. Either way you have to run a simulation in any random node of the ones you generate.
  
  In a recent Gomoku Agent I made, I had a list of all possible plays and extended one node from the list onexpansion (N=1) and per selection if I had plays left to create nodes from I would extend a node from them.
  
  
  ---
  
  