Paper by Martin L. Demaine
- 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.
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.
- This paper is also available from ScienceDirect and as arXiv:1003.2851.
- 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)
See also other papers by Martin Demaine.
These pages are generated automagically from a
Last updated by