LIPIcs.FUN.2016.4.pdf
- Filesize: 0.54 MB
- 17 pages
Document
Hanabi is NP-complete, Even for Cheaters who Look at Their Cards
Authors
-
Part of:
Volume:
8th International Conference on Fun with Algorithms (FUN 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-06-02
Cite As Get BibTex
Jean-Francois Baffier, Man-Kwun Chiu, Yago Diez, Matias Korman, Valia Mitsou, André van Renssen, Marcel Roeloffzen, and Yushi Uno. Hanabi is NP-complete, Even for Cheaters who Look at Their Cards. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FUN.2016.4
Abstract
This paper studies a cooperative card game called Hanabi from an algorithmic combinatorial game theory viewpoint. The aim of the game is to play cards from 1 to n in increasing order (this has to be done independently in c different colors). Cards are drawn from a deck one by one. Drawn cards are either immediately played, discarded or stored for future use (overall each player can store up to h cards). The main feature of the game is that players know the cards their partners hold (but not theirs. This information must be shared through hints). We introduce a simplified mathematical model of a single-player version of the game, and show several complexity results: the game is intractable in a general setting even if we forego with the hidden information aspect of the game. On the positive side, the game can be solved in linear time for some interesting restricted cases (i.e., for small values of h and c).
Subject Classification
Keywords
- algorithmic combinatorial game theory
- sorting
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Antoine Bauza. Hanabi. URL: http://www.antoinebauza.fr/?tag=hanabi.
- BoardGameGeek. URL: https://boardgamegeek.com/boardgame/98778/hanabi.
- Alex Churchill. Magic: The gathering is Turing complete. Unpublished manuscript available at http://www.toothycat.net/~hologram/Turing/index.html.
-
Christopher Cox, Jessica De Silva, Philip Deorsey, Franklin H. J. Kenter, Troy Retter, and Josh Tobin. How to make the perfect fireworks display: Two strategies for Hanabi. Mathematics Magazine, 88(5):323-336, 2015.
-
Erik D. Demaine. Personal communication.
-
Erik D. Demaine. Playing games with algorithms: Algorithmic combinatorial game theory. CoRR, cs.CC/0106019v2, 2008.
-
Erik D. Demaine, Martin L. Demaine, Nicholas J. A. Harvey, Ryuhei Uehara, Takeaki Uno, and Yushi Uno. UNO is hard, even for a single player. Theor. Comp. Sci., 521:51-61, 2014.
- Spiel des Jahres award. URL: http://www.spieldesjahres.de/en/hanabi.
-
Aviezri S. Fraenkel and David Lichtenstein. Computing a perfect strategy for n x n chess requires time exponential in n. J. Comb. Theory, Ser. A, 31(2):199-214, 1981.
-
Martin Gardner. Mathematical Games: The Entire Collection of His Scientific American Columns. The Mathematical Association of America, 2005.
-
Robert Hearn and Erik D. Demaine. Games, Puzzles, and Computation. A. K. Peters, 2009.
-
Michael Lampis and Valia Mitsou. The computational complexity of the game of set and its theoretical applications. In 11^th Latin American Symposium, pages 24-34. Springer, 2014.
-
Kenichiro Nakai and Yasuhiko Takenaga. NP-completeness of pandemic. JIP, 20(3):723-726, 2012.
-
Hirotaka Osawa. Solving Hanabi: Estimating hands by opponent’s actions in cooperative game with incomplete information. In AAAI workshop: Computer Poker and Imperfect Information, pages 37-43, 2015.