Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search

Rémi Coulom 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal, Inria Lille - Nord Europe
Abstract : Monte-Carlo evaluation consists in estimating a position by averaging the outcome of several random continuations, and can serve as an evaluation function at the leaves of a min-max tree. This paper presents a new framework to combine tree search with Monte-Carlo evaluation, that does not separate between a min-max phase and a Monte-Carlo phase. Instead of backing-up the min-max value close to the root, and the average value at some depth, a more general backup operator is defined that progressively changes from averaging to min-max as the number of simulations grows. This approach provides a fine-grained control of the tree growth, at the level of individual simulations, and allows efficient selectivity methods. This algorithm was implemented in a Go-playing program, Crazy Stone, that won the gold medal of the $9 \times 9$ Go tournament at the 11th Computer Olympiad.
Type de document :
Communication dans un congrès
Paolo Ciancarini and H. Jaap van den Herik. 5th International Conference on Computer and Games, May 2006, Turin, Italy. 2006
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00116992
Contributeur : Rémi Coulom <>
Soumis le : mercredi 29 novembre 2006 - 12:12:56
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mardi 6 avril 2010 - 23:37:51

Fichier

CG2006.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00116992, version 1

Collections

Citation

Rémi Coulom. Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. Paolo Ciancarini and H. Jaap van den Herik. 5th International Conference on Computer and Games, May 2006, Turin, Italy. 2006. 〈inria-00116992〉

Partager

Métriques

Consultations de la notice

478

Téléchargements de fichiers

6123