SmartK: Efficient, Scalable, And Winning Parallel MCTS
Document Type
Conference Proceeding
Publication Date
2019
Published In
SC19
Abstract
SmartK is our efficient and scalable parallel algorithm for Monte Carlo Tree Search (MCTS), an approximation technique for game searches. MCTS is also used to solve problems as diverse as planning under uncertainty, combinatorial optimization, and high-energy physics. In these problems, the solution search space is significantly large, necessitating parallel solutions. Shared memory parallel approaches do not scale well beyond the size of a single node's RAM. SmartK is a distributed memory parallelization that takes advantage of both inter-node and intra-node parallelism and a large cumulative RAM found in clusters. SmartK's novel selection algorithm combined with its ability to efficiently search the solution space, results in better solutions than other MCTS parallel approaches. Results of an MPI implementation of SmartK for the game of Hex, show SmartK yields a better win percentage than other parallel algorithms, and that its performance scales to larger search spaces and high degrees of parallelism.
Conference
SC19
Conference Dates
November 17-22, 2019
Conference Location
Denver, CO
Recommended Citation
Michael S. Davinroy, Shawn Pan, Bryce Wiedenbeck, and Tia Newhall.
(2019).
"SmartK: Efficient, Scalable, And Winning Parallel MCTS".
SC19.
https://works.swarthmore.edu/fac-comp-sci/117