Modeling Uncertainty: Constraint-Based Belief States in Imperfect-Information Games
This work addresses uncertainty modeling for agents in games with hidden information, but it is incremental as it builds on existing belief state frameworks.
The paper tackled the problem of decision-making in imperfect-information games by comparing constraint-based and probabilistic belief representations, finding that constraint-based beliefs performed comparably to probabilistic inference with minimal differences in agent performance.
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.