Monte-Carlo Tree Search Parallelisation

This talk was presented at the International Go Symposium in Black Mountain, North Carolina on 4-5 August 2012.

Author: Francois van Niekerk
Collaborators: Steve Kroon, Gert-Jan van Rooyen, Cornelia Inggs


Due to physical constraints, parallel hardware, such as multi-core and cluster systems (sometimes referred to as supercomputers), has become increasingly commonplace. In order to take advantage of this hardware, we parallelise algorithms such as Monte-Carlo Tree Search (MCTS), the dominant algorithm for Computer Go.

In this talk, the general workings of MCTS and the main approaches to MCTS parallelisation are presented. Results from an implementation of tree parallelisation for multi-core systems and root parallelisation for cluster systems are discussed. Finally, new developments in MCTS parallelisation are discussed and we consider the path forward.