Structured Parallel Programming for Monte Carlo Tree Search
This work addresses performance bottlenecks in parallel MCTS for applications like game AI or optimization, though it appears incremental as it builds on existing parallel MCTS techniques.
The paper tackles the problem of parallelizing Monte Carlo Tree Search (MCTS) by introducing a new algorithm based on the pipeline pattern and a lock-free tree data structure, resulting in improved scalability to higher core counts compared to existing methods.
In this paper, we present a new algorithm for parallel Monte Carlo tree search (MCTS). It is based on the pipeline pattern and allows flexible management of the control flow of the operations in parallel MCTS. The pipeline pattern provides for the first structured parallel programming approach to MCTS. Moreover, we propose a new lock-free tree data structure for parallel MCTS which removes synchronization overhead. The Pipeline Pattern for Parallel MCTS algorithm (called 3PMCTS), scales very well to higher numbers of cores when compared to the existing methods.