Abstract
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