Takeaki Uno

  1. The complexity of UNO.

    Authors: Erik D. Demaine, Martin L. Demaine, Yushi Uno, Ryuhei Uehara, Takeaki Uno
    Subjects: Discrete Mathematics
    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 include
    cooperative 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.

RSS-материал