Automatic Synthesis of Generalized Winning Strategies of Impartial Combinatorial Games Using SMT Solvers
Abstract
Strategy representation and reasoning has recently received much attention in artificial intelligence. Impartial combinatorial games (ICGs) are a type of elementary and fundamental games in game theory. One of the challenging problems of ICGs is to construct winning strategies, particularly, generalized winning strategies for possibly infinitely many instances of ICGs. In this paper, we investigate synthesizing generalized winning strategies for ICGs. To this end, we first propose a logical framework to formalize ICGs based on the linear integer arithmetic fragment of numeric part of PDDL. We then propose an approach to generating the winning formula that exactly captures the states in which the player can force to win. Furthermore, we compute winning strategies for ICGs based on the winning formula. Experimental results on several games demonstrate the effectiveness of our approach.
Cite
Text
Wu et al. "Automatic Synthesis of Generalized Winning Strategies of Impartial Combinatorial Games Using SMT Solvers." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/236Markdown
[Wu et al. "Automatic Synthesis of Generalized Winning Strategies of Impartial Combinatorial Games Using SMT Solvers." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/wu2020ijcai-automatic/) doi:10.24963/IJCAI.2020/236BibTeX
@inproceedings{wu2020ijcai-automatic,
title = {{Automatic Synthesis of Generalized Winning Strategies of Impartial Combinatorial Games Using SMT Solvers}},
author = {Wu, Kaisheng and Fang, Liangda and Xiong, Liping and Lai, Zhao-Rong and Qiao, Yong and Chen, Kaidong and Rong, Fei},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2020},
pages = {1703-1711},
doi = {10.24963/IJCAI.2020/236},
url = {https://mlanthology.org/ijcai/2020/wu2020ijcai-automatic/}
}