A Tutorial Introduction to Monte Carlo Tree Search
Michael C. Fu · 2020
This tutorial provides an introduction to Monte Carlo tree search (MCTS), which is a general approach to solving sequential decision-making problems under uncertainty using stochastic (Monte Carlo) simulation. MCTS is most famous for its role in Google DeepMind's AlphaZero, the recent successor to AlphaGo, which defeated the (human) world Go champion Lee Sedol in 2016 and world #1 Go player Ke Jie in 2017. Starting from scratch without using any domain-specific knowledge (other than the rules of the game), AlphaZero was able to defeat not only its predecessors in Go but also the best AI computer programs in chess (Stockfish) and shogi (Elmo), using just 24 hours of training based on MCTS and reinforcement learning. We demonstrate the basic mechanics of MCTS via decision trees and the game of tic-tac-toe.