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?
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.
1$\begingroup$ Some small corrections: default policy does not really select nodes, but states (or even more accurately, actions); typically no nodes are added to the tree for the states encountered during rollout (except for one Expansion at start of rollout/end of Selection). If the opponent is a human, of course the MCTS during its tree search still makes decisions "for the human" while traversing the tree. Just in the "real game" you need to wait for the human, but in the search tree process you don't. In Chess, the initial state (root node) is not an empty board :) $\endgroup$– Dennis Soemers ♦Oct 29, 2020 at 19:05