Hanabi is NP-complete, Even for Cheaters who Look at Their Cards
© Jean Francois Baffier, Man-Kwun Chiu, Yago Diez, Matias Korman, Valia Mitsou, André van Renssen, Marcel Roeloffzen, and Yushi Uno;
licensed under Creative Commons License CC-BY
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). 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, but becomes tractable (and even linear) in some interesting restricted cases (i.e., for small values of h and c).