---
title: "The Complexity of Playing Durak"
authors:
  - "Edouard Bonnet"
doi: ""
url: "https://ijcai.org/proceedings/2016/23"
pdf: "https://ijcai.org/proceedings/2016/0023.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "109-114"
track: ""
keywords:
---

# The Complexity of Playing Durak

Edouard Bonnet

*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.