Monte Carlo Tree Search (MCTS)

• is a heuristic search algorithm for some kinds of decision processes, most notably those employed in game play

Algorithm

Steps

1. selection - selecting good child nodes, starting from the root node R, that represent states leading to a better overall outcome (win)
2. expansion - if L is not a terminal node (i.e. it does not end the game), then create one or more child nodes and select one (C)
3. simulation (rollout) - run a simulated play-out from C until a result is achieved
4. back-propagation - update the current move sequence with the simulation result