Scalable Distributed Monte-Carlo Tree Search


  • Kazuki Yoshizoe The University of Tokyo
  • Akihiro Kishimoto Tokyo Institute of Technology and Japan Science and Technology Agency
  • Tomoyuki Kaneko The University of Tokyo
  • Haruhiro Yoshimoto The University of Tokyo
  • Yutaka Ishikawa The University of Tokyo



Monte-Carlo Tree Search, Parallel Computing, TDS


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.