Paper by Martin L. Demaine

Reference:

Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara, Takeaki Uno, and Yushi Uno, “UNO is hard, even for a single player”, in Proceedings of the 5th International Conference on Fun with Algorithms (FUN 2010), Lecture Notes in Computer Science, volume 6099, Ischia, Italy, June 2–4, 2010, pages 133–144.

Abstract:

UNO® is one of the world-wide well-known and popular card games. We investigate UNO from the viewpoint of combinatorial algorithmic game theory by giving some simple and concise mathematical models for it. They include cooperative and uncooperative versions of UNO, for example. As a result of analyzing their computational complexities, we prove that even a single-player version of UNO is NP-complete, while it becomes in P in some restricted cases. We also show that uncooperative two-player's version is PSPACE-complete.

Comments:

This paper is also available from SpringerLink. The full paper is available as arXiv:1003.2851.

Updates:

The claim that two-player Uncooperative Uno is PSPACE-complete (Section 4) is incorrect. In fact, this game is in P! See the corrected journal version of the paper.

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (202k) and PDF (109k).

See information on file formats.

[Google Scholar search]

Related papers:

Uno_TCS (UNO is hard, even for a single player)