Authors:
Frédéric Koriche, Sylvain Lagrue, Éric Piette, Sébastien Tabary

Venue:
Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 2017

Pages:
280–287

Topics:
General Game Playing, symmetry detection, stochastic CSP, minimax, search reduction

Links: PDF · IJCAI proceedings · ACM Digital Library

Symmetry detection is a promising approach for reducing the search tree of games. In General Game Playing (GGP), where any game is compactly represented by a set of rules in the Game Description Language (GDL), the state-of-the-art methods for symmetry detection rely on a rule graph associated with the GDL description of the game. Though such rule-based symmetry detection methods can be applied to various tree search algorithms, they cover only a limited number of symmetries which are apparent in the GDL description.

In this paper, we develop an alternative approach to symmetry detection in stochastic games that exploits constraint programming techniques. The minimax optimization problem in a GDL game is cast as a stochastic constraint satisfaction problem (SCSP), which can be viewed as a sequence of one-stage SCSPs. Minimax symmetries are inferred according to the microstructure complement of these one-stage constraint networks.

Based on a theoretical analysis of this approach, we experimentally show on various games that the recent stochastic constraint solver MAC-UCB, coupled with constraint-based symmetry detection, significantly outperforms the standard Monte Carlo Tree Search algorithms, coupled with rule-based symmetry detection. This constraint-driven approach is also validated by the excellent results obtained by our player during the last GGP competition.

This paper is a major contribution on the role of symmetry detection in General Game Playing. Instead of relying only on symmetries that are explicit in the GDL rule graph, it proposes a constraint-based approach capable of capturing deeper structural regularities connected to minimax strategies.

It also strengthens the broader research direction developed in this line of work: using stochastic constraint programming not only for representing games, but also for improving search efficiency and competitive play in general game-playing agents.

The paper further supports the competitive results obtained with WoodStock, including its success in the 2016 International General Game Playing Competition.

Koriche, F., Lagrue, S., Piette, É., Tabary, S. (2017). Constraint-Based Symmetry Detection in General Game Playing. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), pp. 280–287.

@inproceedings{koriche2017symmetry,
  author    = {Koriche, Fr{\'e}d{\'e}ric and Lagrue, Sylvain and Piette, {\'E}ric and Tabary, S{\'e}bastien},
  title     = {Constraint-Based Symmetry Detection in General Game Playing},
  booktitle = {Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI)},
  pages     = {280--287},
  year      = {2017}
}