💻 computer science

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

This paper introduces Stochastic Answer Set Programming (SQASP) as the first ASP-based approach for solving two-player turn-taking General Game Description Language (GDL) games with uncertainty, demonstrating its competitiveness with forward search on small stochastic games and its potential for endgame evaluation.

Original authors: Yifan He, Michael Thielscher

Published 2026-05-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yifan He, Michael Thielscher

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a computer how to play a board game. Usually, these games are like chess: you make a move, your opponent makes a move, and the board changes in a predictable way. But what if the game also involves a "wild card"? What if, after you move, a magical die roll decides whether your move works, or if a third invisible player (let's call him "Random") throws a wrench in the gears?

This paper is about teaching computers to solve these tricky, unpredictable games. The authors, Yifan He and Michael Thielscher, have built a new mathematical toolkit to figure out the best possible strategy when luck is involved.

Here is the breakdown of their approach using simple analogies:

1. The Problem: The "Random" Player

In standard game theory, computers are great at calculating the perfect move against a smart opponent. But when you add randomness (like rolling dice or drawing cards), the math gets messy.

The Old Way: Previous computer programs could handle games with two smart players (like Chess) or games with one player and a random element (like Solitaire). They couldn't handle a game with two smart players AND a random element all at once.
The Goal: The authors wanted to solve "General Stochastic Two-Player Games." Think of it as a game of Tic-Tac-Toe where, every time you try to place an X, there's a 30% chance the square turns into an O instead, or a 50% chance the move is blocked entirely.

2. The New Tool: SQASP (The "Magic Blueprint")

The authors invented a new language called Stochastic Answer Set Programming (SQASP).

The Analogy: Imagine you are an architect designing a house. You have a blueprint (the game rules). In the past, you could only design houses for two specific types of builders: one who is a genius strategist (the opponent) and one who is a robot following strict rules.
The Innovation: SQASP is like a new type of blueprint that can describe a construction site where you have a Genius Strategist, a Robot, and a Gambler all working together.
- The Genius (Player X) wants to win.
- The Opponent (Player O) wants to stop Player X.
- The Gambler (Random) flips a coin to decide what happens next.
SQASP allows the computer to ask: "What is the highest possible chance I have of winning, assuming my opponent plays perfectly to stop me, and the Gambler does whatever they want?"

3. The Translator: Turning Blueprints into a Puzzle

Computers don't speak "Blueprint." They speak "Logic Puzzles."

The Process: The authors built a translator (a tool called sqasp2xssat). It takes their fancy SQASP blueprint and converts it into a massive logic puzzle called Extended Stochastic Satisfiability (XSSAT).
The Metaphor: Think of SQASP as a complex recipe for a cake. The translator is a machine that turns that recipe into a giant, multi-layered Sudoku puzzle. Once the puzzle is solved, the answer tells you the exact probability of winning the game.
The Solver: They used an existing solver (SharpSSAT) to crack this Sudoku. If the solver says "Yes, this puzzle can be solved," it means the player has a winning strategy. If it calculates a 67% chance, that's the best possible outcome.

4. The "Quantifier Shifting" Trick

The paper also tested a specific optimization technique called Quantifier Shifting.

The Analogy: Imagine you are organizing a tournament.
- Method A (Baseline): You list every single player's move, then check if the moves are legal, then check if the game ended.
- Method B (Shifting): You check if the moves are legal before you even list the moves. This seems faster because you don't waste time planning moves that are illegal.
The Result: In games with two smart players (deterministic games), this "Shifting" trick is a huge speed boost. However, the authors found that in games with the "Gambler" (stochastic games), this trick didn't make much difference.
Why? The solver they used (SharpSSAT) is very smart. It has a built-in "detective" (called unit propagation) that figures out the illegal moves on its own, regardless of the order you gave the instructions. So, the fancy re-ordering wasn't necessary for this specific solver.

5. The Results: How Did It Do?

The team tested their system on variations of classic games like Tic-Tac-Toe, Connect-4, and Nim, but with the "Random" player added.

Performance: Their new method was competitive with the standard "forward search" methods (which are like a computer playing the game millions of times in its head to see what happens).
The Catch: It worked great on small boards (like 3x3 or 4x4). However, when the game got too big (like a 100-piece pile in Nim), the logic puzzle became too huge for the computer to solve in a reasonable time.
The Takeaway: The method is excellent for endgame evaluation. If a game is almost over, this system can tell a general game-playing AI, "Hey, if you make this move, you have a 99% chance of winning," helping it make the final decision.

Summary

The authors created a new way to mathematically describe games where luck and strategy collide. They turned these descriptions into logic puzzles that a computer can solve to find the "best possible odds" of winning. While it's not a magic bullet for every game size, it proves that we can use logic programming to solve complex, uncertain games, giving computers a better way to think about the future in a chaotic world.

What they did NOT claim:

They did not claim this works for games where you can't see the whole board (like Poker or Krieg-Tic-Tac-Toe). They explicitly state their method is for games where everyone sees the whole board (perfect information).
They did not claim this will replace all other AI methods immediately; they noted it is an alternative for specific scenarios, particularly endgames.

Technical Summary: An ASP-based Approach to Solving General Stochastic Two-Player Games

Problem Statement

General Game Playing (GGP) systems aim to play strategic games based on runtime descriptions without prior knowledge of the rules. The Game Description Language (GDL) and its extension GDL-II are the standard formalisms for specifying such games, with GDL-II supporting randomness (stochasticity) and partial observability. While Answer Set Programming (ASP) has been successfully applied to solving deterministic single- and two-player GDL games, existing ASP frameworks lack the capability to express both adversarial (minimax) and stochastic behaviors simultaneously. Consequently, there is a gap in using ASP-based methods to solve two-player turn-taking GDL games that involve uncertainty.

Methodology

The authors propose a novel approach to solve two-player stochastic GDL games by introducing a new language and a translation-based solver.

1. Stochastic Quantified Answer Set Programming (SQASP)

To bridge the gap between ASP and stochastic game solving, the paper introduces SQASP, a language that extends QASP (Quantified ASP) with chance quantifiers.

Syntax: An SQASP program takes the form $Q_1.x_1 \dots Q_n.x_n \ P$ , where $P$ is a normal logic program and the quantifiers $Q_i$ can be existential ( $\exists$ ), universal ( $\forall$ ), or chance ( $\mathcal{R}_{p}$ ).
Semantics: The maximal probability of satisfying an SQASP program is defined recursively. The chance quantifier $\mathcal{R}_{p}$ assigns a probability $p$ to a variable being true, calculating the expected value based on the probabilities of the sub-formulas.
Translation: The authors implement a tool, sqasp2xssat, which translates SQASP programs into Extended Stochastic Satisfiability (XSSAT) formulas. XSSAT extends Quantified Boolean Formulas (QBF) with chance quantifiers. The translation leverages existing tools (like lp2sat) to convert the logic program $P$ into a CNF formula $\psi$ whose models correspond to the stable models of $P$ .

2. Encoding GDL Games into SQASP

The core contribution is the construction of an SQASP program $\Psi$ such that its maximal satisfiability probability equals the maximal winning probability of a player $x$ within $n$ steps ( $P_x^w(S_0, n)$ ). The encoding proceeds in two main phases:

Cooperative Baseline: First, a logic program $P_c$ is constructed assuming all players (including the opponent $o$ and the random player $r$ ) cooperate to reach a terminal state where $x$ wins. This ensures valid game progression, termination within $n$ steps, and the achievement of the goal state.
Adversarial and Stochastic Modeling: The program is then extended to capture the specific behaviors of the opponent and the environment:
- Adversarial Player ( $o$ ): Modeled using universal quantification ( $\forall$ ) over decision variables (dec_o). This forces the solver to consider the worst-case scenario where the opponent minimizes $x$ 's winning probability. The encoding uses a logarithmic representation of actions to reduce the number of rules.
- Stochastic Player ( $r$ ): Modeled using chance quantifiers ( $\mathcal{R}_{1/i}$ ). The encoding ensures that if the game has not terminated, the random player selects exactly one legal action uniformly from the available legal moves. This is achieved by counting legal actions and applying probability constraints to decision variables (dec_r).

3. Quantification Strategies

The paper investigates two quantification strategies for the resulting XSSAT formula:

Baseline Method ( $Q_b$ ): All non-choice atoms (e.g., legal, terminal) are placed in the innermost existential block, following a strict temporal order of choice atoms.
Dependency-Based Method ( $Q_d$ ): Inspired by techniques for deterministic games, this method shifts non-choice atoms to appear as early as possible in the quantifier prefix, immediately after the choice atoms they depend on. This aims to reduce the search space by fixing values like legal before branching on does.

Key Contributions

First ASP-based Solver for Stochastic GDL: The paper presents the first approach to solving two-player, stochastic, turn-taking GDL games using ASP.
SQASP Language: The introduction of Stochastic Quantified Answer Set Programming, which unifies adversarial and stochastic reasoning within a logic programming framework.
Translation-Based Solver: The development of sqasp2xssat, which converts SQASP programs into XSSAT formulas, enabling the use of existing XSSAT solvers (specifically SharpSSAT) for game solving.
Theoretical Correctness: The authors provide formal proofs (Theorems 2 and 3) establishing the equivalence between the maximal winning probability in the GDL game and the maximal satisfiability probability of the generated SQASP/XSSAT formula.

Experimental Results

The authors evaluated their approach on stochastic variations of Tic-Tac-Toe, Connect-4, and Nim, comparing the SQASP-based method (using both $Q_b$ and $Q_d$ quantification) against a forward search Expected Minimax (EMM) solver.

Performance: The ASP-based approach is competitive with forward search on small stochastic games. In many instances (e.g., Tic-Tac-Toe, Connect-3), the ASP solver computes winning probabilities comparable to EMM, often within similar timeframes.
Quantifier Shifting: Surprisingly, the dependency-based quantification ( $Q_d$ ) did not yield significant performance improvements over the baseline ( $Q_b$ ) when using the SharpSSAT solver. The authors attribute this to SharpSSAT's internal unit propagation mechanism, which can derive values of atoms (like legal) regardless of the quantifier order, effectively mitigating the need for explicit shifting.
Scalability Limits: The approach struggles with larger state spaces, such as Stochastic Nim with large pile sizes. The resulting XSSAT formulas become too large (over one million clauses) for current solvers to handle efficiently, whereas EMM scales well due to dynamic programming and transposition tables.

Significance and Claims

The paper claims that the proposed ASP-based approach provides a viable alternative for endgame evaluation in General Game Playing systems. By extending the successful application of ASP to deterministic games into the stochastic domain, the work demonstrates that logic programming can effectively handle uncertainty and adversarial reasoning.

The authors modestly note that while the approach does not dominate forward search in all cases (particularly for games with very large state spaces or specific structures like Nim), it successfully generalizes previous results for deterministic games to stochastic ones. They identify the extension to partial observability (e.g., Poker, Krieg-Tic-Tac-Toe) as a critical direction for future work, acknowledging that the current method is limited to perfect-information games.