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
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
5 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
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 : Monday, July 8, 2019 - 3:08:40 PM
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

1338

Files downloads

1182