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

By Jean-François Baffier, Man-Kwun Chiu, Y. Diez, Matias Korman, V. Mitsou, André van Renssen, Marcel Roeloffzen, Yushi Uno. 2016

20 citations recorded by the source corpus.

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

Subfields: Artificial Intelligence, Economics and Econometrics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Economics and Econometrics

In Management Science and Operations Research

Citations in the corpus

The Hanabi Challenge: A New Frontier for AI Research (2019, background): “w that even a single player version of Hanabi where the player has perfect information of all cards (including the order of cards in the deck) is NP-complete, despite removing any need to communicate [19]. 9 Analogously, when humans play Hanabi, players rely on the same mutual assumption of communic”
Re-determinizing Information Set Monte Carlo Tree Search in Hanabi (2019, background): “e that the player possesses - e.g. it is not possible to tell a player that they have no red cards in their hand. No communication about hand contents is permitted apart from the hints. Bafﬁer et al. [4] show formally that Hanabi is NP-complete, and not all games can achieve a perfect score of 25 ev”
Evolving Agents for the Hanabi 2018 CIG Competition (2018, background): “[8], even if we remove all hidden information.”
Evaluating and modelling Hanabi-playing agents (2017, background): “Note that Hanabi has been proven to be NP-Complete even when players have perfect information [2].”