Quantified Boolean Solving for Achievement Games
| Autor: | Steve Boucher, Roger Villemaire |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | KI 2021: Advances in Artificial Intelligence ISBN: 9783030876258 KI |
| DOI: | 10.1007/978-3-030-87626-5_3 |
| Popis: | Recent developments in the propositional representation of achievement games have renewed interest in applying the latest advances in Quantified Boolean Formula technologies to solving these games. However, the number of quantifier alternations necessary to explore the solution space still impairs and limits the applicability of these methods. In this paper, we show that one can encode blocking strategies for the second player and express the last moves of the play with a single string of existential quantifiers, instead of the usual alternations of universal and existential quantifiers. We experimentally show that our method improves the performance of state-of-the-art Quantified Boolean Formula solvers on Harary’s Tic-Tac-Toe, a well-known achievement game. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|