“Monte Carlo tree search (MCTS) is a method for making optimal decisions in artificial intelligence (AI) problems.” It takes random samples in a given decision space and builds a search tree according to the simulation results. MCTS is a powerful tool for AI and has wide applications, especially for move planning in games.

The authors study parallel MCTS using graphics processing units (GPUs). This paper considers two approaches. In the simple leaf parallelization approach, “[one] GPU thread performs an independent simulation from the same node.” When the number of GPU threads is large enough, this approach has the advantage of better accuracy. The second approach is the block parallelization method, a mixed method that is more efficient than the first. Based on experiments, the authors propose a hybrid algorithm using both GPUs and central processing units (CPUs). The performance of the hybrid algorithm is much more accurate: one GPU outperforms 256 CPUs. The results are very strong.

The main contribution of the paper is that it proposes an MCTS algorithm suitable for GPU devices. From the experiments, we can see that the block parallelization algorithm outperforms the traditional leaf parallelization on GPUs. The paper is a good reference for researchers working in related areas.