Date : March 7, 2019, 1 p.m. - Room :Salle du conseil
A Stochastic Constraint-Based Approach to General Game Playing
Eric PIETTE, Post-doctorant - DKE, Maastricht University
The ability for a computer program to effectively play any strategic game, often referred to General Game Playing (GGP), is a key challenge in AI. The GGP competitions, where any game is represented according to a set of logical rules in the Game Description Language (GDL), have led researches to compare various approaches, including Monte Carlo methods, automatic constructions of evaluation functions, logic programming, and answer set programming through some general game players. In this thesis, we offer a new approach driven by stochastic constraints.
We first focus on a translation process from GDL to stochastic constraint networks (SCSP) in order to provide compact representations of strategic games and to model strategies.
In a second part, we exploit a fragment of SCSP through an algorithm called MAC-UCB by coupling the MAC (Maintaining Arc Consistency) algorithm, used to solve each stage of the SCSP in turn, together with the UCB (Upper Confidence Bound) policy for approximating the values of those strategies obtained by the last stage in the sequence. The efficiency of this technical on the others GGP approaches is confirmed by WoodStock, implementing MAC-UCB, by becomming the leader on the GGP Continuous Tournament in just a few months.
Finally, in the last part, we propose an alternative approach to symmetry detection in stochastic games, inspired from constraint programming techniques. We demonstrate experimentally that MAC-UCB, coupled with our constraint-based symmetry detection approach, significantly outperforms the best approaches and made WoodStock the GGP champion 2016.