Consistency Modifications for Automatically Tuned Monte-Carlo Tree Search

Vincent Berthier 1 Hassen Doghmen 2 Olivier Teytaud 1, 2
2 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
Abstract : Monte-Carlo Tree Search algorithms (MCTS [4, 6]), includ- ing upper confidence trees (UCT [9]), are known for their impressive ability in high dimensional control problems. Whilst the main testbed is the game of Go, there are increasingly many applications [13, 12, 7]; these algorithms are now widely accepted as strong candidates for high- dimensional control applications. Unfortunately, it is known that for op- timal performance on a given problem, MCTS requires some tuning; this tuning is often handcrafted or automated, with in some cases a loss of consistency, i.e. a bad behavior asymptotically in the computational power. This highly undesirable property led to a stupid behavior of our main MCTS program MoGo in a real-world situation described in sec- tion 3. This is a big trouble for our several works on automatic parameter tuning [3] and the genetic programming of new features in MoGo. We will see in this paper: - A theoretical analysis of MCTS consistency; - Detailed examples of consistent and inconsistent known algorithms; - How to modify a MCTS implementation in order to ensure con- sistency, independently of the modifications to the "scoring" mod- ule (the module which is automatically tuned and genetically pro- grammed in MoGo); - As a by product of this work, we'll see the interesting property that some heavily tuned MCTS implementations are better than UCT in the sense that they do not visit the complete tree (whereas UCT asymptotically does), whilst preserving the consistency at least if "consistency" modifications above have been made.
Type de document :
Communication dans un congrès
Lion4, 2010, venice, Italy. 14 p., 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00437146
Contributeur : Olivier Teytaud <>
Soumis le : dimanche 29 novembre 2009 - 16:03:12
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : jeudi 17 juin 2010 - 22:42:17

Fichier

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

Identifiants

  • HAL Id : inria-00437146, version 1

Collections

Citation

Vincent Berthier, Hassen Doghmen, Olivier Teytaud. Consistency Modifications for Automatically Tuned Monte-Carlo Tree Search. Lion4, 2010, venice, Italy. 14 p., 2010. 〈inria-00437146〉

Partager

Métriques

Consultations de la notice

560

Téléchargements de fichiers

503