Parallel Monte-Carlo Tree Search for HPC Systems and its Application to Computer Go

Lars Schäfers

ISBN 978-3-8325-3748-7
147 Seiten, Erscheinungsjahr: 2014
Preis: 40.00 €
Parallel Monte-Carlo Tree Search for HPC Systems and its Application to Computer Go

Monte-Carlo Tree Search (MCTS) is a class of simulation-based search algorithms. It brought about great success in the past few years regarding the evaluation of deterministic two-player games such as the Asian board game Go.

In this thesis, we present a parallelization of the most popular MCTS variant for large HPC compute clusters that efficiently shares a single game tree representation in a distributed memory environment and scales up to 128 compute nodes and 2048 cores. It is hereby one of the most powerful MCTS parallelizations to date.

In order to measure the impact of our parallelization on the search quality and remain comparable to the most advanced MCTS implementations to date, we implemented it in a state-of-the-art Go engine Gomorra, making it competitive with the strongest Go programs in the world.

We further present an empirical comparison of different Bayesian ranking systems when being used for predicting expert moves for the game of Go and introduce a novel technique for automated detection and analysis of evaluation uncertainties that show up during MCTS searches.