TY - GEN
T1 - Scalable distributed Monte-Carlo tree search
AU - Yoshizoe, Kazuki
AU - Kishimoto, Akihiro
AU - Kaneko, Tomoyuki
AU - Yoshimoto, Haruhiro
AU - Ishikawa, Yutaka
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84864989944&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84864989944&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84864989944
SN - 9781577355373
T3 - Proceedings of the 4th Annual Symposium on Combinatorial Search, SoCS 2011
SP - 180
EP - 187
BT - Proceedings of the 4th Annual Symposium on Combinatorial Search, SoCS 2011
T2 - 4th International Symposium on Combinatorial Search, SoCS 2011
Y2 - 15 July 2011 through 16 July 2011
ER -