Abstract

Single-player deduction games are a canonical form of hidden-information reasoning. Agents iteratively issue actions (queries) and receive deterministic feedback, thereby shrinking the information set of feasible secret codes. Classical search techniques—such as Information-Set Monte-Carlo Tree Search (ISMCTS) or the entropy-driven Information-Set Entropy Search (ISES)—handle these games by sampling or enumerating states, but both struggle when the combinatorial space explodes. We introduce a constraint-propagation variant of ISES that models the information set as a constraint-satisfaction problem (CSP) and applies the AC-3 arc-consistency algorithm after every observation. By aggressively pruning unsupported variable values before entropy evaluation, our method eliminates many impossible states and accelerates inference without sacrificing optimality. Case studies on several single-player deduction games from the Deduction Game Framework demonstrate that constraint propagation significantly enhances ISES efficiency.

Citation

Meng, F., Xu, K., & Lucas, S. (2025, August). Constraint Propagation for Reasoning in Single-player Deduction Games. In 2025 IEEE Conference on Games (CoG) (pp. 1-4). IEEE.

@inproceedings{meng2025constraint,
  author    = {Fangyi Meng and Kaijie Xu and Simon Lucas},
  title     = {Constraint Propagation for Reasoning in Single-player Deduction Games},
  booktitle = {2025 IEEE Conference on Games (CoG)},
  pages     = {1-4},
  year      = {2025},
  month     = {Aug},
  organization={IEEE}
}