Monte Carlo Tree Search

Summary

Monte Carlo Tree Search is an iterative Reinforcement learning algorithm that finds optimal solutions in a highly multidimensional search space. It is a heuristic in that it does not require any knowledge beyond the “rules of the game”.

Details

The algorithm proceeds in four steps:

1. Selection: a child node is selected with the highest upper confidence bound applied to trees ($UCT$):

   $$UCT=\frac{w_i}{n_i}+C\sqrt{\frac{\ln N_i}{n_i}}$$

   $w_i$: Score, or number of wins from this node $n_i$: Number of simulations from this node $N_i$: Total number of simulations $C$: A constant that is chosen empirically (usually set to $\sqrt{2}$)

2. Expansion: a new child node is added to the tree at this optimally reached point

3. Simulation (AKA rollout): the remainder of the process or game is played out

4. Backpropagation: updating score of all nodes to the top of the tree with the result

Figures

Ref geeksforgeeks.com