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

Venue:
IJCAI Workshop: General Intelligence in Game-Playing Agents (GIGA), 2016

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

Links: PDF

The Game Description Language with incomplete information (GDL-II) is expressive enough to capture 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, where agents share the same partial observations. We show that this fragment can be cast as a decomposable Stochastic Constraint Satisfaction Problem (SCSP), allowing it to be solved using standard constraint programming techniques.

We introduce a constraint-based sequential decision algorithm (MAC-UCB-II) that combines constraint propagation and Monte Carlo sampling. Experimental results on a wide range of games demonstrate that this approach significantly outperforms state-of-the-art General Game Playing algorithms.

This paper extends previous work on stochastic constraint programming for General Game Playing to the setting of imperfect information games described in GDL-II.

It introduces a tractable fragment of GDL-II and proposes a constraint-based encoding into SCSPs, enabling the use of constraint reasoning for sequential decision-making in partially observable games.

The paper also presents the algorithm MAC-UCB-II, an extension of MAC-UCB that integrates probabilistic reasoning through conditional probabilities derived from observations.

This work is closely related to the JFPC 2016 paper and serves as a step toward the full journal version published later in Constraints.

Koriche, F., Lagrue, S., Piette, É., Tabary, S. (2016). Stochastic Constraint Programming for General Game Playing with Imperfect Information. In IJCAI Workshop on General Intelligence in Game-Playing Agents (GIGA).

@inproceedings{koriche2016giga,
  author    = {Koriche, Fr{\'e}d{\'e}ric and Lagrue, Sylvain and Piette, {\'E}ric and Tabary, S{\'e}bastien},
  title     = {Stochastic Constraint Programming for General Game Playing with Imperfect Information},
  booktitle = {IJCAI Workshop on General Intelligence in Game-Playing Agents (GIGA)},
  year      = {2016}
}