Author: Francois van Niekerk
Supervisors: Dr. Gert-Jan van Rooyen, Dr. Steve Kroon, Dr. Cornelia Inggs
Final Year Project of Bachelors for Stellenbosch University
Abstract
Modern processors are making increasing use of parallel hardware to increase processing power. This has given increasing importance to parallelisation of computationally expensive algorithms, such as Monte-Carlo Tree Search (MCTS), in order to make use of the parallel hardware.
This project implemented pondering and parallelised an existing MCTS implementation for Computer Go on multi-core and cluster systems. Tree parallelisation was used for multi-core systems and root parallelisation was used for cluster systems.
Pondering functioned as designed and provided a strength increase in the order of 60 Elo. Multi-core parallelisation scaled close to perfectly on the tested hardware on 9×9 and 19×19 with virtual loss. Cluster parallelisation showed disappointing results on 9×9, but succeeded to scale well on 19×19 were it achieved a four core ideal strength increase on eight cores.
This project has implemented pondering and parallelisation techniques that enable an MCTS implementation to take advantage of parallel hardware.