Monte-Carlo Tree Search Parallelisation for Computer Go
Date
2012
Journal Title
Journal ISSN
Volume Title
Publisher
ACM Publishers, NY, USA
Abstract
ENGLISH ABSTRACT: 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 9x9 and 19x19 boards when using the virtual loss
modi cation. Cluster parallelisation showed poor results
on 9x9 boards, but scaled well on 19x19 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.
Description
SAICSIT’12, October 01–03 2012, Pretoria, South Africa
South African Institute of Computer Scientists and Information Technologists
South African Institute of Computer Scientists and Information Technologists
Keywords
Parallelizing compilers, Algorithms, Oakfoam, Monte Carlo method