An ASP-based approach to Solving General Stochastic Two-Player Games

Michael Thielscher; Yifan He

arxiv: 2605.23705 · v1 · pith:IKQJRLOHnew · submitted 2026-05-22 · 💻 cs.LO

An ASP-based approach to Solving General Stochastic Two-Player Games

Yifan He , Michael Thielscher This is my paper

Pith reviewed 2026-05-25 02:56 UTC · model grok-4.3

classification 💻 cs.LO

keywords stochastic gamesanswer set programminggame description languagegeneral game playingstochastic satisfiabilitywinning probabilitytwo-player gamesuncertainty

0 comments

The pith

Stochastic Answer Set Programming encodes the maximal winning probability for a player in uncertain two-player games.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces Stochastic Answer Set Programming (SQASP) to represent the highest winning chance achievable by one player in two-player turn-taking games specified in the Game Description Language that include random outcomes. It pairs this encoding with a solver that converts SQASP programs into Extended Stochastic Satisfiability instances to obtain exact probabilities. This matters for general game playing because prior ASP techniques handled only deterministic games, leaving stochastic variants without a comparable logic-programming route. Empirical tests indicate the method matches forward search performance on small instances and could aid endgame analysis inside broader game players. The central mechanism is the translation step that turns the probabilistic encoding into a form solvable by existing stochastic satisfiability tools.

Core claim

SQASP encodes the maximally achievable winning probability for a given player in stochastic GDL games, and a translation-based solver evaluates these programs by converting them to Extended Stochastic Satisfiability, yielding the first ASP-based approach for solving two-player turn-taking GDL games with uncertainty.

What carries the argument

Stochastic Answer Set Programming (SQASP) that encodes maximal winning probability, evaluated by translation to Extended Stochastic Satisfiability.

If this is right

The approach is competitive with forward search on small stochastic games.
It can potentially support general game players in endgame evaluation.
It supplies an exact probability rather than an approximation for the tested game sizes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Hybrid solvers could combine SQASP endgame values with forward search for larger games.
The same encoding pattern might apply to non-game domains that involve sequential decisions under uncertainty.
Existing ASP grounders and solvers could be reused to implement the SQASP layer without building new probabilistic engines from scratch.

Load-bearing premise

The translation from SQASP programs to Extended Stochastic Satisfiability computes the exact maximal winning probability without semantic distortion or size-dependent approximations.

What would settle it

Running the solver on a small stochastic game whose true maximal winning probability can be computed by exhaustive enumeration of all random outcomes and move sequences; any mismatch between the two values would falsify the claim.

Figures

Figures reproduced from arXiv: 2605.23705 by Michael Thielscher, Yifan He.

**Figure 1.** Figure 1: GDL description of a stochastic game with horizon 1. Player x gets 100 points if win holds. At step 0, x may choose either le or ri, while o can only play noop. The player random chooses a, b, or c uniformly, i.e. each with probability 1 3 . Hence, if x selects le (resp. ri), the probability that win holds in the next state is 2 3 (resp. 1 3 ). as GDL) that describes stochastic games with complete state in… view at source ↗

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper claims the first ASP treatment of stochastic GDL games but supplies no translation rules, semantic argument, or data to back the central claims.

read the letter

The one thing to know is that the work extends prior deterministic ASP encodings of GDL to the stochastic case by defining SQASP programs that capture maximal winning probabilities, then translating those programs into extended stochastic satisfiability. That move is new on its face and could matter for logic-programming approaches to general game playing if the reduction is faithful. The abstract positions the solver as competitive with forward search on small instances and potentially useful for endgame evaluation, which is a reasonable target given the limits of exact methods on larger stochastic games. What the paper does cleanly is identify the gap and sketch an encoding strategy that builds directly on existing ASP machinery for deterministic turn-taking games. The authors avoid reducing the problem to earlier published results and keep the scope modest. The soft spots are exactly where the stress-test note flags them. The translation step is load-bearing for the claim of exact maximal probabilities, yet the abstract gives neither the translation rules, a preservation argument, nor a worked toy example. Without those, it is impossible to check whether the reduction introduces semantic distortion or hidden approximations. The empirical statement that the approach is competitive is also unsupported by any numbers, game instances, or comparison details in the provided text. Those omissions make the soundness hard to assess from the abstract alone. This paper is for readers already working on ASP encodings of games or stochastic extensions of logic programming. Someone looking for new ideas in that narrow intersection might find the encoding direction worth following up. It deserves a serious referee because the core idea is coherent and the gap it targets is real, even though the current write-up leaves the key technical step unshown. Send it to review so the translation and experiments can be checked directly.

Referee Report

2 major / 1 minor

Summary. The paper presents the first ASP-based approach for solving two-player turn-taking GDL games with uncertainty. It introduces Stochastic Answer Set Programming (SQASP) to encode the maximally achievable winning probability for a given player in stochastic GDL games and develops a translation-based solver that converts SQASP programs to Extended Stochastic Satisfiability. Empirical results indicate competitiveness with forward search on small stochastic games and potential support for general game players in endgame evaluation.

Significance. If the translation is shown to be correct and the empirical results are substantiated with data, this work would offer a novel method for handling stochastic elements in general game descriptions using logic programming techniques, extending existing ASP applications in deterministic games to uncertain settings.

major comments (2)

[Abstract] Abstract: The abstract states the existence of a translation-based solver from SQASP to Extended Stochastic Satisfiability that evaluates the programs to compute maximal winning probabilities, but provides neither the translation rules, a semantic preservation argument, nor a worked example. This is load-bearing for the central claim of exact computation without semantic errors or approximations.
[Abstract] Abstract: The abstract asserts that the proposed approach is competitive with forward search on small stochastic games, but supplies no data, tables, error bars, implementation details, or tested game sizes, making it impossible to assess the empirical claim.

minor comments (1)

[Abstract] The hyphenated 'An- swer' in 'Stochastic An- swer Set Programming' appears to be a typesetting artifact.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. We address each major comment below and indicate planned revisions to the manuscript.

read point-by-point responses

Referee: [Abstract] Abstract: The abstract states the existence of a translation-based solver from SQASP to Extended Stochastic Satisfiability that evaluates the programs to compute maximal winning probabilities, but provides neither the translation rules, a semantic preservation argument, nor a worked example. This is load-bearing for the central claim of exact computation without semantic errors or approximations.

Authors: The abstract is a high-level summary; the translation rules, semantic preservation argument, and worked example are fully detailed in Sections 3 and 4 of the manuscript. We will revise the abstract to explicitly reference these sections so readers can locate the supporting material immediately. revision: partial
Referee: [Abstract] Abstract: The abstract asserts that the proposed approach is competitive with forward search on small stochastic games, but supplies no data, tables, error bars, implementation details, or tested game sizes, making it impossible to assess the empirical claim.

Authors: The abstract summarizes the results; complete data, tables, error bars, implementation details, and tested game sizes appear in Section 5. We will revise the abstract to note the scale of the evaluated instances for improved clarity. revision: partial

Circularity Check

0 steps flagged

No circularity: translation presented as independent solver construction

full rationale

The abstract and available text introduce SQASP as a new encoding for maximal winning probabilities in stochastic GDL games and describe a translation-based solver to Extended Stochastic Satisfiability without any equations, self-definitions, or self-citations that reduce the claimed exact probabilities back to fitted inputs or prior author results by construction. The approach builds on existing ASP and stochastic SAT machinery as external foundations, with the central claim resting on the (unshown here) correctness of the translation rather than any renaming, ansatz smuggling, or load-bearing self-reference. This is the normal case of a self-contained proposal whose verification lies outside the derivation itself.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no information on free parameters, background axioms, or new entities; ledger therefore empty pending full text.

pith-pipeline@v0.9.0 · 5651 in / 1061 out tokens · 44614 ms · 2026-05-25T02:56:00.456210+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

19 extracted references · 1 canonical work pages

[1]

io/articles/probabilistic-tic-tac-toe(2024)

Abraham, L.: Solving Probabilistic Tic-Tac-Toe.https://louisabraham.github. io/articles/probabilistic-tic-tac-toe(2024)

2024
[2]

Bertolino, M., Jonnarth, A.: Monte Carlo methods applied to tree-structured de- cision processes (2017)

2017
[3]

IEEETransactionsonComputationalIntelligenceandAIinGamespp.4–15(2009)

Bjornsson, Y., Finnsson, H.: Cadiaplayer: A simulation-based general game player. IEEETransactionsonComputationalIntelligenceandAIinGamespp.4–15(2009)

2009
[4]

In: Proceedings of the AAAI

Fan, Y.W., Jiang, J.H.R.: Sharpssat: A witness-generating stochastic boolean sat- isfiability solver. In: Proceedings of the AAAI. pp. 3949–3958 (2023)

2023
[5]

TheoryandPractice of Logic Programming21(5), 663–679 (2021)

Fandinno, J., Laferrière, F., Romero, J., Schaub, T., Son, T.C.: Planning with in- completeinformation inQuantifiedAnswerSetProgramming. TheoryandPractice of Logic Programming21(5), 663–679 (2021)

2021
[6]

Springer Nature (2022)

Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Answer set solving in prac- tice. Springer Nature (2022)

2022
[7]

Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers (2014)

Genesereth, M.R., Thielscher, M.: General Game Playing. Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers (2014). https://doi.org/10.2200/S00564ED1V01Y201311AIM024

work page doi:10.2200/s00564ed1v01y201311aim024 2014
[8]

In: Proceedings of AAAI

Goldwaser, A., Thielscher, M.: Deep Reinforcement Learning for General Game Playing. In: Proceedings of AAAI. pp. 1701–1708 (2020)

2020
[9]

In: Proceedings of AAMAS

He, Y., Saffidine, A., Thielscher, M.: Solving two-player games with qbf solvers in general game playing. In: Proceedings of AAMAS. pp. 807–815 (2024)

2024
[10]

In: Proceedings of ECAI

Janhunen, T.: Representing normal programs with clauses. In: Proceedings of ECAI. p. 358–362 (2004)

2004
[11]

Constraints21, 95–114 (2016)

Koriche, F.,Lagrue, S.,Piette, É.,Tabary, S.:General gameplayingwithstochastic CSP. Constraints21, 95–114 (2016)

2016
[12]

In: Proceedings of CADE

Lonsing, F., Egly, U.: DepQBF 6.0: A Search-Based QBF Solver Beyond Tradi- tional QCDCL. In: Proceedings of CADE. pp. 371–384 (2017)

2017
[13]

Love, N., Genesereth, M., Hinrichs, T.: General game playing: Game descrip- tion language specification. Tech. Rep. LG-2006-01, Stanford University (2006), ggp.stanford.edu/readings/gdl_spec.pdf

2006
[14]

In: Proceedings of FMCAD

Rabe, M.N., Tentrup, L.: CAQE: A Certifying QBF Solver. In: Proceedings of FMCAD. pp. 136–143 (2015)

2015
[15]

In: Pro- ceedings of AAAI

Schiffel, S., Thielscher, M.: Fluxplayer: A successful general game player. In: Pro- ceedings of AAAI. p. 1191–1196 (2007)

2007
[16]

In: Proceedings of ICAART

Schiffel, S., Thielscher, M.: A multiagent semantics for the game description lan- guage. In: Proceedings of ICAART. pp. 44–55 (2009)

2009
[17]

Teige, T.: Stochastic satisfiability modulo theories: a symbolic technique for the analysisofprobabilistichybridsystems.Ph.D.thesis,UniversitätOldenburg(2012)

2012
[18]

In: Proceedings of ICLP

Thielscher,M.:AnswerSetProgrammingforSingle-PlayerGamesinGeneralGame Playing. In: Proceedings of ICLP. pp. 327–341 (2009)

2009
[19]

In: Proceedings of the AAAI

Thielscher, M., Voigt, S.: A temporal proof system for general game playing. In: Proceedings of the AAAI. pp. 1000–1005 (2010)

2010

[1] [1]

io/articles/probabilistic-tic-tac-toe(2024)

Abraham, L.: Solving Probabilistic Tic-Tac-Toe.https://louisabraham.github. io/articles/probabilistic-tic-tac-toe(2024)

2024

[2] [2]

Bertolino, M., Jonnarth, A.: Monte Carlo methods applied to tree-structured de- cision processes (2017)

2017

[3] [3]

IEEETransactionsonComputationalIntelligenceandAIinGamespp.4–15(2009)

Bjornsson, Y., Finnsson, H.: Cadiaplayer: A simulation-based general game player. IEEETransactionsonComputationalIntelligenceandAIinGamespp.4–15(2009)

2009

[4] [4]

In: Proceedings of the AAAI

Fan, Y.W., Jiang, J.H.R.: Sharpssat: A witness-generating stochastic boolean sat- isfiability solver. In: Proceedings of the AAAI. pp. 3949–3958 (2023)

2023

[5] [5]

TheoryandPractice of Logic Programming21(5), 663–679 (2021)

Fandinno, J., Laferrière, F., Romero, J., Schaub, T., Son, T.C.: Planning with in- completeinformation inQuantifiedAnswerSetProgramming. TheoryandPractice of Logic Programming21(5), 663–679 (2021)

2021

[6] [6]

Springer Nature (2022)

Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Answer set solving in prac- tice. Springer Nature (2022)

2022

[7] [7]

Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers (2014)

Genesereth, M.R., Thielscher, M.: General Game Playing. Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers (2014). https://doi.org/10.2200/S00564ED1V01Y201311AIM024

work page doi:10.2200/s00564ed1v01y201311aim024 2014

[8] [8]

In: Proceedings of AAAI

Goldwaser, A., Thielscher, M.: Deep Reinforcement Learning for General Game Playing. In: Proceedings of AAAI. pp. 1701–1708 (2020)

2020

[9] [9]

In: Proceedings of AAMAS

He, Y., Saffidine, A., Thielscher, M.: Solving two-player games with qbf solvers in general game playing. In: Proceedings of AAMAS. pp. 807–815 (2024)

2024

[10] [10]

In: Proceedings of ECAI

Janhunen, T.: Representing normal programs with clauses. In: Proceedings of ECAI. p. 358–362 (2004)

2004

[11] [11]

Constraints21, 95–114 (2016)

Koriche, F.,Lagrue, S.,Piette, É.,Tabary, S.:General gameplayingwithstochastic CSP. Constraints21, 95–114 (2016)

2016

[12] [12]

In: Proceedings of CADE

Lonsing, F., Egly, U.: DepQBF 6.0: A Search-Based QBF Solver Beyond Tradi- tional QCDCL. In: Proceedings of CADE. pp. 371–384 (2017)

2017

[13] [13]

Love, N., Genesereth, M., Hinrichs, T.: General game playing: Game descrip- tion language specification. Tech. Rep. LG-2006-01, Stanford University (2006), ggp.stanford.edu/readings/gdl_spec.pdf

2006

[14] [14]

In: Proceedings of FMCAD

Rabe, M.N., Tentrup, L.: CAQE: A Certifying QBF Solver. In: Proceedings of FMCAD. pp. 136–143 (2015)

2015

[15] [15]

In: Pro- ceedings of AAAI

Schiffel, S., Thielscher, M.: Fluxplayer: A successful general game player. In: Pro- ceedings of AAAI. p. 1191–1196 (2007)

2007

[16] [16]

In: Proceedings of ICAART

Schiffel, S., Thielscher, M.: A multiagent semantics for the game description lan- guage. In: Proceedings of ICAART. pp. 44–55 (2009)

2009

[17] [17]

Teige, T.: Stochastic satisfiability modulo theories: a symbolic technique for the analysisofprobabilistichybridsystems.Ph.D.thesis,UniversitätOldenburg(2012)

2012

[18] [18]

In: Proceedings of ICLP

Thielscher,M.:AnswerSetProgrammingforSingle-PlayerGamesinGeneralGame Playing. In: Proceedings of ICLP. pp. 327–341 (2009)

2009

[19] [19]

In: Proceedings of the AAAI

Thielscher, M., Voigt, S.: A temporal proof system for general game playing. In: Proceedings of the AAAI. pp. 1000–1005 (2010)

2010