AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 4

Scalable Distributed Monte-Carlo Tree Search

Authors

Kazuki Yoshizoe,Akihiro Kishimoto,Tomoyuki Kaneko,Haruhiro Yoshimoto,Yutaka Ishikawa

The University of Tokyo,Tokyo Institute of Technology and Japan Science and Technology Agency,The University of Tokyo,The University of Tokyo,The University of Tokyo


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 4

Volume

Issue:

Vol. 4 No. 1 (2011): Fourth Annual Symposium on Combinatorial Search

Track:

Full Papers

Downloads:

Download PDF

Abstract:

Monte-Carlo Tree Search (MCTS) is remarkably successful in two-player games, but parallelizing MCTS has been notoriously difficult to scale well, especially in distributed environments. For a distributed parallel search, transposition-table driven scheduling (TDS) is known to be efficient in several domains. We present a massively parallel MCTS algorithm, that applies the TDS parallelism to the Upper Confidence bound Applied to Trees (UCT) algorithm, which is the most representative MCTS algorithm. To drastically decrease communication overhead, we introduce a reformulation of UCT called Depth-First UCT. The parallel performance of the algorithm is evaluated on clusters using up to 1,200 cores in artificial game-trees. We show that this approach scales well, achieving 740-fold speedups in the best case.

DOI:

10.1609/socs.v2i1.18194


SOCS

Vol. 4 No. 1 (2011): Fourth Annual Symposium on Combinatorial Search