Published on Mon Mar 07 2016
Hanabi is NP-hard, even for cheaters who look at their cards
See More ...
In this paper we study a cooperative card game called Hanabi from the
viewpoint of algorithmic combinatorial game theory. In Hanabi, each card has
one among $c$ colors and a number between $1$ and $n$. The aim is to make, for
each color, a pile of cards of that color with all increasing numbers from $1$
to $n$. At each time during the game, each player holds $h$ cards in hand.
Cards are drawn sequentially from a deck and the players should decide whether
to play, discard or store them for future use. One of the features of the game
is that the players can see their partners' cards but not their own and
information must be shared through hints.
We introduce a single-player, perfect-information model and show that the
game is intractable even for this simplified version where we forego both the
hidden information and the multiplayer aspect of the game, even when the player
can only hold two cards in her hand. On the positive side, we show that the
decision version of the problem---to decide whether or not numbers from $1$
through $n$ can be played for every color---can be solved in (almost) linear
time for some restricted cases.