General Game Playing : que peut apporter la Programmation Par Contraintes ?
Cédric Piette
3 oct. 2019 - 14:00Depuis la présentation du Game Description Language (GDL) en 2005, puis de ses extensions, de nombreux "programmes-joueurs" ont été proposés. Contrairement aux algorithmes dédiés, conçus pour un jeu donné, ceux-ci visent à être capables de jouer à n'importe quel jeu codé en GDL, sans expertise préalable ni technologie dédiée à un jeu particulier. Les meilleurs programmes-joueurs mondiaux utilisent une technique appelée Monte Carlo Tree Search (MCTS), qui est une approche heuristique basée sur un échantillonnage aléatoire des états atteignables dans un jeu. Si MCTS et ses dérivés ont fait leurs preuves lors des différentes compétitions organisées depuis l'arrivée de GDL, les techniques algorithmiques liées à la Programmation Par Contraintes (PPC) ne sont -sauf dans de (très très) rares occasions- pas exploitées par les programmes-joueurs. Or, elles semblent représenter une piste intéressante à bien des égards. Ce travail préliminaire se concentre principalement sur les jeux dits à "1 joueur", c'est-à-dire les puzzles (au sens général), et pave la voie pour constater ce que la PPC permet de réaliser dans le domaine du General Game Playing, et quelles perspectives elle offre.