The Monte Carlo tree search algorithm
The Monte Carlo Tree Search (MCTS) is a planning algorithm and a way of making optimal decisions in case of artificial narrow intelligence problems. MCTS works on a planning ahead kind of approach to solve the problem.
The MCTS algorithm gained importance after earlier algorithms such as minimax and game trees failed to show results with complex problems. So what makes the MCTS different and better than past decision making algorithms such as minimax?
Let's first discuss what minimax is.
Minimax and game trees
Minimax was the algorithm used by IBM Deep Blue to beat the world champion Gary Kasparov on February 10, 1996 in a chess game. This win was a very big milestone back then. Both minimax and game trees are directed graphs, where each node represents the game states, that is, position in the game as shown in the following diagram of a game of tic-tac-toe:
Game tree for tic-tac-toe. The top node represents the start position of the game. Following down...
