Answers.Body: <p>In the basic form, if you encounter a terminal leaf, you add visits and score depending on whether it is a win or loss, and backpropagate accordingly. The same as if you made a simulation step, but in this case the "simulation" is instant.</p>
  
  <p>But you can improve that: If the leaf is losing, you can give it a very large negative score or even <span class="math-container">$-\infty$</span>, so in the next selection step it surely won't be chosen, unless other moves are as bad. But if it is a winning leaf, you not only can give it a very big positive score or <span class="math-container">$\infty$</span>, but also add a negative score for the immediate parent, so the parent won't be chosen, as it is obviously a losing state for him. This way we can save some simulations. I had encountered that situation many times in my game and Monte Carlo tree searches.</p>
  
  <p>Suppose the parent has <span class="math-container">$200$</span> unexplored children, <span class="math-container">$10$</span> of which are immediate wins for the opponent. Your search may explore <span class="math-container">$100$</span> non-winning children and have a score of 80/100. But then it encounters the terminate child. After that, normally, it would have <span class="math-container">$80/101$</span>, so, still, a big chance to be chosen in the next iteration. And it would take many iterations to see that this is not a good move, as it would need to get like <span class="math-container">$80/150$</span> or more. But if we cancel out the score or give it a negative one like <span class="math-container">$-1/101$</span>, then we ensure it won't be chosen.</p>
  
  <p>It seems in literature it's called "MCTS solver", to backpropagate proven wins and losses.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-07-03T06:29:00.720Z
Answers.LastActivityDate: 2019-11-18T21:47:19.723Z
Answers.LastEditDate: 2019-11-18T21:47:19.723Z
Answers.UserDisplayName: derjack
Body: <p>In Monte Carlo tree search, what should we do when the selection step selects a terminal state (i.e. a won or lost state), which is, by definition, a leaf node? Expansion and simulation is not in order, as it's game over, but does the tree (score/visits) need to be updated (backpropagation)? Won't this particular node be selected continuously?</p>
  
Tags: <monte-carlo-tree-search>
Title: What should we do when the selection step selects a terminal state?
UserDisplayName: degski
ThreadText: # What should we do when the selection step selects a terminal state?
  
  (Asked by: username_0 on 2017-01-11)
  
  In Monte Carlo tree search, what should we do when the selection step selects a terminal state (i.e. a won or lost state), which is, by definition, a leaf node? Expansion and simulation is not in order, as it's game over, but does the tree (score/visits) need to be updated (backpropagation)? Won't this particular node be selected continuously?
  
  **Tags:** monte-carlo-tree-search
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-07-03. Score: 7 | Accepted answer
  
  In the basic form, if you encounter a terminal leaf, you add visits and score depending on whether it is a win or loss, and backpropagate accordingly. The same as if you made a simulation step, but in this case the "simulation" is instant.
  
  But you can improve that: If the leaf is losing, you can give it a very large negative score or even $-\infty$, so in the next selection step it surely won't be chosen, unless other moves are as bad. But if it is a winning leaf, you not only can give it a very big positive score or $\infty$, but also add a negative score for the immediate parent, so the parent won't be chosen, as it is obviously a losing state for him. This way we can save some simulations. I had encountered that situation many times in my game and Monte Carlo tree searches.
  
  Suppose the parent has $200$ unexplored children, $10$ of which are immediate wins for the opponent. Your search may explore $100$ non-winning children and have a score of 80/100. But then it encounters the terminate child. After that, normally, it would have $80/101$, so, still, a big chance to be chosen in the next iteration. And it would take many iterations to see that this is not a good move, as it would need to get like $80/150$ or more. But if we cancel out the score or give it a negative one like $-1/101$, then we ensure it won't be chosen.
  
  It seems in literature it's called "MCTS solver", to backpropagate proven wins and losses.
  
  
  ---
  
  