Authors:
Frédéric Koriche, Sylvain Lagrue, Éric Piette, Sébastien Tabary

Venue:
Journées Francophones de Programmation par Contraintes (JFPC), 2016

Topics:
General Game Playing, GDL-II, incomplete information, stochastic CSP, constraint programming

Links: PDF

The Game Description Language with incomplete information (GDL-II) is expressive enough to represent partially observable stochastic multi-agent games. However, this expressiveness comes at a high computational cost: finding a winning strategy is NExpNP-hard.

In this paper, we identify a Pspace-complete fragment of GDL-II in which agents share the same partial observations. We show that this fragment can be encoded as a decomposable Stochastic Constraint Satisfaction Problem (SCSP), allowing each round of the game to be solved using standard constraint programming techniques.

We introduce a constraint-based sequential decision algorithm for GDL-II games that combines constraint propagation, Monte Carlo evaluation, and symmetry detection. Experimental results on a wide variety of games demonstrate that this approach significantly outperforms the state-of-the-art methods in General Game Playing.

Koriche, F., Lagrue, S., Piette, É., Tabary, S. (2016). Programmation par contraintes stochastiques pour le General Game Playing avec informations incomplètes. Journées Francophones de Programmation par Contraintes (JFPC).

@inproceedings{koriche2016gdl2,
  author    = {Koriche, Fr{\'e}d{\'e}ric and Lagrue, Sylvain and Piette, {\'E}ric and Tabary, S{\'e}bastien},
  title     = {Programmation par contraintes stochastiques pour le General Game Playing avec informations incompl{\`e}tes},
  booktitle = {Journ{\'e}es Francophones de Programmation par Contraintes (JFPC)},
  year      = {2016}
}