Monte Carlo Tree Search: A Review of Recent Modifications and Applications

Monte Carlo Tree Search (MCTS) is a decision-making algorithm that consists in searching large combinatorial spaces represented by trees. In such trees, nodes denote states, also referred to as configurations of the problem, whereas edges denote transitions (actions) from one state to another. MCTS has been originally proposed in the work by Kocsis and Szepesvári (2006) and by Coulom (2006), as an algorithm for making computer players in Go. It was quickly called a major breakthrough (Gelly et al., 2012) as it allowed for a leap from 14 kyu, which is an average amateur level, to 5 dan, which is considered an advanced level but not professional yet. Before MCTS, bots for combinatorial games had been using various modifications of the min-max alpha-beta pruning algorithm (Junghanns, 1998) such as MTD(f) (Plaat, 2014) and hand-crafted heuristics. In contrast to them, MCTS algorithm is at its core aheuristic, which means that no additional knowledge is required other than just rules of a game (or a problem, generally speaking). However, it is possible to take advantage of heuristics and include them in the MCTS approach to make it more efficient and improve its convergence. Moreover, the given problem often tends to be so complex, from the combinatorial point of view, that some form of external help, e.g.