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

Venue:
Constraints, 2016

Volume and pages:
Volume 21, pp. 95–114

Published online:
26 August 2015

DOI:
10.1007/s10601-015-9199-5

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

Links: PDF · Springer page

The challenge of General Game Playing (GGP) is to devise game playing programs that take as input the rules of any strategic game, described in the Game Description Language (GDL), and that effectively play without human intervention.

The aim of this paper is to address the GGP challenge by casting GDL games (potentially with chance events) into the Stochastic Constraint Satisfaction Problem (SCSP). The stochastic constraint network of a game is decomposed into a sequence of μSCSPs (also know as one-stage SCSP), each associated with a game round.

Winning strategies are searched by coupling the MAC (Maintaining Arc Consistency) algorithm, used to solve each μSCSP in turn, together with the UCB (Upper Confidence Bound) policy for approximating the values of those strategies obtained by the last μSCSP in the sequence. Extensive experiments conducted on various GDL games with different deliberation times per round demonstrate that the MAC-UCB algorithm significantly outperforms the state-of-the-art UCT (Upper Confidence bounds for Trees) algorithm.

This journal article is the full and mature version of a line of work combining General Game Playing, stochastic constraint satisfaction, and sequential decision-making.

It formalises how GDL games can be encoded into SCSPs, decomposed into μSCSPs, and solved with the hybrid MAC-UCB algorithm that combines symbolic constraint reasoning and statistical exploration.

The article also reports extensive experiments on a broad range of games, showing that MAC-UCB significantly outperforms UCT across many settings, especially in stochastic environments.

Koriche, F., Lagrue, S., Piette, É., Tabary, S. (2016). General game playing with stochastic CSP. Constraints, 21, 95–114. Springer Science+Business Media New York. DOI: 10.1007/s10601-015-9199-5

@article{koriche2016ggp,
  author    = {Koriche, Fr{\'e}d{\'e}ric and Lagrue, Sylvain and Piette, {\'E}ric and Tabary, S{\'e}bastien},
  title     = {General game playing with stochastic CSP},
  journal   = {Constraints},
  volume    = {21},
  pages     = {95--114},
  year      = {2016},
  doi       = {10.1007/s10601-015-9199-5},
  publisher = {Springer Science+Business Media New York}
}