General game playing with stochastic CSP
(2015) Constraints : an international journal — Vol. 21, n° 1, p. 95-114 (2015)
Files
s10601-015-9199-5.pdf
Open Access - Adobe PDF
- 1.27 MB
Details
- Authors
- Abstract
- 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.
- Affiliations
Citations
Koriche, F., Lagrue, S., Piette, E., & Tabary, S. (2015). General game playing with stochastic CSP. Constraints : an international journal, 21(1), 95-114. https://doi.org/10.1007/s10601-015-9199-5 (Original work published 2015)