Answers.Body: <p>Imagine a game with a very clear first move, such as a game where choosing to go first if you win a coin toss brings a clear and obvious advantage.</p>
  
  <p>In this situation standard MCTS does little exploration down the side of the tree that branches at the win toss > let opponent start step, as the basic simulations of the rest of the game at this split quickly show the large gain you get when always starting when you win the coin toss.</p>
  
  <p>As a result, you would end up with a tree with very little expansion on the side of win the toss > put your opponent in, as every simulation step you do from even the most senior nodes ends with much worse expected outcome values than the alternatives on the other side of the tree where you do the correct move of always playing first.</p>
  
  <p>These nodes on the side of letting your opponent start have <em>huge</em> potential sub trees (as the whole game would still need to be played out if your opponent started), but would have very little searching down them. As a result, on this side of the tree, you would have many leaf nodes with large (but as yet unexplored, outside of the basic, early simulations down that side) sub trees that you <em>could</em> search if you modified the exploration vs exploration algorithm.</p>
  
  <p>As a basic example, take the 0/3 node at the far right on level one of the wiki example below, which would get much less attention than the much more promising 7/10 and 3/8 nodes, despite having potentially many subsequent children it <em>could</em> explore. If you took this node as your L node, you would expand it's children that you have not yet searched, and thus find out more about why this side of the tree is bad and update our now more granular probabilities accordingly, just as it does for the 3/3 node here:</p>
  
  <p><a href="https://i.sstatic.net/A5vw0.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/A5vw0.png" alt="enter image description here"></a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T10:50:43.577Z
Answers.Text: Thank you @Philip for your answer. As you post the diagram here, let me ask my questions in other words based on your diagram. The tree on the most left has 4 levels, there are 2 nodes on the bottom of the tree, 2/3 and 3/3. 
  
  How the values 2/3 and 3/3 are calculated? 
  Whether there are more levels under 2/3 and 3/3 are now shown, what nodes are not shown here? Whether the nodes from 2/3 to the terminal nodes (an end state of the game)  are not shown? Otherwise, how is 2 calculated?. 
  And why are these nodes not shown? 
  Why does the step "Selection" stop on node 2/3 and 3/3?
Answers.UserDisplayName: Wenbo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T11:09:03.057Z
Answers.Text: Don't know why I can't edit my last comment. For the question
  > How the values 2/3 and 3/3 are calculated?
  I meant without deeper search under 2/3 and 3/3, how the values of the 2 nodes are obtained. I understand the meaning of 2 and 3.
Answers.UserDisplayName: Wenbo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T11:22:41.020Z
Answers.Text: These would be created using some kind of simulation logic. This could range from just making random moves through to using the current best AI to play itself down until a finish. Those values are what the score has been so far using that simulation logic, and thus represent the best approximation of the current expected value of that branch of the game using that simulation logic.
Answers.UserDisplayName: Philip
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T11:45:02.407Z
Answers.Text: Say initially, there is only one root node which should be 0/0, then how this node can be filled as 11/21? By simulation logic of step "Simulation"? A simple approach for this step is selecting random action until a finish, can a random action ends with 11/21? I definitely misunderstood something.
Answers.UserDisplayName: Wenbo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T11:50:56.690Z
Answers.Text: At the start of the tree it was 0/0. The first iteration will have picked one of the three possible children (here, nodes now at 7/10, 3/8 and 0/3), and played the game out from there and recorded the result. Say the first child was the node that is now 0/3, we know that game would have been a loss, so the first node would now be 0/1 and the far right node would also be 0/1. As each trial repeats this process updates until we reach 21 trials and you have the graph above at step one.
Answers.UserDisplayName: Philip
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T11:54:30.450Z
Answers.Text: Also note how at step four above when the simulation is complete the number of trials update all the way up the tree, so that at the end of this step the top node stands at 11/22 instead of 11/21.
Answers.UserDisplayName: Philip
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T12:00:04.610Z
Answers.Text: > we know that game would have been a loss
  Thank you. How do we know that? By randomly play the game until a finish? If so, whether it means this value is not reliable for exploitation? and 0/3 means we simulated the game 3 times by randomly selection?
Answers.UserDisplayName: Wenbo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T12:01:49.857Z
Answers.Text: Yes exactly, and that is one of they key trade offs made by MCTS, as playing every permutation of every node in complex games quickly becomes computationally impossible. If you could do that you would have no need for this type of process.
Answers.UserDisplayName: Philip
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T12:04:09.250Z
Answers.Text: > Yes exactly, and that is one of they key trade offs made by MCTS.
  Bingo! This helps me a lot.
Answers.UserDisplayName: Wenbo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T12:11:08.180Z
Answers.Text: If this has helped you please mark the question answered by adding the green tick to this answer as per: https://meta.stackexchange.com/questions/106319/in-stack-overflow-how-do-i-put-the-big-green-check-to-the-answer-which-i-like-th
Answers.UserDisplayName: Philip
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T12:13:57.030Z
Answers.Text: Should I consider the step of exploring from the root node 0/0 to the far right node 0/0 as "Expansion" ?
Answers.UserDisplayName: Wenbo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T12:23:12.593Z
Answers.Text: This video with a worked example also might be helpful: https://www.youtube.com/watch?v=UXW2yZndl7U
Answers.UserDisplayName: Philip
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T09:53:15.197Z
Answers.LastActivityDate: 2019-11-19T10:06:32.493Z
Answers.LastEditDate: 2019-11-19T10:06:32.493Z
Answers.UserDisplayName: Philip
Answers.Body: <p>I also want to answer my question after watching the video that @Philip post youtube.com/watch?v=UXW2yZndl7U . But still thank @Philip 's answer which is pretty helpful.</p>
  
  <blockquote>
    <p>The definition of "leaf" node.</p>
  </blockquote>
  
  <p>The key point is <code>what tree is the host/owner of a "leaf" node</code> to this question. Through "Expansion" step, we are actually creating a tree with MCTS. The tree, the owner of a "leaf" node, should be the one that we are building, not the tree of the game state in our head (or perhaps it is too big to fill in our head, the tree of the game state actually does not exist). Then we can understand that a "leaf" node is the one, which does not have any child, in the tree that we are building.
  Once we get the answer of this question, the other questions can be answered automatically.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-20T01:13:34.433Z
Answers.LastActivityDate: 2019-11-20T01:13:34.433Z
Answers.UserDisplayName: Wenbo
Body: <p>From many blogs and this one <a href="https://web.archive.org/web/20160308070346/http://mcts.ai/about/index.html" rel="nofollow noreferrer">https://web.archive.org/web/20160308070346/http://mcts.ai/about/index.html</a>
  We know that the process of MCTS algorithm has 4 steps.</p>
  
  <blockquote>
    <ol>
    <li>Selection: Starting at root node R, recursively select optimal child nodes until a leaf node L is reached. </li>
    </ol>
  </blockquote>
  
  <p>What does leaf node L mean here? I thought it should be a node representing the terminal state of the game, or another word which ends the game. 
  If L is not a terminal node (one end state of the game), how do we decide that the selection step stops on node L? From the terms of general algorithm, a leaf node is the one that does not have any</p>
  
  <blockquote>
    <ol start="2">
    <li>Expansion: If L is a not a terminal node (i.e. it does not end the game) then create one or more child nodes and select one C. </li>
    </ol>
  </blockquote>
  
  <p>From this description I realise that obviously my previous thought incorrect. 
  Then if L is not a terminal node, it implies that L should have children, why not continue finding a child from L at the "Selection" step? 
  Do we have the children list of L at this step?<br>
  From the description of this step itself, when do we create one child node, and when do we need to create more than one child nodes? Based on what rule/policy do we select node C? </p>
  
  <blockquote>
    <ol start="3">
    <li>Simulation: Run a simulated playout from C until a result is achieved.</li>
    </ol>
  </blockquote>
  
  <p>Because of the confusion of the 1st question, I totally cannot understand why we need to simulate the game. I thought from the selection step, we can reach the terminal node and the game should be ended on node L in this path. We even do not need to do "Expansion" because node L is the terminal node.</p>
  
  <ol start="4">
  <li>Backpropagation: Update the current move sequence with the simulation result. Fine.</li>
  </ol>
  
  <p>Last question, from where did you get the answer to these questions?</p>
  
  <p>Thank you</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-18T21:07:47.150Z
Comments.Text: Hi and welcome to this community! Try asking just one question per post. You're asking too many questions here! Ask each question in its separate post
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-19T21:53:01.937Z
Comments.Text: @nbro I'm inclined to view this as a four-part question on a single subject, since the "4 steps" imply relation to each other.
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-19T21:54:58.850Z
Comments.Text: @DukeZhou We should really discourage this type of post. The OP is asking too many questions, which both reduces the future usefulness of this post and doesn't facilitate the answerer's life. Essentially, the OP is asking how MCTS works. See [https://meta.stackexchange.com/a/39224/287113](https://meta.stackexchange.com/a/39224/287113). I've not read the answer, but it looks like it doesn't address all questions. So, maybe we can reformulate this post so that it is the question to the given answer.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-19T21:56:53.847Z
Comments.Text: @nbro fair point.  And the questions are nested in the text, which increases the likelihood of various questions being missed.
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-19T21:58:05.843Z
Comments.Text: @wenbo Welcome and I'm glad you got an answer.  I'm going to leave this open b/c of that, but please do restrict to one question per post in the future--we hope to see more of you!
Comments.UserDisplayName: DukeZhou
Tags: <algorithm><monte-carlo-tree-search>
Title: How to understand the 4 steps of Monte Carlo Tree Search
UserDisplayName: Wenbo
ThreadText: # How to understand the 4 steps of Monte Carlo Tree Search
  
  (Asked by: username_0 on 2019-11-18)
  
  From many blogs and this one <https://web.archive.org/web/20160308070346/http://mcts.ai/about/index.html>
  We know that the process of MCTS algorithm has 4 steps.
  
  > 1. Selection: Starting at root node R, recursively select optimal child nodes until a leaf node L is reached.
  
  What does leaf node L mean here? I thought it should be a node representing the terminal state of the game, or another word which ends the game.
  If L is not a terminal node (one end state of the game), how do we decide that the selection step stops on node L? From the terms of general algorithm, a leaf node is the one that does not have any
  
  > 2. Expansion: If L is a not a terminal node (i.e. it does not end the game) then create one or more child nodes and select one C.
  
  From this description I realise that obviously my previous thought incorrect.
  Then if L is not a terminal node, it implies that L should have children, why not continue finding a child from L at the "Selection" step?
  Do we have the children list of L at this step?  
  From the description of this step itself, when do we create one child node, and when do we need to create more than one child nodes? Based on what rule/policy do we select node C?
  
  > 3. Simulation: Run a simulated playout from C until a result is achieved.
  
  Because of the confusion of the 1st question, I totally cannot understand why we need to simulate the game. I thought from the selection step, we can reach the terminal node and the game should be ended on node L in this path. We even do not need to do "Expansion" because node L is the terminal node.
  
  4. Backpropagation: Update the current move sequence with the simulation result. Fine.
  
  Last question, from where did you get the answer to these questions?
  
  Thank you
  
  **Tags:** algorithm, monte-carlo-tree-search
  > **Comments:**
  > **username_1**: Hi and welcome to this community! Try asking just one question per post. You're asking too many questions here! Ask each question in its separate post  
  > **username_2**: @nbro I'm inclined to view this as a four-part question on a single subject, since the "4 steps" imply relation to each other.  
  > **username_1**: @DukeZhou We should really discourage this type of post. The OP is asking too many questions, which both reduces the future usefulness of this post and doesn't facilitate the answerer's life. Essentially, the OP is asking how MCTS works. See [https://meta.stackexchange.com/a/39224/287113](https://meta.stackexchange.com/a/39224/287113). I've not read the answer, but it looks like it doesn't address all questions. So, maybe we can reformulate this post so that it is the question to the given answer.  
  > **username_2**: @nbro fair point.  And the questions are nested in the text, which increases the likelihood of various questions being missed.  
  > **username_2**: @wenbo Welcome and I'm glad you got an answer.  I'm going to leave this open b/c of that, but please do restrict to one question per post in the future--we hope to see more of you!  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2019-11-19. Score: 2 | Accepted answer
  
  Imagine a game with a very clear first move, such as a game where choosing to go first if you win a coin toss brings a clear and obvious advantage.
  
  In this situation standard MCTS does little exploration down the side of the tree that branches at the win toss > let opponent start step, as the basic simulations of the rest of the game at this split quickly show the large gain you get when always starting when you win the coin toss.
  
  As a result, you would end up with a tree with very little expansion on the side of win the toss > put your opponent in, as every simulation step you do from even the most senior nodes ends with much worse expected outcome values than the alternatives on the other side of the tree where you do the correct move of always playing first.
  
  These nodes on the side of letting your opponent start have *huge* potential sub trees (as the whole game would still need to be played out if your opponent started), but would have very little searching down them. As a result, on this side of the tree, you would have many leaf nodes with large (but as yet unexplored, outside of the basic, early simulations down that side) sub trees that you *could* search if you modified the exploration vs exploration algorithm.
  
  As a basic example, take the 0/3 node at the far right on level one of the wiki example below, which would get much less attention than the much more promising 7/10 and 3/8 nodes, despite having potentially many subsequent children it *could* explore. If you took this node as your L node, you would expand it's children that you have not yet searched, and thus find out more about why this side of the tree is bad and update our now more granular probabilities accordingly, just as it does for the 3/3 node here:
  
  [![enter image description here](https://i.sstatic.net/A5vw0.png)](https://i.sstatic.net/A5vw0.png)
  
  > **Comments:**
  > **username_0**: Thank you @Philip for your answer. As you post the diagram here, let me ask my questions in other words based on your diagram. The tree on the most left has 4 levels, there are 2 nodes on the bottom of the tree, 2/3 and 3/3.   How the values 2/3 and 3/3 are calculated?  Whether there are more levels under 2/3 and 3/3 are now shown, what nodes are not shown here? Whether the nodes from 2/3 to the terminal nodes (an end state of the game)  are not shown? Otherwise, how is 2 calculated?.  And why are these nodes not shown?  Why does the step "Selection" stop on node 2/3 and 3/3?  
  > **username_0**: Don't know why I can't edit my last comment. For the question > How the values 2/3 and 3/3 are calculated? I meant without deeper search under 2/3 and 3/3, how the values of the 2 nodes are obtained. I understand the meaning of 2 and 3.  
  > **username_3**: These would be created using some kind of simulation logic. This could range from just making random moves through to using the current best AI to play itself down until a finish. Those values are what the score has been so far using that simulation logic, and thus represent the best approximation of the current expected value of that branch of the game using that simulation logic.  
  > **username_0**: Say initially, there is only one root node which should be 0/0, then how this node can be filled as 11/21? By simulation logic of step "Simulation"? A simple approach for this step is selecting random action until a finish, can a random action ends with 11/21? I definitely misunderstood something.  
  > **username_3**: At the start of the tree it was 0/0. The first iteration will have picked one of the three possible children (here, nodes now at 7/10, 3/8 and 0/3), and played the game out from there and recorded the result. Say the first child was the node that is now 0/3, we know that game would have been a loss, so the first node would now be 0/1 and the far right node would also be 0/1. As each trial repeats this process updates until we reach 21 trials and you have the graph above at step one.  
  > **username_3**: Also note how at step four above when the simulation is complete the number of trials update all the way up the tree, so that at the end of this step the top node stands at 11/22 instead of 11/21.  
  > **username_0**: > we know that game would have been a loss Thank you. How do we know that? By randomly play the game until a finish? If so, whether it means this value is not reliable for exploitation? and 0/3 means we simulated the game 3 times by randomly selection?  
  > **username_3**: Yes exactly, and that is one of they key trade offs made by MCTS, as playing every permutation of every node in complex games quickly becomes computationally impossible. If you could do that you would have no need for this type of process.  
  > **username_0**: > Yes exactly, and that is one of they key trade offs made by MCTS. Bingo! This helps me a lot.  
  > **username_3**: If this has helped you please mark the question answered by adding the green tick to this answer as per: https://meta.stackexchange.com/questions/106319/in-stack-overflow-how-do-i-put-the-big-green-check-to-the-answer-which-i-like-th  
  > **username_0**: Should I consider the step of exploring from the root node 0/0 to the far right node 0/0 as "Expansion" ?  
  > **username_3**: This video with a worked example also might be helpful: https://www.youtube.com/watch?v=UXW2yZndl7U  
  
  ---
  
  ### Answer by username_0 on 2019-11-20. Score: 0
  
  I also want to answer my question after watching the video that @Philip post youtube.com/watch?v=UXW2yZndl7U . But still thank @Philip 's answer which is pretty helpful.
  
  > The definition of "leaf" node.
  
  The key point is `what tree is the host/owner of a "leaf" node` to this question. Through "Expansion" step, we are actually creating a tree with MCTS. The tree, the owner of a "leaf" node, should be the one that we are building, not the tree of the game state in our head (or perhaps it is too big to fill in our head, the tree of the game state actually does not exist). Then we can understand that a "leaf" node is the one, which does not have any child, in the tree that we are building.
  Once we get the answer of this question, the other questions can be answered automatically.
  
  
  ---
  
  