The Complexity of Playing Durak
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 109-114.
Abstract
Durak is a Russian card game in which players try to get rid of all their cards via a particular attack/defense mechanism. The last player standing with cards loses. We show that, even restricted to the perfect information two-player game, finding optimal moves is a hard problem. More precisely, we prove that, given a generalized Durak position, it is PSPACE-complete to decide if a player has a winning strategy. We also show that deciding if an attack can be answered is NP-hard.
Edouard Bonnet. 2016. The Complexity of Playing Durak. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 109–114. https://ijcai.org/proceedings/2016/23
Bonnet, E. (2016). The Complexity of Playing Durak. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 (pp. 109–114). IJCAI. https://ijcai.org/proceedings/2016/23
@inproceedings{ijcai2016p23,
title = {The Complexity of Playing Durak},
author = {Bonnet, Edouard},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {109--114},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/23},
}
TY - CPAPER TI - The Complexity of Playing Durak AU - Bonnet, Edouard T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 109 EP - 114 UR - https://ijcai.org/proceedings/2016/23 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
