How to understand the 4 steps of Monte Carlo Tree Search

Question

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

Answer 1

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:

Answer 2

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.