• Thèse soutenue le :
  • 2016-12-09
  • faculté des sciences

Résumé :

Développer un programme capable de jouer à n’importe quel jeu de stratégie, souvent désigné par le General Game Playing (GGP) constitue un des Graal de l’intelligence artificielle. Les compétitions GGP, où chaque jeu est représenté par un ensemble de règles logiques au travers du Game Description Language (GDL), ont conduit la recherche à confronter de nombreuses approches incluant les méthodes de type Monte Carlo, la construction automatique de fonctions d’évaluations, ou la programmation logique et ASP. De par cette thèse, nous proposons une nouvelle approche dirigée par les contraintes stochastiques.

Dans un premier temps, nous nous concentrons sur l’élaboration d’une traduction de GDL en réseaux de contraintes stochastiques (SCSP) dans le but de fournir une représentation dense des jeux de stratégies et permettre la modélisation de stratégies.

Par la suite, nous exploitons un fragment de SCSP au travers d’un algorithme dénommé MAC-UCB combinant l’algorithme MAC (Maintaining Arc Consistency) utilisé pour résoudre chaque niveau du SCSP tour après tour, et à l’aide de UCB (Upper Confidence Bound) afin d’estimer l’utilité de chaque stratégie obtenue par le dernier niveau de chaque séquence. L’efficacité de cette nouvelle technique sur les autres approches GGP est confirmée par WoodStock, implémentant MAC-UCB, le leader actuel du tournoi continu de GGP.

Finalement, dans une dernière partie, nous proposons une approche alternative à la détection de symétries dans les jeux stochastiques, inspirée de la programmation par contraintes. Nous montrons expérimentalement que cette approche couplée à MAC-UCB, surpasse les meilleures approches du domaine et a permis à WoodStock de devenir champion GGP 2016.

Composition du jury :

  • Christian Bessière, LIRMM, Rapporteur
  • Tristan Cazenave, LAMSADE, Rapporteur
  • Arnaud Lallouet, Huawei Technologies, Rapporteur
  • Frédéric Koriche, CRIL, co-directeur de thèse
  • Sylvain Lagrue, CRIL, directeur de thèse
  • Anastasia Paparrizou, CRIL, Examinatrice
  • Florian Richoux, LINA Examinateur
  • Sébastien Tabary, CRIL, co-directeur de thèse