Cette thèse est une contribution au domaine du General Game Playing (GGP), une problématique de l’Intelligence Artificielle qui s’intéresse au développement d’agents autonomes capables de jouer à une grande variété de jeux et que nous appelons les jeux généraux. Le GGP se distingue des recherches sur les algorithmes permettant de bien jouer à des jeux spécifiques et offre de ce fait la possibilité d’évaluer l’efficacité de méthodes développées en Intelligence Artificielle sans perturbation par ajout de connaissances spécifiques à un jeu fournies par des experts. Un aspect important de nos travaux de recherche porte sur l’utilisation d’une représentation implicite de l’arbre de jeu sous la forme de règles logiques, une représentation explicite étant trop volumineuse pour être stockée sur une machine. Dans ce contexte, nous avons proposé une méthode efficace d’instanciation des règles définissant les jeux permettant la génération d’un circuit logique avec lequel nous pouvons effectuer une analyse statique du jeu et simuler rapidement des parties aléatoires. Une parallélisation de l’évaluation du circuit logique nous a permis d’accélérer significativement la recherche dans l’arbre de jeu. Nous avons proposé des adaptations des méthodes de recherche Monte-Carlo dans les arbres aux contraintes du GGP ainsi qu’une méthode permettant d’utiliser une estimation RAVE (Rapid Action Value Estimation) en début de recherche lorsque peu d’estimations sont disponibles. / This thesis is a contribution to the General Game Playing domain (GGP), a problematic of Artificial Intelligence (AI) aiming at developing autonomous agents that are able to play at a large variety of games called General Games. GGP is different from search algorithms allowing to play with a good level at specific games and opens the possibility to evaluate the efficiency of AI methods without prior knowledge form experts. An important aspect of our work lies on the utilization of an implicit game tree representation as a set of logic rules, an explicit representation being too large to be stored in memory. In this context, we have proposed an efficient method of rule instantiation allowing the computation of a logic circuit. A parallelization of the circuit evaluation allowed us to significantly accelerate the game tree exploration. We have proposed an adaptation of Monte-Carlo Tree Search for GGP and a method using RAVE (Rapid Action Value Estimation) in the beginning of the exploration when few estimations are available.
| Identifer | oai:union.ndltd.org:theses.fr/2017PA080102 |
| Date | 01 December 2017 |
| Creators | Vittaut, Jean-Noël |
| Contributors | Paris 8, Jouandeau, Nicolas, Mehat, Jean |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0018 seconds