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.
Type de document :
Communication dans un congrès
The International Conference on Computers and Games 2010, Sep 2010, Kanazawa, Japan. 2010
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00512854
Contributeur : Jean-Baptiste Hoock <>
Soumis le : mardi 31 août 2010 - 18:21:27
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : mercredi 1 décembre 2010 - 02:36:15

Fichier

newcluster.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. 2010. 〈inria-00512854〉

Partager

Métriques

Consultations de la notice

802

Téléchargements de fichiers

715