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

Venue:
AAAI Workshop on Planning, Search, and Optimization (PlanSOpt), 2015

Topics:
General Game Playing, constraint programming, stochastic decision making

Links: PDF | AAAI page

Among the languages used for representing goals, actions and their consequences for decision making and planning, the Game Description Language (GDL) enables the modelling of complex actions in uncertain and competitive environments.

This paper proposes to exploit stochastic constraint networks to provide compact representations of strategic games and to identify optimal policies. We develop a compiler translating games described in GDL into instances of Stochastic Constraint Satisfaction Problems (SCSP).

The correctness of the approach is established for games with complete information and an oblivious environment. The method is evaluated by solving several GDL games using a generic SCSP solver.

This work introduces a compilation approach bridging symbolic game representations and constraint-based optimization.

Games described in GDL are translated into Stochastic Constraint Satisfaction Problems (SCSP), enabling the use of general-purpose constraint solvers to compute optimal strategies.

The approach establishes a formal equivalence between:

• Game representations as Markov games
• Constraint-based representations as SCSP instances

This work provides a foundational step toward unifying game playing, planning, and constraint reasoning within a common computational framework.

Koriche, F., Lagrue, S., Piette, E., Tabary, S. (2015). Compiling Strategic Games with Complete Information into Stochastic CSPs. In AAAI Workshop on Planning, Search, and Optimization (PlanSOpt). Association for the Advancement of Artificial Intelligence.

@inproceedings{koriche2015aaaiw,
  author    = {Koriche, Frédéric and Lagrue, Sylvain and Piette, Eric and Tabary, Sébastien},
  title     = {Compiling Strategic Games with Complete Information into Stochastic CSPs},
  booktitle = {AAAI Workshop on Planning, Search, and Optimization (PlanSOpt)},
  year      = {2015},
  publisher = {AAAI Press}
}