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