Authors:
Cédric Piette, Eric Piette, Matthew Stephenson, Dennis J. N. J. Soemers, Cameron Browne

Venue:
IEEE Conference on Games (CoG), 2019

DOI:
10.1109/CIG.2019.8848086

Topics:
Ludii, constraint programming, XCSP, logic puzzles, CSP, general game systems

Links: PDF · IEEE / ACM entry · arXiv

Many logic puzzles are NP-complete problems, making them natural candidates for constraint programming approaches.

This paper presents how puzzles modelled in the Ludii general game system can be translated into the XCSP formalism, allowing them to be solved using state-of-the-art constraint solvers.

The approach enables Ludii to support efficient solving, analysis, and assistance for a wide range of puzzles, bridging general game systems and constraint programming.

This work connects two major paradigms: general game systems and constraint programming.

It shows that Ludii can go beyond simulation-based AI (e.g., MCTS) by leveraging symbolic and exact solving techniques for structured problems such as logic puzzles.

The translation to XCSP makes it possible to reuse decades of advances in CSP solvers, enabling efficient solving, explanation, and assistance features for puzzles modelled in Ludii.

Piette, C., Piette, E., Stephenson, M., Soemers, D. J. N. J., Browne, C. (2019). Ludii and XCSP: Playing and Solving Logic Puzzles. In Proceedings of the IEEE Conference on Games (CoG). DOI: 10.1109/CIG.2019.8848086

@inproceedings{piette2019xcsp,
  author    = {Piette, Cédric and Piette, Eric and Stephenson, Matthew and Soemers, Dennis J. N. J. and Browne, Cameron},
  title     = {Ludii and XCSP: Playing and Solving Logic Puzzles},
  booktitle = {Proceedings of the IEEE Conference on Games (CoG)},
  year      = {2019},
  doi       = {10.1109/CIG.2019.8848086},
  url       = {https://arxiv.org/abs/1907.00245}
}