Batch Monte Carlo Tree Search

This analysis examines the implementation and optimization of Batch Monte Carlo Tree Search (MCTS) for complex two-player games, specifically focusing on the game of Go. The primary objective is to leverage the computational efficiency of modern GPUs by processing neural network inferences in batches rather than sequentially. By separating the search tree—which stores move statistics—from a transposition table—which records state evaluations and priors—the proposed algorithm achieves higher throughput and more accurate search results.

The research introduces several key heuristics to enhance search performance. The µ FPU (First Play Urgency) is identified as superior to constant or best-mean FPU methods for guiding exploration. Furthermore, the Virtual Mean is proposed as a replacement for the traditional virtual loss, providing more realistic statistics during parallel tree descents. Additional refinements include the Last Iteration heuristic, which maximizes the utility of unused state evaluations, and the Second Move heuristic, which optimizes root-level decision-making when the most simulated move is no longer viable.

Experimental evaluations were conducted using a MobileNet neural network trained on the Katago dataset. Results demonstrate that batching inferences significantly increases the number of inferences per second, with a batch size of 32 yielding a 26-fold increase in throughput compared to a batch size of one. Ablation studies confirm that the integration of the µ FPU, Virtual Mean, Last Iteration, and Second Move heuristics collectively contributes to a substantial improvement in win rates against standard sequential PUCT algorithms. The findings conclude that combining these architectural optimizations allows for more efficient and effective search strategies in deep reinforcement learning-based game engines.