License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2016.4
URN: urn:nbn:de:0030-drops-58644
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5864/
Go to the corresponding LIPIcs Volume Portal

Baffier, Jean-Francois ; Chiu, Man-Kwun ; Diez, Yago ; Korman, Matias ; Mitsou, Valia ; van Renssen, André ; Roeloffzen, Marcel ; Uno, Yushi

Hanabi is NP-complete, Even for Cheaters who Look at Their Cards

pdf-format:
4.pdf (0.5 MB)

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

BibTeX - Entry

@InProceedings{baffier_et_al:LIPIcs:2016:5864,
  author =	{Jean-Francois Baffier and Man-Kwun Chiu and Yago Diez and Matias Korman and Valia Mitsou and Andr{\'e} van Renssen and Marcel Roeloffzen and Yushi Uno},
  title =	{{Hanabi is NP-complete, Even for Cheaters who Look at Their Cards}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Erik D. Demaine and Fabrizio Grandoni},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5864},
  URN =		{urn:nbn:de:0030-drops-58644},
  doi =		{10.4230/LIPIcs.FUN.2016.4},
  annote =	{Keywords: algorithmic combinatorial game theory, sorting}
}

Keywords: algorithmic combinatorial game theory, sorting
Collection: 8th International Conference on Fun with Algorithms (FUN 2016)
Issue Date: 2016
Date of publication: 02.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI