Séminaire

Date : 7 mars 2019 13:00 - Salle :Salle du conseil Une nouvelle approche au General Game Playing dirigée par les contraintes stochastiques Eric PIETTE, Post-doctorant - DKE, Maastricht University

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’évaluation, ou la programmation logique et ASP. De par ces travaux, 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é MACUCB 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 a été confirmée par WoodStock, implémentant MACUCB, devenant leader du tournoi continu de GGP en à peine quelques mois.

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 à MACUCB, surpasse les meilleures approches du domaine et a permis à WoodStock de devenir champion GGP 2016.