Algorithmes de recherche basés sur l'échantillonnage dans les jeux
21/11/2024 à 10h00
M.Jérôme ARJONILLA présente ses travaux en soutenance le 21/11/2024 à 10h00
À l'adresse suivante : Université Paris Dauphine-PSL, Place du Maréchal de Lattre de Tassigny, 75016, Paris - Salle des thèses D520
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Algorithmes de recherche basés sur l'échantillonnage dans les jeux
École doctorale
École doctorale Dauphine SDOSE
Équipe de recherche
UMR 7243 - Laboratoire d’Analyse et de Modélisation de Systèmes d’Aide à la Décision
Section CNU
27 - Informatique
Directeur(s)
M. Tristan CAZENAVE
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. Tristan CAZENAVE | Professeur | UNIVERSITE PARIS DAUPHINE - PSL | Directeur de thèse |
| M. Lucas SIMON | Professor | Queen Mary University of London | Rapporteur |
| M. Bruno BOUZY | Maître de conférences | Université Paris Cité | Rapporteur |
| Mme Anne-Gwenn BOSSER | Maître de conférences | École nationale d'ingénieurs de Brest | Examinatrice |
| M. Bruno ZANUTTINI | Professeur des universités | Université de Caen Normandie | Examinateur |
| M. Abdallah SAFFIDINE | Associate professor | Potassco Solutions | Co-encadrant de thèse |
Résumé
La recherche d'algorithmes appliquée aux jeux est un domaine de recherche très dynamique. Les jeux constituent un terrain d'application privilégié pour les algorithmes de recherche, car les jeux permettent de modéliser des problèmes complexes, de manière efficace. De nombreux algorithmes ont d'abord été développés pour les jeux avant d'être étendus à d'autres domaines. % Dans cette thèse, nous nous intéressons à la recherche d'algorithmes heuristiques dans le cadre des jeux, en particulier aux algorithmes de recherche heuristique basés sur le sampling, tels que Monte Carlo Tree Search (MCTS) en information parfaite, ainsi qu'à des algorithmes de détermination en information imparfaite. Nous explorons également l'intégration des algorithmes de recherche avec d'autres types d'algorithmes, notamment les algorithmes d'apprentissage par renforcement. Ce travail présente les méthodes existantes ainsi que plusieurs contributions originales dans ce domaine. La première partie de la thèse est consacrée à l'étude des algorithmes de recherche heuristique indépendants du domaine, ce qui les rend facilement testables et applicables dans divers contextes. Plus particulièrement, nous nous concentrons sur les jeux à information imparfaite, où les joueurs ne disposent pas de toutes les informations sur l'état du jeu. Dans ce contexte, certains problèmes apparaissent avec les méthodes existantes, notamment en ce qui concerne la fusion de stratégies et l'impact de la révélation d'informations. Nous discuterons en détail de ces problématiques et présenterons les méthodes proposées pour les résoudre. La seconde partie de la thèse porte sur les algorithmes de recherche heuristique spécifiques à un domaine. Ces algorithmes, dépendants du domaine, sont souvent plus efficaces que les algorithmes indépendants, car ils peuvent apprendre, généraliser et s'adapter à un contexte spécifique. Au cours de cette partie, nous étudions l'intégration des algorithmes de recherche heuristique avec d'autres types d'algorithmes, en particulier ceux d'apprentissage par renforcement. Nous présentons une contribution originale dans ce domaine ainsi qu'une autre en cours de développement. La première méthode propose de renforcer les algorithmes de recherche en intégrant des algorithmes d'apprentissage par renforcement basés sur le principe de guide. La seconde méthode vise à intégrer des méthodes basées sur des modèles (model-based) dans les algorithms recherches en information imparfaite.