The complexity of UNO

Erik D. Demaine, Martin L. Demaine, Nicholas J. A. Harvey, Ryuhei Uehara, Takeaki Uno, Yushi Uno

Abstract

This paper investigates the popular card game UNO from the viewpoint of algorithmic combinatorial game theory. We define simple and concise mathematical models for the game, including both cooperative and uncooperative versions, and analyze their computational complexity. In particular, we prove that even a single-player version of UNO is NP-complete, although some restricted cases are in P. Surprisingly, we show that the uncooperative two-player version is also in P.

Introduction

While games like Chess, Go, and even Tetris have long been the subjects of rigorous mathematical study, the popular card game UNO had remained largely unexamined by the algorithmic combinatorial game theory community. This research bridges the gap by formalizing UNO's mechanics to determine the computational complexity of deciding if a player can win given a specific hand. The study explores three primary variations: Solitaire UNO (single player), Cooperative UNO (two players working together), and Uncooperative UNO (two players playing optimally against each other).

Methodology

The researchers simplified UNO to its core mechanic: matching a card's color or number to the one previously played. Action cards (e.g., Skip, Draw Two) and the draw pile were excluded to isolate the fundamental matching logic. The "data" for this theoretical study consists of mathematical instances of card sets and player hands constructed to prove complexity bounds.

Graph Theory and Reductions

The game is modeled using "UNO graphs," where each card is a vertex and edges represent valid consecutive plays. To prove NP-completeness for Solitaire UNO, the authors performed a reduction from the Hamiltonian Path problem. This involves constructing a gadget where each vertex $v$ of a graph is replaced by a triangle of vertices representing the incident edges, as shown below.

Vertex-to-triangle gadget for Hamiltonian Path reduction.

Dynamic Programming and Game Theory

For restricted cases, such as a fixed number of colors, a geometric dynamic programming (DP) algorithm was developed. For the uncooperative version, the problem was reduced to Undirected Vertex Geography, which is solvable in polynomial time using maximum matching algorithms.

Key Insights

A central discovery is that Solitaire UNO is equivalent to finding a Hamiltonian path in the line graph of a bipartite graph. Furthermore, the study highlights a "cooperative paradox": while adding players usually increases complexity, Cooperative Two-Player UNO is NP-complete, whereas Uncooperative Two-Player UNO is in P. This makes UNO a rare example where competition is computationally easier than cooperation.

Geometric Interpretation

By representing a card $(color, number)$ as a point $(x, y)$ in a 2D plane, the game becomes a challenge of visiting points using only horizontal (same number) or vertical (same color) moves.

Geometric representation of UNO as a path on a grid.

Results

The complexity results are summarized below:

Model Complexity Reference
Solitaire UNO (Uno-1) NP-complete Theorem 3
Solitaire UNO (fixed colors or numbers) Polynomial (P) Theorem 4
Cooperative UNO-2 NP-complete Theorem 1
Uncooperative UNO-2 Polynomial (P) Theorem 6

Conclusion and Future Work

The current models provide a foundation but exclude action cards, imperfect information, and the draw pile. Future research could incorporate these elements or investigate "Minimum Card Fill-in"—the minimum cards needed to turn a losing hand into a winning one. The complexity of Cooperative UNO-2 with a constant number of colors also remains an open question.

Summary updated

Abstract

This paper investigates the popular card game UNO from the viewpoint of algorithmic combinatorial game theory. We define simple and concise mathematical models for the game, including both cooperative and uncooperative versions, and analyze their computational complexity. In particular, we prove that even a single-player version of UNO is NP-complete, although some restricted cases are in P. Surprisingly, we show that the uncooperative two-player version is also in P.
BibTeX
@misc{demaine2010complexity,
  author = {Erik D. Demaine and Martin L. Demaine and Nicholas J. A. Harvey and Ryuhei Uehara and Takeaki Uno and Yushi Uno},
  title = {{The complexity of UNO}},
  year = {2010},
  eprint = {1003.2851},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1003.2851},
}
Figure