A Scalable Solver for 2p0s Differential Games with One-Sided Payoff Information and Continuous Actions, States, and Time

Mukesh Ghimire, Lei Zhang, Zhe Xu, Yi Ren

Abstract

Existing solvers for imperfect-information extensive-form games (IIEFGs) often struggle with scalability in terms of action and state space sizes and the number of time steps. However, many real-world games involve continuous action and state spaces and occur in continuous time, making them differential in nature. This paper addresses the scalability challenges for a representative class of two-player zero-sum (2p0s) differential games where the informed player knows the game type (payoff) while the uninformed one only has a prior belief over the set of possible types. Such games encompass a wide range of attack-defense scenarios, where the defender adapts based on their belief about the attacker's target. We make the following contributions: (1) We show that under the Isaacs' condition, the complexity of computing the Nash equilibrium for these games is not related to the action space size; and (2) we propose a multigrid approach to effectively reduce the cost of these games when many time steps are involved.

Introduction

Solving imperfect-information games, such as Poker or Stratego, is notoriously difficult due to the exponential growth of the "game tree"—the map of all possible moves and counter-moves. For a game with $K$ time steps and an action space of size $U$, the complexity typically scales as $U^{2K}$. This challenge is amplified in real-world scenarios like robotics or sports, where actions and states are continuous (e.g., precise acceleration and angles in a football play). Standard solvers often struggle with discretization or fail to converge.

This paper addresses these scalability challenges for a representative class of two-player zero-sum (2p0s) differential games with one-sided payoff information (2p0s1). In these games, one player (the "Informed" player) knows the exact payoff goal, while the other (the "Uninformed" player) maintains a probabilistic belief over possible goals.

Methodology: Continuous Action Mixed-strategy Solvers (CAMS)

The core contribution of this work is the introduction of CAMS, which exploits a mathematical proof showing that the Nash Equilibrium for 2p0s1 games is atomic.

The CAMS framework: (a) reduction of game tree complexity from $U^{2K}$ to $I^K$ and $(I+1)^K$; (b) 22-player football simulation environment; (c) strategic concealment of intent by the informed player.

As illustrated in Figure 1(a), instead of considering a broad distribution over the continuous action space $U$, players only need to mix between a small number of "prototype" actions. Specifically, the Informed player (P1) mixes between at most $I$ prototypes (where $I$ is the number of possible goals), and the Uninformed player (P2) mixes between $I+1$ prototypes. This collapses the complexity from being dependent on the action space size $U$ to being dependent only on the number of possible goals $I$.

The value function $V$ is the lower convex hull of $\tilde{V}$, demonstrating the atomic structure of the optimal strategy.

The atomic nature of the strategy is tied to the geometric properties of the value function. As shown in Figure 6, the value function $V(t, x, p)$ is the lower convex hull of the "naive" value function $\tilde{V}(t, x, p)$, where $p$ is the belief. The linear segments of the hull correspond to the mixing of atomic strategies. To implement this efficiently, CAMS utilizes a Primal-Dual Reformulation to solve for both players' strategies and a Multigrid Value Approximation (coarse-to-fine grid approach) to solve the underlying Hamilton-Jacobi partial differential equations.

Experimental Evaluation

The authors evaluated CAMS on two primary benchmarks:

  • Hexner’s Game: A control theory classic used to verify accuracy against known analytical solutions.
  • 11-vs-11 American Football: A high-dimensional simulation with 22 players featuring double-integrator kinematics and "soft tackle" dynamics. The offense (Informed player) chooses between two "types": a "Running Back Power Push" or a "Quarterback Throw."

Key Results

  • Scalability: The football simulation, which has a theoretical complexity of $10^{440}$ even with coarse discretization, was solved in less than 30 minutes on a standard laptop (M1 Pro MacBook).
  • Efficiency: The Multigrid approach significantly reduced runtime. In Hexner's game, it cut the time for a 16-stage game from 46.2 hours to 17.8 hours while maintaining high accuracy.
  • Strategic Concealment: The solver naturally discovered "deceptive" behavior. As seen in Figure 1(c), the offense (P1) conceals its true intent for the first 0.5 seconds, keeping the defender's belief at the prior until a positional advantage is secured. This "action-size invariance" ensures performance doesn't degrade as the action space becomes more granular.

Conclusion

CAMS demonstrates that exploiting the atomic structure of equilibria in one-sided information games allows for solving high-dimensional, continuous-time problems that were previously intractable. While currently limited to deterministic dynamics, future work aims to extend these "atomic" properties to stochastic environments, potentially enabling real-time strategic AI for complex team sports and physical robotics.

Summary updated

Abstract

Existing solvers for imperfect-information extensive-form games (IIEFGs) often struggle with scalability in terms of action and state space sizes and the number of time steps. However, many real-world games involve continuous action and state spaces and occur in continuous time, making them differential in nature. This paper addresses the scalability challenges for a representative class of two-player zero-sum (2p0s) differential games where the informed player knows the game type (payoff) while the uninformed one only has a prior belief over the set of possible types. Such games encompass a wide range of attack-defense scenarios, where the defender adapts based on their belief about the attacker's target. We make the following contributions: (1) We show that under the Isaacs' condition, the complexity of computing the Nash equilibrium for these games is not related to the action space size; and (2) we propose a multigrid approach to effectively reduce the cost of these games when many time steps are involved. Code for this work is available at https://github.com/ghimiremukesh/cams/tree/conf_sub.
BibTeX
@misc{ghimire2025scalable,
  author = {Mukesh Ghimire and Lei Zhang and Zhe Xu and Yi Ren},
  title = {{A Scalable Solver for 2p0s Differential Games with One-Sided Payoff Information and Continuous Actions, States, and Time}},
  year = {2025},
  eprint = {2502.00560},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.00560},
}

Loading related content...

Figure