HackerPapers

arXiv:1003.2851cs.DM

The complexity of UNO

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

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

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.

arXiv comments
13 body pages, 2 appendix pages, 1 table, 7 figures
Journal reference
DOI
Subjects
cs.DMDiscrete Mathematics cs.CCComputational Complexity

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Nov 2018 to Nov 2018. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.