Français Anglais
Accueil Annuaire Plan du site
Accueil > Production scientifique > Thèses et habilitations
Production scientifique
Doctorat de RIMMEL Arpad
RIMMEL Arpad
Doctorat
Equipe : Apprentissage et Optimisation

"Improvements and Evaluation of the Monte Carlo Tree Search Algorithm".

Début le 01/10/2006
Direction : SEBAG, Michèle
[CORNUEJOLS Antoine]

Ecole doctorale : Paris XI
Etablissement d'inscription : Université Paris-Saclay

Lieu de déroulement : LRI

Soutenue le 15/12/2009 devant le jury composé de :
Jean-Yves Audibert (examinateur), Université Paris Est
Tristan Cazenave (rapporteur), Université Paris Dauphine
Antoine Cornuéjols (directeur de thèse), AgroParisTech
Phillipe Dague (examinateur), Université Paris Sud
Martin Müller (rapporteur de thèse), University of Alberta
Olivier Teytaud (directeur de thèse), Université Paris Sud

Activités de recherche :

Résumé :
"Ma thèse se situe dans le contexte de la planification à horizon fini en
environnement discret avec un nombre d'états trop important pour qu'ils
soient tous explorés. L'objectif est de maximiser une fonction de
récompense qui associe une valeur aux états finaux. Cette thèse est en
particulier centrée sur l'amélioration et l'étude d'un nouvel algorithme:
l'exploration d'arbre basée sur une formule de bandit avec évaluation
Monte Carlo. Après avoir présenté les algorithmes de référence du domaine
(Minimax et Alphabéta dans le cas deux joueurs; Nested Monte Carlo et
Programmation Dynamique dans le cas un joueur), je décris le principe de
l'algorithme. Puis je propose une méthode de parallélisation efficace pour
le cas ou la mémoire est séparée. Cette méthode se combine avec des
méthodes classiques de parallélisation à mémoire partagée. Je propose
ensuite une méthode pour construire une base d'ouverture et montre son
efficacité dans le cadre concret du jeu de Go. J'introduis également
plusieurs manières d'utiliser des connaissances expertes, aussi bien dans
la partie concernant les bandits que dans la partie Monte Carlo.
Finalement, je montre que cet algorithme qui donne de très bons résultats
dans le cadre des applications à deux joueurs est également efficace dans
un cadre à un joueur. En effet, je propose une adaptation de l'algorithme
pour le cas des graphes et en utilisant une formule de bandit différente
afin de résoudre le problème concret de la génération automatique de
librairies de transformations linéaires. J'obtiens des résultats nettement
supérieurs à ceux obtenus avec une méthode classique de programmation
dynamique."