Array-Based Monte Carlo Tree Search
This work provides a faster implementation for decision-making problems, but it is incremental as it builds on an existing algorithm.
The authors tackled the problem of slow Monte Carlo Tree Search implementations by developing an array-based version of the Upper Confidence bounds applied to Trees algorithm, achieving up to 2.8 times better scaling with search depth in simulations.
Monte Carlo Tree Search is a popular method for solving decision making problems. Faster implementations allow for more simulations within the same wall clock time, directly improving search performance. To this end, we present an alternative array-based implementation of the classic Upper Confidence bounds applied to Trees algorithm. Our method preserves the logic of the original algorithm, but eliminates the need for branch prediction, enabling faster performance on pipelined processors, and up to a factor of 2.8 times better scaling with search depth in our numerical simulations.