The Complexity of Playing Durak

Édouard BonnetIJCAI 2016

Abstract

This study explores the computational complexity of Durak, a popular Russian card game characterized by its unique attack/defense mechanics. We demonstrate that determining a winning strategy in a generalized, perfect-information version of the game is PSPACE-complete. Additionally, we show that the sub-problem of deciding if a player can defend against a single round of attacks is NP-hard. These findings categorize Durak alongside high-complexity games like Hex and Go.

Introduction

While the complexity of board games like Chess and Go is well-established, card games—particularly those without trick-taking mechanics—remain less explored. Durak (Russian for "fool") is an endgame-focused game where players attempt to empty their hands to avoid being the last player left with cards. This paper bridges the gap in game complexity literature by analyzing a generalized version of Durak featuring $s$ suits, $r$ ranks, and an attack threshold $y$.

Methodology

The research employs reductions from known hard problems to Durak's mechanics. To establish NP-hardness for the defense phase, the author reduces 3-SAT to a single round of play. Suits and ranks represent variables and clauses, requiring the defender to strategically choose cards to "satisfy" the defense.

Figure 2: A generalized Durak position representing a reduction from a boolean formula, mapping variables and clauses to game states.

PSPACE-Completeness and Gadget Design

The core of the PSPACE-completeness proof lies in the design of gadgets that force players into specific move sequences. By defining "weaknesses"—ranks where an opponent holds superior cards in all relevant suits—the author creates states where a player must play optimally to avoid immediate loss. These gadgets allow the game to simulate the logic of quantified boolean formulas.

Figure 4: The variable gadget used in the PSPACE reduction, showing how card distributions simulate true and false assignments.

A critical component of the PSPACE classification is the game's termination. The author proves that any game of Durak with $n$ cards must conclude within $O(n^3)$ moves. This polynomial bound ensures that the game state space can be explored using polynomial memory, preventing the complexity from escalating to EXPTIME.

Key Insights

  • Defense Complexity: Even with perfect information, determining the optimal defense against a multi-card attack is NP-hard due to the combinatorial explosion of possible rank-based additions by the attacker.
  • The Attack Threshold ($y$): The limit on the number of cards played per round is a vital constraint that keeps the game within PSPACE.
  • Endgame Depth: The "fool" mechanic, where the goal is to avoid losing rather than to "win" in a traditional sense, creates a deep strategic landscape in the perfect-information endgame.

Conclusion and Future Work

This work establishes Durak as a PSPACE-complete challenge. Future research may explore whether the game remains PSPACE-hard without the attack threshold ($y = \infty$) or if single-suit variants allow for polynomial-time solutions. Additionally, the transition from perfect information to the standard game's hidden information (draw piles and trumps) suggests even higher complexity classes, potentially involving POMDPs.

Summary updated

BibTeX
@inproceedings{bonnet2016complexity,
  author = {Édouard Bonnet},
  title = {{The Complexity of Playing Durak}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure