How does the MCTS tree look like?

Question

I have come across the Monte Carlo tree search (MCTS) algorithm, but I can't find what the tree should look like. For example, does it still represent a minimax process, i.e. player 1 from the root has its child nodes as probabilities of moves, then from those child nodes, the next move is player 2, etc.? Is this how the tree looks like, so when we backpropagate we update only the winning player nodes?

Answer 1

In a MCTS (Monte Carlo tree search) the resulting tree is expanded by two policies:

• tree-policy (selects next and unknown child nodes by a exploration-exploitation tradeoff)
• default policy (selects known child nodes till terminal state e.g. with random uniform moves).

The term terminal state is often considered to be the end a tree. If you consider designing an agent with MCTS that is able to play chess, then the terminal state would a win, lose or draw. One game like this is called a playout (sometimes also roll-out). The main concept of MCTS relies on repeating this playouts many times and updating the tree according to the scores. The tree is built up in an incremental and asymmetric manner.

Imagine designing a chess-playing agent. The tree, or rather how the tree is built up can be like this:

• Root Node: Starting with an empty board
• Child Nodes: Board configuration after each move (opponent and agent)
• Selection of Child Nodes: If the opponent is a human, then the selection of child nodes is performed by his/her own strategy. The agent is selecting moves according to a policy.
• Terminal State: Score of the game (win/lose/draw).

So after each move (opponent or agent) the current child node/root node is expanded by the resulting child nodes.

If you want to dive deeper into MCTS, then I would recommend to take a look at A Survey of Monte Carlo Tree Search Methods.