# Modeling Uncertainty: Constraint-Based Belief States in Imperfect-Information Games

arXiv: https://arxiv.org/abs/2507.19263 · HTML: https://mlsanity.com/paper/2507.19263/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 21 references that are in the map.
- First posted on arXiv 25 Jul 2025.

## Builds on (most cited first, 5 of 5)

- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Rethinking Formal Models of Partially Observable Multiagent Decision Making](https://mlsanity.com/paper/1906.11110/) (2019)
- [Solving Imperfect Information Games Using Decomposition](https://mlsanity.com/paper/1303.4441/) (2013)
- [Student of Games: A unified learning algorithm for both perfect and imperfect information games](https://mlsanity.com/paper/2112.03178/) (2021)
- [Problems with the EFG formalism: a solution attempt using observations](https://mlsanity.com/paper/1906.06291/) (2019)

## Built on by (most cited first, 1 of 1)

- [Valet: A Standardized Testbed of Traditional Imperfect-Information Card Games](https://mlsanity.com/paper/2603.03252/) (2026)

## Abstract (arXiv)

In imperfect-information games, agents must make decisions based on partial knowledge of the game state. The Belief Stochastic Game model addresses this challenge by delegating state estimation to the game model itself. This allows agents to operate on externally provided belief states, thereby reducing the need for game-specific inference logic. This paper investigates two approaches to represent beliefs in games with hidden piece identities: a constraint-based model using Constraint Satisfaction Problems and a probabilistic extension using Belief Propagation to estimate marginal probabilities. We evaluated the impact of both representations using general-purpose agents across two different games. Our findings indicate that constraint-based beliefs yield results comparable to those of probabilistic inference, with minimal differences in agent performance. This suggests that constraint-based belief states alone may suffice for effective decision-making in many settings.