The Complexity of Playing Durak / 109
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.