SC19 Proceedings

The International Conference for High Performance Computing, Networking, Storage, and Analysis

Poster 51: SmartK: Efficient, Scalable, and Winning Parallel MCTS

Authors: Michael S. Davinroy (Swarthmore College), Shawn Pan (Swarthmore College), Bryce Wiedenbeck (Swarthmore College, Davidson College), Tia Newhall (Swarthmore College)

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.

Best Poster Finalist (BP): no

Poster: PDF
Poster summary: PDF

Back to Poster Archive Listing