The complexity of playing durak
Édouard Bonnet · SZTAKI Publication Repository (Hungarian Academy of Sciences) · 2016
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.