Scalability and Parallelization of Monte-Carlo Tree Search

Amine Bourki 1 Guillaume Chaslot 2 Matthieu Coulm 1 Vincent Danjean 3 Hassen Doghmen 4 Thomas Hérault 5 Jean-Baptiste Hoock 4, 6 Arpad Rimmel 7 Fabien Teytaud 4, 6 Olivier Teytaud 4, 6 Paul Vayssière 1 Ziqin Yu 4
3 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
4 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
5 GRAND-LARGE - Global parallel and distributed computing
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LIFL - Laboratoire d'Informatique Fondamentale de Lille, LRI - Laboratoire de Recherche en Informatique
Abstract : Monte-Carlo Tree Search is now a well established algorithm, in games and beyond. We analyze its scalability, and in particular its limitations, and the implications in terms of parallelization, in particular for our program MoGo but also for our Havannah program Shakti. In particular, we get a good efficiency for the parallel versions, both for multicore machines and for message-passing machines, but in spite of promising results in self-play there are situations for which increasing the time per move does not solve anything, and therefore parallelization is not the solution either. Nonetheless, for problems on which the Monte-Carlo part is less biased than in Go, parallelization should be very efficient even without shared memory.
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00512854
Contributor : Jean-Baptiste Hoock <>
Submitted on : Tuesday, August 31, 2010 - 6:21:27 PM
Last modification on : Friday, October 25, 2019 - 1:21:52 AM
Long-term archiving on : Wednesday, December 1, 2010 - 2:36:15 AM

File

newcluster.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00512854, version 1

Citation

Amine Bourki, Guillaume Chaslot, Matthieu Coulm, Vincent Danjean, Hassen Doghmen, et al.. Scalability and Parallelization of Monte-Carlo Tree Search. The International Conference on Computers and Games 2010, Sep 2010, Kanazawa, Japan. ⟨inria-00512854⟩

Share

Metrics

Record views

1346

Files downloads

1215