Stochastic Constraint Programming for General Game Playing with Imperfect Information
(2016) General Intelligence in Game-Playing Agents — Location: New York, USA (9.July.2016)
Files
giga16.pdf
Open Access - Adobe PDF
- 353.98 KB
Details
- Authors
- Abstract
- The game description language with incomplete information (GDL-II) is expressive enough to capture partially observable stochastic multi-agent games. Unfortunately, such expressiveness does not come without a price: the problem of finding a winning strategy is NEXP NP-hard, a complexity class which is far beyond the reach of modern constraint solvers. 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) which, in turn, can be solved using general-purpose constraint programming techniques. Namely, we develop a constraint-based sequential decision algorithm for GDL-II games, which exploits constraint propagation and Monte Carlo sampling based. Our algorithm, validated on a wide variety of games, significantly outperforms the state-of-the-art general game playing algorithms.
- Affiliations
Citations
Koriche, F., Lagrue, S., Piette, E., & Tabary, S. (2016). Stochastic Constraint Programming for General Game Playing with Imperfect Information. Computer Games. Published. General Intelligence in Game-Playing Agents, New York, USA. https://hdl.handle.net/2078.5/254043