A Parallel Monte-Carlo Tree Search Algorithm

Tristan Cazenave, Nicolas Jouandeau

Abstract

Monte-Carlo Tree Search is a powerful paradigm for the game of Go. In this contribution we present a parallel Master-Slave algorithm for Monte-Carlo Tree Search and test it on a network of computers using various configurations: from 12,500 to 100,000 playouts, from 1 to 64 slaves, and from 1 to 16 computers. On our own architecture we obtain a speedup of 14 for 16 slaves. With a single slave and five seconds per move our algorithm scores 40.5% against GNU Go, with sixteen slaves and five seconds per move it scores 70.5%. At the end we give the potential speedups of our algorithm for various playout times.
BibTeX
@inproceedings{cazenave2008parallel,
  author = {Tristan Cazenave and Nicolas Jouandeau},
  title = {{A Parallel Monte-Carlo Tree Search Algorithm}},
  booktitle = {Computers and Games},
  year = {2008},
  doi = {10.1007/978-3-540-87608-3\_7},
}

Loading related content...

Figure