Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara, Takeaki Uno, and Yushi Uno, “UNO is hard, even for a single player”, Theoretical Computer Science, volume 521, February 2014, pages 51–61.

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.

Comments:

This paper is also available from ScienceDirect and as arXiv:1003.2851.

Availability:

The paper is available in PostScript (822k), gzipped PostScript (383k), and PDF (228k).

See information on file formats.

[Google Scholar search]

Related papers:

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