Presentation
Poster 51: SmartK: Efficient, Scalable, and Winning Parallel MCTS
SessionResearch Posters Display
Event Type
Posters
Research Posters
TP
EX
EXH
TimeThursday, 21 November 20198:30am - 5pm
LocationE Concourse
DescriptionSmartK 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.
Archive
