Monte Carlo tree search

• 1. Random Roots In The 1940s

  ›

  The Monte Carlo method emerged in the 1940s as a way to solve deterministic problems using random sampling. Mathematicians needed a new approach for complex calculations that traditional methods could not handle efficiently. This technique relied on generating many random numbers to estimate outcomes rather than solving equations directly. Early applications focused on physics and nuclear research where exact solutions were impossible to derive by hand. By the late 1980s researchers began applying these ideas to game playing software. Bruce Abramson published his PhD thesis in 1987 describing how to combine minimax search with expected-outcome models based on random playouts. He tested this approach on tic-tac-toe and later applied it to Othello and chess programs. His work showed that random simulations could provide precise and domain-independent evaluations without needing static evaluation functions. Other teams followed suit in automated theorem proving during 1989. W. Ertel, J. Schumann, and C. Suttner improved exponential search times by integrating Monte Carlo techniques into their algorithms. These early experiments laid the groundwork for future developments in heuristic search.

  67

• 2. Four Steps To A Decision

  ›

  A single round of Monte Carlo tree search consists of four distinct steps repeated until time runs out. Selection starts at the root node representing the current game state and follows child nodes down to an unvisited leaf. Expansion creates one or more new child nodes if the selected leaf does not end the game decisively. Simulation completes a random playout from that node all the way to a final result like win loss or draw. Backpropagation updates statistics along the path from the leaf back to the root using the simulation outcome. Each node tracks wins divided by total simulations to estimate value over many iterations. If white loses a simulation every node along the selection path increments its simulation count but only black nodes receive credit for wins. The process repeats as long as the allotted time remains for making a move. Programs choose the move with the highest number of simulations when time expires. Pure Monte Carlo Game Search applies this same procedure to any finite game position without needing explicit evaluation functions. It converges to optimal play in board filling games with random turn order such as Hex.

  3436

• 3. The UCT Breakthrough In Go

  ›

  Rémi Coulom coined the term Monte Carlo tree search in 2006 while applying the Monte Carlo method to game-tree search. That same year Levente Kocsis and Csaba Szepesvári developed the Upper Confidence bounds applied to Trees algorithm known as UCT. S. Gelly et al. implemented UCT in their program MoGo which achieved dan level performance on 9x9 boards by 2008. Fuego began winning against strong amateur players on 9x9 Go later that year. The UCT formula balances exploitation of high win rates with exploration of moves having few simulations. It uses an expression where the first component reflects average win ratio and the second encourages trying untested options. Most contemporary implementations trace their roots back to Adaptive Multi-stage Sampling introduced by Chang et al. in 2005. This earlier work explored UCB-based exploration within Markov Decision Processes and became the main seed for UCT. By January 2012 the Zen program won a three-to-one match against an amateur 2-dan player on a full 19x19 board. These developments marked a turning point where random sampling combined with smart selection could challenge human expertise.

  12133339

• 4. Neural Networks Meet Search

  ›

  Google Deepmind released AlphaGo in October 2015 becoming the first computer program to beat a professional human Go player without handicaps on a standard 19x19 board. In March 2016 AlphaGo defeated Lee Sedol four games to one earning an honorary 9-dan title. The system used Monte Carlo tree search together with artificial neural networks for both policy and value estimation. This combination gave it efficiency far surpassing previous programs that relied solely on random playouts. DeepMind's AlphaZero later replaced the simulation step entirely with evaluations based on neural network outputs. Leela Chess Zero adopted similar methods for chess and now ranks among leading chess playing programs. The integration of deep learning architectures transformed machine intelligence capabilities across multiple domains including strategy video games like Total War: Rome II. Applications extended beyond traditional board games to include real-time titles such as Ms. Pac-Man and Fable Legends. Nondeterministic games like poker Magic: The Gathering and Settlers of Catan also benefited from these hybrid approaches. The fusion of search algorithms with pattern recognition represented a significant milestone in artificial general intelligence research.

  11750

• 5. Strengths And Hidden Traps

  ›

  Monte Carlo tree search offers advantages over alpha-beta pruning especially in games with high branching factors. It does not require an explicit evaluation function since implementing game mechanics alone suffices to explore the search space. The algorithm grows asymmetrically concentrating on promising subtrees rather than expanding uniformly. However certain positions contain moves appearing strong superficially but leading to loss through subtle lines of play. These trap states demand thorough analysis which MCTS may miss due to selective node expansion policies. Experts believe this limitation contributed to AlphaGo losing its fourth game against Lee Sedol. The search attempts to prune sequences deemed less relevant yet sometimes critical outcomes fall off the radar entirely. In some cases specific lines of play prove significant but remain overlooked when the tree prunes branches prematurely. Pure Monte Carlo Game Search converges only in so-called Monte Carlo Perfect games while basic versions struggle elsewhere. Despite these drawbacks the method achieves better results than classical algorithms in many complex scenarios requiring deep lookahead.

  4440

• 6. Optimizing Speed And Scale

  ›

  Various modifications shorten search time by incorporating domain-specific expert knowledge or automated tuning methods. Light playouts use random moves while heavy playouts apply heuristics influenced by previous results or expert patterns. Paradoxically playing suboptimally during simulations sometimes makes programs stronger overall. RAVE Rapid Action Value Estimation reduces exploratory phases in games where move permutations lead to identical positions. This technique stores statistics not just for immediate children but also for all playouts containing a given move anywhere below that node. Progressive bias adds an element to the UCB1 formula using heuristic scores to adjust selection frequency. Automated methods tune parameters to maximize win rates across different game types. Parallel execution allows concurrent processing through leaf root or tree parallelization strategies. Leaf parallelization runs multiple playouts from one leaf simultaneously. Root parallelization builds independent trees and combines their root-level branches before choosing a move. Tree parallelization constructs the same tree concurrently protecting data with mutexes or non-blocking synchronization mechanisms. These optimizations enable real-time decision making even under tight computational constraints.

  2734