1
$\begingroup$

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

  1. 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?

  1. 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.

  1. 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

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – nbro Nov 18 '19 at 21:07
  • $\begingroup$ @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. $\endgroup$ – DukeZhou Nov 19 '19 at 21:53
  • $\begingroup$ @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. 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. $\endgroup$ – nbro Nov 19 '19 at 21:54
  • $\begingroup$ @nbro fair point. And the questions are nested in the text, which increases the likelihood of various questions being missed. $\endgroup$ – DukeZhou Nov 19 '19 at 21:56
  • $\begingroup$ @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! $\endgroup$ – DukeZhou Nov 19 '19 at 21:58
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Wenbo Nov 19 '19 at 10:50
  • $\begingroup$ 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. $\endgroup$ – Wenbo Nov 19 '19 at 11:09
  • $\begingroup$ 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. $\endgroup$ – Philip Nov 19 '19 at 11:22
  • $\begingroup$ 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. $\endgroup$ – Wenbo Nov 19 '19 at 11:45
  • $\begingroup$ 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. $\endgroup$ – Philip Nov 19 '19 at 11:50
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.