Answers.Body: <p>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.</p>
  
  <p>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.</p>
  
  <p>If you're not afraid of running out of memory, you can choose to expand as many nodes as you like. For example, <a href="https://github.com/DennisSoemers/MaastCTS2" rel="noreferrer">my General Video Game AI agent</a> 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.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-21T08:22:17.980Z
Answers.LastActivityDate: 2018-04-21T08:22:17.980Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>In Monte Carlo Tree Search (MCTS), we start at root node <span class="math-container">$R$</span>. Then we select some leaf node <span class="math-container">$L$</span>. And we expand <span class="math-container">$L$</span> by one or more child nodes and simulate from the child to the end of the game. </p>
  
  <p><a href="https://i.sstatic.net/bQH9b.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/bQH9b.png" alt="enter image description here"></a></p>
  
  <p>When should we expand and when should we simulate in MCTS? Why not expand 2 or 3 levels, and simulate from there, then back-propagate the values to the top?  Should we just expand 1 level? Why not more?</p>
  
Tags: <monte-carlo-tree-search>
Title: When to expand and when to simulate in Monte Carlo Tree Search?
UserDisplayName: Soroush
ThreadText: # When to expand and when to simulate in Monte Carlo Tree Search?
  
  (Asked by: username_0 on 2018-04-20)
  
  In Monte Carlo Tree Search (MCTS), we start at root node $R$. Then we select some leaf node $L$. And we expand $L$ by one or more child nodes and simulate from the child to the end of the game.
  
  [![enter image description here](https://i.sstatic.net/bQH9b.png)](https://i.sstatic.net/bQH9b.png)
  
  When should we expand and when should we simulate in MCTS? Why not expand 2 or 3 levels, and simulate from there, then back-propagate the values to the top? Should we just expand 1 level? Why not more?
  
  **Tags:** monte-carlo-tree-search
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-04-21. Score: 6 | Accepted answer
  
  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](https://github.com/username_1/MaastCTS2) 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.
  
  
  ---
  
  