Programmation par contraintes stochastiques pour le General Game Playing avec informations incomplètes

Koriche, Frédéric;Lagrue, Sylvain;Piette, Eric;Tabary, Sébastien
(2016) Journées Francophones de Programmation par Contraintes — Location: Montpellier, France (13.June.2016)

Files

jfpc16.pdf
  • Open Access
  • Adobe PDF
  • 438.85 KB

Details

Authors
  • Koriche, Frédéric
    Author
  • Lagrue, Sylvain
    Author
  • Piette, EricUCLouvain
    Author
  • Tabary, Sébastien
    Author
Abstract
Le Game Description Language avec informations incomplètes (GDL-II) est assez expressif pour représenter les jeux stochastiques multi-agents avec observation partielle. Malheureusement, une telle expressivité n'est pas possible sans un prix : le problème consistant à trouver une stratégie gagnante est NExpNP-hard, une classe de complexité qui est bien au-delà de la portée des solvers actuels. Dans ce papier, nous identifions un fragment Pspace-complete de GDL-II, où les agents partagent les mêmes observations (partielles). Nous montrons que ce fragment peut être encapsulé dans un problème de satisfaction de contraintes stochastiques décomposable (SCSP) qui, par tour, peut être résolu en utilisant des techniques de programmation par contraintes usuelles. Dès lors, nous avons développé un algorithme de décisions séquentielles fondé sur les contraintes pour les jeux GDL-II exploitant la propagation par contraintes, l'évaluation Monte-Carlo et la détection de symétries. Notre algorithme, vérifié sur une large variété de jeux, surpasse aisément l'état de l'art des algorithmes du General Game Playing (GGP).
Affiliations

Citations

Koriche, F., Lagrue, S., Piette, E., & Tabary, S. (2016). Programmation par contraintes stochastiques pour le General Game Playing avec informations incomplètes. Journées Francophones de Programmation par Contraintes, Montpellier, France. https://hdl.handle.net/2078.5/253677