Automatic synthesis of generalized winning strategies of impartial combinatorial games  (CCF B)

Kaisheng Wu; Yong Qiao; Kaidong Chen; Fei Rong; Liangda Fang; Zhao Rong Lai; Qian Dong; Liping Xiong

Automatic synthesis of generalized winning strategies of impartial combinatorial games (CCF B)

Kaisheng Wu, Yong Qiao, Kaidong Chen, Fei Rong, Liangda Fang, Zhao Rong Lai, Qian Dong, Liping Xiong

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

1 Citation (Scopus)

Abstract

One of the challenging problems of impartial combinatorial games (ICGs) is to construct generalized winning strategies for possibly infinitely many states. 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 linear integer arithmetic. We then propose an approach to generating the winning strategy for ICGs. Experimental results on several games demonstrate that our approach is effective in most of these games.

Original language	English
Title of host publication	Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020
Editors	Bo An, Amal El Fallah Seghrouchni, Gita Sukthankar
Publisher	International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages	2041-2043
Number of pages	3
ISBN (Electronic)	9781450375184
Publication status	Published - 2020
Externally published	Yes
Event	19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020 - Virtual, Auckland, New Zealand Duration: 19 May 2020 → …

Publication series

Name	Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume	2020-May
ISSN (Print)	1548-8403
ISSN (Electronic)	1558-2914

Conference

Conference	19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020
Country/Territory	New Zealand
City	Virtual, Auckland
Period	19/05/20 → …

Keywords

Impartial combinatorial games
Strategy synthesis

Cite this

Wu, K., Qiao, Y., Chen, K., Rong, F., Fang, L., Lai, Z. R., Dong, Q., & Xiong, L. (2020). Automatic synthesis of generalized winning strategies of impartial combinatorial games (CCF B). In B. An, A. El Fallah Seghrouchni, & G. Sukthankar (Eds.), Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020 (pp. 2041-2043). (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS; Vol. 2020-May). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

Wu, Kaisheng ; Qiao, Yong ; Chen, Kaidong et al. / Automatic synthesis of generalized winning strategies of impartial combinatorial games (CCF B). Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020. editor / Bo An ; Amal El Fallah Seghrouchni ; Gita Sukthankar. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2020. pp. 2041-2043 (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS).

@inproceedings{d5cab6a6d3cb49ca9bfd85bfc90907af,

title = "Automatic synthesis of generalized winning strategies of impartial combinatorial games (CCF B)",

abstract = "One of the challenging problems of impartial combinatorial games (ICGs) is to construct generalized winning strategies for possibly infinitely many states. 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 linear integer arithmetic. We then propose an approach to generating the winning strategy for ICGs. Experimental results on several games demonstrate that our approach is effective in most of these games.",

keywords = "Impartial combinatorial games, Strategy synthesis",

author = "Kaisheng Wu and Yong Qiao and Kaidong Chen and Fei Rong and Liangda Fang and Lai, {Zhao Rong} and Qian Dong and Liping Xiong",

note = "Funding Information: ∗Liangda Fang is the corresponding author. This work was supported by the Natural Science Foundation of China (Nos. 61603152, 61602210, 61703182, 61772232, 61773179, 61877029 and U1811263). Publisher Copyright: {\textcopyright} 2020 International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS). All rights reserved.; 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020 ; Conference date: 19-05-2020",

year = "2020",

language = "English",

series = "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS",

publisher = "International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)",

pages = "2041--2043",

editor = "Bo An and {El Fallah Seghrouchni}, Amal and Gita Sukthankar",

booktitle = "Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020",

}

Wu, K, Qiao, Y, Chen, K, Rong, F, Fang, L, Lai, ZR, Dong, Q & Xiong, L 2020, Automatic synthesis of generalized winning strategies of impartial combinatorial games (CCF B). in B An, A El Fallah Seghrouchni & G Sukthankar (eds), Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, vol. 2020-May, International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), pp. 2041-2043, 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020, Virtual, Auckland, New Zealand, 19/05/20.

Automatic synthesis of generalized winning strategies of impartial combinatorial games (CCF B). / Wu, Kaisheng; Qiao, Yong; Chen, Kaidong et al.
Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020. ed. / Bo An; Amal El Fallah Seghrouchni; Gita Sukthankar. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2020. p. 2041-2043 (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS; Vol. 2020-May).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - Automatic synthesis of generalized winning strategies of impartial combinatorial games (CCF B)

AU - Wu, Kaisheng

AU - Qiao, Yong

AU - Chen, Kaidong

AU - Rong, Fei

AU - Fang, Liangda

AU - Lai, Zhao Rong

AU - Dong, Qian

AU - Xiong, Liping

N1 - Funding Information: ∗Liangda Fang is the corresponding author. This work was supported by the Natural Science Foundation of China (Nos. 61603152, 61602210, 61703182, 61772232, 61773179, 61877029 and U1811263). Publisher Copyright: © 2020 International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS). All rights reserved.

PY - 2020

Y1 - 2020

N2 - One of the challenging problems of impartial combinatorial games (ICGs) is to construct generalized winning strategies for possibly infinitely many states. 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 linear integer arithmetic. We then propose an approach to generating the winning strategy for ICGs. Experimental results on several games demonstrate that our approach is effective in most of these games.

AB - One of the challenging problems of impartial combinatorial games (ICGs) is to construct generalized winning strategies for possibly infinitely many states. 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 linear integer arithmetic. We then propose an approach to generating the winning strategy for ICGs. Experimental results on several games demonstrate that our approach is effective in most of these games.

KW - Impartial combinatorial games

KW - Strategy synthesis

UR - http://www.scopus.com/inward/record.url?scp=85096657850&partnerID=8YFLogxK

M3 - Conference Proceeding

AN - SCOPUS:85096657850

T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

SP - 2041

EP - 2043

BT - Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020

A2 - An, Bo

A2 - El Fallah Seghrouchni, Amal

A2 - Sukthankar, Gita

PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)

T2 - 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020

Y2 - 19 May 2020

ER -

Wu K, Qiao Y, Chen K, Rong F, Fang L, Lai ZR et al. Automatic synthesis of generalized winning strategies of impartial combinatorial games (CCF B). In An B, El Fallah Seghrouchni A, Sukthankar G, editors, Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS). 2020. p. 2041-2043. (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS).