The Complexity of Playing Durak
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. PDF
Cite
Text
Bonnet. "The Complexity of Playing Durak." International Joint Conference on Artificial Intelligence, 2016.Markdown
[Bonnet. "The Complexity of Playing Durak." International Joint Conference on Artificial Intelligence, 2016.](https://mlanthology.org/ijcai/2016/bonnet2016ijcai-complexity/)BibTeX
@inproceedings{bonnet2016ijcai-complexity,
title = {{The Complexity of Playing Durak}},
author = {Bonnet, Édouard},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2016},
pages = {109-115},
url = {https://mlanthology.org/ijcai/2016/bonnet2016ijcai-complexity/}
}