An ASP-based approach to Solving General Stochastic Two-Player Games
For researchers in general game playing and ASP, this provides a novel method to handle uncertainty in two-player games, though it is limited to small games and incremental in nature.
This paper presents the first ASP-based approach for solving two-player turn-taking stochastic games specified in GDL, encoding winning probabilities via Stochastic Answer Set Programming (SQASP) and translating to Extended Stochastic Satisfiability. The approach is competitive with forward search on small games and aids endgame evaluation.
The Game Description Language (GDL) is a widely used formalism for specifying general games. Due to their similar syntax and semantics, Answer Set Programming (ASP) and its extensions have been applied to single- and two-player deterministic turn-taking GDL games. This paper presents the first ASP-based approach for solving two-player turn-taking GDL games with uncertainty. We introduce Stochastic An- swer Set Programming (SQASP) to encode the maximally achievable winning probability for a given player in stochastic GDL games, and develop a translation-based solver that evaluates SQASP programs by converting them to Extended Stochastic Satisfiability. Our empirical results show that the proposed approach is competitive with forward search on small stochastic games and can potentially support general game players in endgame evaluation.