UNO is hard, even for a single player

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

作者机构：MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Univ British Columbia Fac Sci Dept Comp Sci Vancouver BC V6T 1Z4 Canada JAIST Sch Informat Sci Nomi Ishikawa 9231292 Japan Res Org Informat & Syst Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan Osaka Prefecture Univ Grad Sch Sci Dept Math & Informat Sci Sakai Osaka 5998531 Japan 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2014年第521卷第0期

页      面：51-61页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：KAKENHI [23500022, 25106508] Funding Program for World-Leading Innovative R&D on Science and Technology, Japan Grants-in-Aid for Scientific Research [23500022, 24106004, 23500013, 25106508] Funding Source: KAKEN 

主　　题：Algorithmic combinatorial game theory Dynamic programming Hamiltonian path Mathematical puzzles/games 

摘      要：This paper investigates the popular card game UNO (R) 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. (c) 2013 Elsevier B.V. All rights reserved.