Monte Carlo Tree Search

Monte Carlo Tree Search (MCTS) is a method for making optimal decisions in artificial intelligence (AI) problems, typically move planning in combinatorial games. It combines the generality of random simulation with the precision of tree search.

The basic MCTS algorithm is simple: a search tree is built, node by node, according to the outcomes of simulated playouts. The process can be broken down into the following steps.

1. Selection:
Starting at root node R, recursively select optimal child nodes (explained below) until a leaf node L is reached.

2. Expansion:
If L is a 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:
Run a simulated playout from C until a result is achieved.

4. Backpropagation:Update the current move sequence with the simulation result.

In general, Monte Carlo methods (or Monte Carlo experiments) are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. Their essential idea is using randomness to solve problems that might be deterministic in principle.

adapted from: http://mcts.ai/about/index.html

visit this website to gain more knowledge about this subject.