In recent years there has been much interest in the Monte Carlo tree search algorithm, a new, adaptive, randomized optimization algorithm. In fields as diverse as Artificial Intelligence, Operations Research, and High Energy Physics, research has established that Monte Carlo tree search can find good solutions without domain dependent heuristics. However, practice shows that reaching high performance on large parallel machines is not so successful as expected. This paper proposes a new method for parallel Monte Carlo tree search based on the pipeline computation pattern.
Tree parallelization: For shared memory machines, tree parallelization is a suitable method. It is used in Fuego , an open source Go program @cite_3 . In tree parallelization one MCTS tree is shared among several threads that are performing simultaneous searches @cite_14 . It is shown in @cite_14 that the playout speedup of tree parallelization with does not scale perfectly for up to 16 threads. The main challenge is the use of the data locks to prevent data corruption. Moreover, it is shown in @cite_1 that a lock-free implementation of this algorithm provides better scaling than a locked approach. @cite_1 such a lock-free tree parallelization for MCTS is proposed. They intentionally ignored rare faulty updates inside the tree and studied the scalability of the algorithm for up to 8 threads. Baudi s et al @cite_9 reported the performance of a lock-free tree parallelization with virtual loss for a Go program. The strength-speedup in only self-play experiments is good up to 16 cores but the improvement drops after 22 cores.
@cite_9 @cite_14 @cite_1 @cite_3
202421935 1528097685 2101101673
We present a state of the art implementation of the Monte Carlo Tree Search algorithm for the game of Go. Our Pachi software is currently one of the strongest open source Go programs, competing at the top level with other programs and playing evenly against advanced human players. We describe our implementation and choice of published algorithms as well as three notable original improvements: (1) an adaptive time control algorithm, (2) dynamic komi, and (3) the usage of the criticality statistic. We also present new methods to achieve efficient scaling both in terms of multiple threads and multiple machines in a cluster. With the recent success of Monte-Carlo tree search algorithms in Go and other games, and the increasing number of cores in standard CPUs, the efficient parallelization of the search has become an important issue. We present a new lock-free parallel algorithm for Monte-Carlo tree search which takes advantage of the memory model of the IA-32 and Intel-64 CPU architectures and intentionally ignores rare faulty updates of node values. We show that this algorithm significantly improves the scalability of the Fuego Go program. FUEGO is both an open-source software framework and a state-of-the-art program that plays the game of Go. The framework supports developing game engines for full-information two-player board games, and is used successfully in a substantial number of projects. The FUEGO Go program became the first program to win a game against a top professional player in 9 × 9 Go. It has won a number of strong tournaments against other programs, and is competitive for 19 × 19 as well. This paper gives an overview of the development and current state of the FUEGO project. It describes the reusable components of the software framework and specific algorithms used in the Go engine.