GPU for Monte Carlo Search

Lilian Buzer, Tristan Cazenave

Abstract

Nested Monte Carlo Search (NMCS) is a powerful algorithm for combinatorial optimization, but its implementation on GPUs has historically been hindered by thread divergence and random memory access patterns. This paper presents a novel approach to parallelizing NMCS on consumer-grade GPUs. By utilizing a "parallel leaf" strategy and optimizing for shared memory, we achieve speedups exceeding 420x compared to high-end CPUs. We evaluate our method on the Snake-in-the-Box problem, demonstrating that the massive parallelism of modern GPUs can overcome architectural disadvantages for search-based AI.

Introduction

Monte Carlo Search algorithms, including Monte Carlo Tree Search (MCTS) and Nested Monte Carlo Search (NMCS), are fundamental to state-of-the-art AI systems. Despite their success, these algorithms are typically executed on CPUs due to three primary challenges on GPU architectures: thread divergence, high memory latency for random walks, and severe cache constraints. This work challenges the conventional wisdom that GPUs are unsuitable for search-based AI by demonstrating a highly efficient NMCS implementation on an NVIDIA GTX 3080.

Methods

Our implementation focuses on Nested Monte Carlo Search (NMCS), which leverages lower-level simulations to inform higher-level decision-making. We address GPU-specific bottlenecks through several key strategies:

Parallel Leaf Strategy

Rather than parallelizing the recursive tree structure, which would be prohibitively memory-intensive, we parallelize at the "leaf" level. For each move evaluated at a higher nesting level, the GPU executes 32 playouts concurrently within a single warp.

Shared Memory Optimization

To mitigate the latency of global memory during random state-space walks, we utilize the GPU's shared memory. Although limited to approximately 100KB per multiprocessor, shared memory provides the low-latency access necessary for efficient random updates.

Theoretical Modeling of Synchronization Overhead

A significant challenge in GPU search is the "synchronization tax"—the idle time spent waiting for the longest playout in a warp to complete. We modeled this overhead using a Gaussian distribution to calculate an "alpha factor" (alpha), representing the expected ratio of the maximum playout length to the mean.

The alpha factor (alpha) as a function of the coefficient of variation (sigma/mu), illustrating the theoretical overhead of warp synchronization.

Key Insights

While a single CPU core maintains a significant advantage in raw speed and memory latency over a single GPU core, the sheer scale of GPU parallelism (e.g., 8,704 cores on a GTX 3080) provides a decisive advantage.

Comparison of CPU vs GPU performance ratios for integer and floating-point operations across different threading configurations.

Our findings indicate that moving the game state to shared memory is critical; implementations relying on global memory were found to be approximately 50% less efficient. Furthermore, the "alpha factor" tends to stabilize for most problem domains, ensuring that GPU parallelism scales effectively despite the inherent costs of synchronization.

Results

We evaluated our GPU-accelerated NMCS on the Snake-in-the-Box problem, a memory-bound graph theory challenge. Comparing an NVIDIA GTX 3080 against a single core of an AMD Ryzen 9 3900X, we observed the following:

  • Level 1 NMCS: Speedups of 380x to 390x.
  • Level 2 NMCS: Speedups ranging from 470x to 520x.

These results exceed the theoretical estimate of 420x, particularly at higher nesting levels, confirming the efficacy of the parallel leaf strategy.

Conclusion

This research demonstrates that consumer GPUs are highly effective for Monte Carlo Search when optimized for shared memory and warp-level parallelism. The successful porting of NMCS to GPUs marks a technological tipping point, suggesting that GPUs will become the standard hardware for generating playouts in complex search-based AI applications. Future work will focus on scaling these techniques to larger game states that exceed current shared memory limits.

Summary updated

Abstract

Monte Carlo Search algorithms can give excellent results for some combinatorial optimization problems and for some games. They can be parallelized efficiently on high-end CPU servers. Nested Monte Carlo Search is an algorithm that parallelizes well. We take advantage of this property to obtain large speedups running it on low cost GPUs. The combinatorial optimization problem we use for the experiments is the Snake-in-the-Box. It is a graph theory problem for which Nested Monte Carlo Search previously improved lower bounds. It has applications in electrical engineering, coding theory, and computer network topologies. Using a low cost GPU, we obtain speedups as high as 420 compared to a single CPU.
BibTeX
@inproceedings{buzer2023gpu,
  author = {Lilian Buzer and Tristan Cazenave},
  title = {{GPU for Monte Carlo Search}},
  booktitle = {LION},
  year = {2023},
  doi = {10.1007/978-3-031-44505-7\_13},
}
Figure