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

Venue:
Principles and Practice of Constraint Programming (CP), 2015

Type:
Abstract / fast-track paper (journal extension in Constraints)

Topics:
General Game Playing, stochastic CSP, Monte Carlo methods, constraint reasoning

Links: PDF

The aim of General Game Playing (GGP) is to design algorithms capable of playing a wide variety of games without being tailored to a specific one. Games are described using the Game Description Language (GDL), which allows modelling of complex, multi-agent environments with uncertainty.

This work proposes a constraint-based approach using Stochastic Constraint Satisfaction Problems (SCSP) to model and solve such games. The approach focuses on stochastic games with complete information and decomposes them into sequences of one-stage SCSPs.

Based on this formulation, the MAC-UCB algorithm is introduced, combining constraint propagation (MAC) and bandit-based exploration (UCB). Experimental results show that this approach significantly outperforms state-of-the-art methods such as UCT across a wide range of games.

This paper provides a high-level synthesis of a line of work combining constraint programming and stochastic decision-making for General Game Playing.

It introduces a unified view where:

• Games are modelled declaratively using GDL
• They are translated into SCSP representations
• They are solved using hybrid algorithms combining reasoning and learning

The proposed MAC-UCB algorithm highlights how combining symbolic reasoning with statistical exploration can outperform purely simulation-based approaches.

Koriche, F., Lagrue, S., Piette, E., Tabary, S. (2015). General Game Playing with Stochastic CSP. In Principles and Practice of Constraint Programming (CP). Abstract / fast-track paper (journal version in Constraints).

@inproceedings{koriche2015cp,
  author    = {Koriche, Frédéric and Lagrue, Sylvain and Piette, Eric and Tabary, Sébastien},
  title     = {General Game Playing with Stochastic CSP},
  booktitle = {Principles and Practice of Constraint Programming (CP)},
  year      = {2015},
  note      = {Abstract / journal fast-track (Constraints 21(1))}
}