Home * Search * Monte-Carlo Tree Search

Monte Carlo Tree Search, (Monte-Carlo Tree Search, MCTS)
is a Best-First search algorithm based on random playouts. In conjunction with UCT (Upper Confidence bounds applied to Trees) Monte-Carlo Tree Search has yielded in a breakthrough in Computer Go [1], and is also successful in Amazons [2] [3], Lines of Action [4], Havannah [5], Hex [6], Checkers [7] and other Games with some difficulties in position evaluation, but (so far) not for Chess [8] [9].

MCTS is based on randomized explorations of the search space. Using the results of previous explorations, the algorithm gradually grows a game tree in memory, and successively becomes better at accurately estimating the values of the most promising moves [10].
Edvard Munch - At the Roulette Table in Monte Carlo [11]

Four Phases

MCTS consists of four strategic phases, repeated as long as there is time left [12] :
  1. In the Selection phase the tree is traversed from the root node until it selects a leaf node that is not added to the tree yet
  2. The Expansion strategy adds the leaf node to the tree
  3. The Simulation strategy plays moves in self-play until the end of the game. The result is either 1, 0 ,-1
  4. The Backpropagation strategy propagates the results through the tree
Steps of Monte Carlo Tree Search [13]

Pure Monte-Carlo search

Pure Monte-Carlo search with parameter T means that for each feasible move T random games are generated. The move with the best average score is played. A game is called “Monte Carlo perfect” when this procedure converges to perfect play for each position, when T goes to infinity. However, with limited time per move, increasing T does not guarantee to find a better move [14].


UCT (Upper Confidence bounds applied to Trees) deals with the flaw of Monte-Carlo Tree Search, when a program may favor a losing move with only one or a few forced refutations, but due to the vast majority of other moves provides a better random playout score than other, better moves [15].

See also



1990 ...

2000 ...

2005 ...


2010 ...


2015 ...


Forum Posts

2010 ...

2015 ...

External Links

Monte Carlo Tree Search

Monte Carlo Misc


  1. ^ Rémi Coulom (2009). The Monte-Carlo Revolution in Go. JFFoS'2008: Japanese-French Frontiers of Science Symposium, slides as pdf
  2. ^ Julien Kloetzer, Hiroyuki Iida, Bruno Bouzy (2007). The Monte-Carlo approach in Amazons. CGW 2007
  3. ^ Richard J. Lorentz (2008). Amazons Discover Monte-Carlo. CG 2008
  4. ^ Mark Winands and Yngvi Björnsson (2009). Evaluation Function Based Monte-Carlo LOA. pdf
  5. ^ Richard J. Lorentz (2010). Improving Monte-Carlo Tree Search in Havannah. CG 2010
  6. ^ Broderick Arneson, Ryan Hayward, Philip Henderson (2010). Monte Carlo Tree Search in Hex. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 2, No. 4, pdf
  7. ^ UCT surprise for checkers ! by Daniel Shawul, CCC, March 25, 2011
  8. ^ Raghuram Ramanujan, Ashish Sabharwal, Bart Selman (2010). On Adversarial Search Spaces and Sampling-Based Planning. ICAPS 2010
  9. ^ Oleg Arenz (2012). Monte Carlo Chess. B.Sc. thesis, Darmstadt University of Technology, advisor Johannes Fürnkranz, pdf
  10. ^ Guillaume Chaslot, Mark Winands, Jaap van den Herik (2008). Parallel Monte-Carlo Tree Search. CG 2008, pdf
  11. ^ Edvard Munch, At the Roulette Table in Monte Carlo, 1893, Edvard Munch from Wikipedia
  12. ^ Guillaume Chaslot, Mark Winands, Jaap van den Herik (2008). Parallel Monte-Carlo Tree Search. CG 2008, pdf
  13. ^ Steps of Monte-Carlo Tree Search by Mciura, March 31, 2013, Wikimedia Commons, Monte Carlo tree search from Wikipedia
  14. ^ Ingo Althöfer (2011). On Board-Filling Games with Random-Turn Order and Monte Carlo Perfectness. Advances in Computer Games 13
  15. ^ Levente Kocsis, Csaba Szepesvári (2006). Bandit based Monte-Carlo Planning ECML-06, LNCS/LNAI 4212, pp. 282-293. introducing UCT, pdf
  16. ^ Jeff Rollason (2015). Mixing the Immiscible - MCTS and evaluation. AI Factory, October 2015
  17. ^ Monte Carlo in LOA by Mark Watkins, Open Chess Forum, December 30, 2010
  18. ^ The Settlers of Catan from Wikipedia
  19. ^ Blokus Duo from Wikipedia
  20. ^ NoGo (ICGA Tournaments)
  21. ^ Ms. Pac-Man from Wikipedia
  22. ^ Scotland Yard (board game) from Wikipedia
  23. ^ Re: MC methods by Daniel Shawul, CCC, April 13, 2013
  24. ^ Crossings from Wikipedia
  25. ^ Epaminondas from Wikipedia
  26. ^ 7 Wonders (board game) from WIkipedia
  27. ^ Guillaume Chaslot, Mark Winands, Jos Uiterwijk, Jaap van den Herik, Bruno Bouzy (2008). Progressive Strategies for Monte-Carlo Tree Search. New Mathematics and Natural Computation, Vol. 4, No. 3, pdf
  28. ^ Dap Hartmann (2017). Let's Catch the Train to Monte-Carlo. ICGA Journal, Vol. 39, No. 1
  29. ^ David Silver, Gerald Tesauro (2009). Monte-Carlo Simulation Balancing. ICML 2009, pdf

What links here?

Up one level