Monte Carlo tree search (MCTS) is a general approach to solving game problems, playing a central role in Google DeepMind's AlphaZero and its predecessor AlphaGo, which famously 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 game rules), AlphaZero defeated not only its ancestors in Go but also the best computer programs in chess (Stockfish) and shogi (Elmo). In this tutorial, we provide an introduction to MCTS, including a review of its history and relationship to a more general simulation-based algorithm for Markov decision processes (MDPs) published in a 2005 Operations Research article; a demonstration of the basic mechanics of the algorithms via decision trees and the game of tic-tac-toe; and its use in AlphaGo and AlphaZero.
Description
MONTE CARLO TREE SEARCH: A TUTORIAL | IEEE Conference Publication | IEEE Xplore
%0 Conference Paper
%1 8632344
%A Fu, M. C.
%B 2018 Winter Simulation Conference (WSC)
%D 2018
%K 2018 mcts tutorial
%P 222-236
%R 10.1109/WSC.2018.8632344
%T Monte Carlo tree search: A tutorial
%U https://ieeexplore.ieee.org/abstract/document/8632344
%X Monte Carlo tree search (MCTS) is a general approach to solving game problems, playing a central role in Google DeepMind's AlphaZero and its predecessor AlphaGo, which famously 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 game rules), AlphaZero defeated not only its ancestors in Go but also the best computer programs in chess (Stockfish) and shogi (Elmo). In this tutorial, we provide an introduction to MCTS, including a review of its history and relationship to a more general simulation-based algorithm for Markov decision processes (MDPs) published in a 2005 Operations Research article; a demonstration of the basic mechanics of the algorithms via decision trees and the game of tic-tac-toe; and its use in AlphaGo and AlphaZero.
@inproceedings{8632344,
abstract = {Monte Carlo tree search (MCTS) is a general approach to solving game problems, playing a central role in Google DeepMind's AlphaZero and its predecessor AlphaGo, which famously 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 game rules), AlphaZero defeated not only its ancestors in Go but also the best computer programs in chess (Stockfish) and shogi (Elmo). In this tutorial, we provide an introduction to MCTS, including a review of its history and relationship to a more general simulation-based algorithm for Markov decision processes (MDPs) published in a 2005 Operations Research article; a demonstration of the basic mechanics of the algorithms via decision trees and the game of tic-tac-toe; and its use in AlphaGo and AlphaZero.},
added-at = {2021-03-13T07:12:20.000+0100},
author = {{Fu}, M. C.},
biburl = {https://www.bibsonomy.org/bibtex/2c85b58926f6ff11a033831892c0087d1/analyst},
booktitle = {2018 Winter Simulation Conference (WSC)},
description = {MONTE CARLO TREE SEARCH: A TUTORIAL | IEEE Conference Publication | IEEE Xplore},
doi = {10.1109/WSC.2018.8632344},
interhash = {1664ecaad9f3efac81255fd3ad055a5d},
intrahash = {c85b58926f6ff11a033831892c0087d1},
issn = {1558-4305},
keywords = {2018 mcts tutorial},
month = dec,
pages = {222-236},
timestamp = {2021-03-13T07:13:13.000+0100},
title = {Monte Carlo tree search: A tutorial},
url = {https://ieeexplore.ieee.org/abstract/document/8632344},
year = 2018
}