Constraint-Based Symmetry Detection in General Game Playing
| Autor: | Éric Piette, Frédéric Koriche, Sylvain Lagrue, Sébastien Tabary |
|---|---|
| Přispěvatelé: | Centre de Recherche en Informatique de Lens (CRIL), Université d'Artois (UA)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
[INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT]
Computer science [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] 02 engineering and technology computer.software_genre General game playing [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] Algebra Constraint (information theory) 020204 information systems 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Simultaneous game Symmetry (geometry) computer ComputingMilieux_MISCELLANEOUS |
| Zdroj: | The International Joint Conference on Artificial Intelligence: (IJCAI'17) The International Joint Conference on Artificial Intelligence Twenty-Sixth International Joint Conference on Artificial Intelligence Twenty-Sixth International Joint Conference on Artificial Intelligence, Aug 2017, Melbourne, Australia. pp.280-287, ⟨10.24963/ijcai.2017/40⟩ IJCAI |
| DOI: | 10.24963/ijcai.2017/40⟩ |
| Popis: | 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 themicrostructure 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|