著者

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

出版者

Elsevier

雑誌

Theoretical Computer Science (ISSN:03043975)

巻号頁・発行日

vol.521, pp.51-61, 2013-11-22

被引用文献数

8

---

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.