UNO Is Hard, Even for a Single Player

• Demaine, Erik D.

• Demaine, Martin L.

• Uehara, Ryuhei

• Uno, Takeaki

• Uno, Yushi

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 includecooperative 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.

Fun with Algorithms : 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010.

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/9860

Journal

• Lecture Notes in Computer Science

  Lecture Notes in Computer Science 6099/2010 133-144, 2010

  Springer

Keywords

• UNO
• computational complexity
• game and puzzle
• PSPACE-completeness
• NP-completeness

Details

• CRID: 1050564287491720320
• NII Article ID: 120003184351
• ISSN: 03029743
• Web Site: http://hdl.handle.net/10119/9860
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • CiNii Articles