MCTS [1]} incrementally builds an asymmetric game tree balanced towards to most promising parts of the game state space. It uses multiple iterations of four steps: first, it navigates through the tree, using a tree policy, until reaching a node which is not yet fully expanded; next, it adds a new random child of this node to the tree; it then performs a Monte Carlo rollout from the new child (randomly sampling actions until the end of the game or a predetermined depth \(L=10\) ); the state reached at the end of the rollout is evaluated with a heuristic function, and this score is backed up through all the nodes visited during the iteration. The process is repeated until the budget is exhausted, and the most visited child of the root is chosen as the action to play.
