Monte-Carlo Tree Search Parallelisation for Computer Go

Authors: F. van Niekerk, S. Kroon, G.J. van Rooyen and C.P. Inggs
Published in proceedings of SAICSIT’12.
DOI: 10.1145/2389836.2389852


Parallelisation of computationally expensive algorithms, such as Monte-Carlo Tree Search (MCTS), has become increasingly important in order to increase algorithm performance by making use of commonplace parallel hardware.

Oakfoam, an MCTS-based Computer Go player, was extended to support parallel processing on multi-core and cluster systems. This was done using tree parallelisation for multi-core systems and root parallelisation for cluster systems.

Multi-core parallelisation scaled linearly on the tested hardware on 9×9 and 19×19 boards when using the virtual loss modification. Cluster parallelisation showed poor results on 9×9 boards, but scaled well on 19×19 boards, where it achieved a four-node ideal strength increase on eight nodes.

Due to this work, Oakfoam is currently one of only two open-source MCTS-based Computer Go players with cluster parallelisation, and the only one using the Message Passing Interface (MPI) standard.