Authors:
Achille Morenville, Eric Piette

Venue:
IEEE Conference on Games (CoG), 2025

Topics:
general game playing, imperfect-information games, belief modeling, constraint satisfaction, knowledge representation

Links: PDF · IEEE · arXiv

In imperfect-information games, agents must reason under uncertainty about hidden aspects of the game state. The Belief Stochastic Game model addresses this challenge by externalizing state estimation to the game model, allowing agents to operate on belief states rather than raw observations.

This paper investigates two approaches for representing belief states: a constraint-based representation using constraint satisfaction problems, and a probabilistic extension based on Belief Propagation to estimate marginal probabilities.

Experimental results show that constraint-based belief representations can achieve performance comparable to probabilistic approaches, suggesting that logical representations alone may be sufficient for effective decision-making in many general game playing settings.

This work contributes to the development of general-purpose AI agents capable of handling uncertainty without relying on game-specific inference mechanisms.

By shifting belief modeling into the game representation itself, the Belief-SG framework enables agents to focus on strategy rather than inference, improving generality across diverse games.

The results highlight an important insight: simpler constraint-based representations may provide a strong and efficient alternative to more complex probabilistic reasoning, particularly in the context of general game playing.

Morenville, A., Piette, E. (2025). Modeling Uncertainty: Constraint-Based Belief States in Imperfect-Information Games. IEEE Conference on Games (CoG).

@inproceedings{morenville2025belief_constraints,
  author    = {Morenville, Achille and Piette, Eric},
  title     = {Modeling Uncertainty: Constraint-Based Belief States in Imperfect-Information Games},
  booktitle = {IEEE Conference on Games (CoG)},
  year      = {2025},
  doi       = {10.1109/COG64752.2025.11114384}
}