The game tree is a recursive data structure, therefore after choosing the best move, you end up in a child node which is, in fact, a root node for its subtree. Therefore you can think of a game as a sequence of “the most promising next move” problems represented by a game tree every time (with different root node). Very often in practice, you do not have to remember the path leading to your current state, as it is not a concern in a current game state.
MCTS generally consists of four strategic steps, repeated as long as there is time left. The steps are as follows.
In the selection mode, the tree is traversed from the root node until we reach a node E, where we select a position that is not added to the tree yet.
Next, during the play-out step moves are played in self-play until the end of the game is reached. The result R of this “simulated” game is +1 in case of a win for Black (the first player in LOA), 0 in case of a draw, and −1 in case of a win for White.
Subsequently, in the expansion stepchildren of E are added to the tree.
Finally, R is propagated back along the path from E to the root node in the backpropagation step. When time is up, the move played by the program is the child of the root with the highest value.
For a better understanding of the algorithm you can refer the following link:
https://int8.io/monte-carlo-tree-search-beginners-guide/
Learn more about Artificial Intelligence in this insightful artificial intelligence online course now!
Back