A Tutorial for Monte Carlo Tree Search in AI
Michael C. Fu, Daniel Qiu, Jie Xu · 2024
This tutorial serves as an introductory guide to Monte Carlo tree search (MCTS), a versatile methodology for sequential decision making under uncertainty through stochastic/Monte Carlo simulation. MCTS gained notoriety from its pivotal role in Google DeepMind's AlphaZero and AlphaGo, hailed as major breakthroughs in artificial intelligence (AI) due to AlphaGo defeating the reigning human world Go champion Lee Sedol in 2016 and the world's top-ranked Go player Ke Jie in 2017. AlphaZero, without requiring any domain-specific knowledge beyond the game rules (tabula rasa), achieved remarkable success by surpassing previous benchmarks in Go and outperforming leading AI opponents in chess (Stockfish) and shogi (Elmo) after just 24 hours of MCTS-driven reinforcement learning. We demonstrate the building blocks of MCTS and its performance through decision trees and the game of Othello, and provide an empirical simulation study for the latter.