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.
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.