JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >
このアイテムの引用には次の識別子を使用してください:
http://hdl.handle.net/10119/9860
|
タイトル: | UNO Is Hard, Even for a Single Player |
著者: | Demaine, Erik D. Demaine, Martin L. Uehara, Ryuhei Uno, Takeaki Uno, Yushi |
キーワード: | UNO computational complexity game and puzzle PSPACE-completeness NP-completeness |
発行日: | 2010 |
出版者: | Springer |
誌名: | Lecture Notes in Computer Science |
巻: | 6099/2010 |
開始ページ: | 133 |
終了ページ: | 144 |
DOI: | 10.1007/978-3-642-13122-6_15 |
抄録: | 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. |
Rights: | This is the author-created version of Springer, Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara, Takeaki Uno, and Yushi Uno, Lecture Notes in Computer Science, 6099/2010, 2010, 133-144. The original publication is available at www.springerlink.com, http://dx.doi.org/10.1007/978-3-642-13122-6_15 |
URI: | http://hdl.handle.net/10119/9860 |
資料タイプ: | author |
出現コレクション: | b10-1. 雑誌掲載論文 (Journal Articles)
|
このアイテムのファイル:
ファイル |
記述 |
サイズ | 形式 |
15190-1.pdf | | 95Kb | Adobe PDF | 見る/開く |
|
当システムに保管されているアイテムはすべて著作権により保護されています。
|