Synonyms Monte-Carlo Tree Search, UCT Definition

The Monte-Carlo method in games and puzzles consists in playing random games called playouts in order to estimate the value of a position. The method is related to learning since the algorithm dynamically learns which moves are good and which moves are bad as more playouts are played. The learning is achieved by keeping statistics on the outcomes of the random games that started with a move. This algorithm is strongly linked with the area of machine learning named reinforcement learning. It has benefited from research on the multiarmed bandit problem in the area of machine learning (Auer et al. 2002). The method is related to learning since the algorithm starts learning a position from scratch each time it has to play: it learns the moves that are good for any given position. When there are no good heuristics for a problem, Monte-Carlo methods can learn to solve an instance of the problem. Consider for example the game of Go, this is a difficult problem for artificial intelligence since evaluating a position with rules and knowledge is very difficult, moreover there are more than 250 possible moves on average and it is necessary to look multiple moves ahead, therefore there is a combinatorial explosion of the number of positions to look at. On the other hand, in the game of Go, it is very simple to program