Hanabi

A cooperative card game in which players can see others' cards but not their own. Players exchange hints with the goal of playing the cards in a specific order.

Description

Hanabi is a a cooperative multiplayer card game with imperfect information. An hanabi card $(v,c)$ consists of an integer value $v$ between $1$ an $n$ and of a color $c$ out of $C$ possible. Up to $r$ copies of the same card might appear in an deck consisting of $N \le n \cdot c \cdot h$ cards. Throught the game, the cards held by one player are only visible by the other players. Additionally, players share a certain number of information tokens.

At the beginnign of the game Players draw $h$ cards each. Then, the players play in turns, where each turn consits of one of the following actions:

The game terminates whenever one of the following conditions holds:

When the game ends, it is scored by summing the values of the highest-value card of each color that has been successfully played.

In the classical version of the game $n=5$, $c=5$ (white, yellow, green, blue, and red), $h \in {4,5}$, the game ends after $3$ mistakes, and the number of information tokens is $3$.

Computational complexity

The variant in which there is a unique player with full knowledge over the order of the cards in the deck has been considered in [1]. In this variant the player draws a card and can discard it, store it for later, or play it right away along with any number of stored cards. Up to $h$ cards can be stored, which corresponds to an hand size of $h+1$ in the original game. The goal is to determine whether there is a strategy that (successfully) plays all the cards of values $1,2,…, n$ for each color.

The results for the above variant are as follows [1]:

References

[1] J.-F. Baffier, M.-K. Chiu, Y. Diez, M. Korman, V. Mitsou, A. van Renssen, M. Roeloffzen, Y. Uno, “Hanabi is NP-hard, even for cheaters who look at their cards”, Theoretical Computer Science, 2017.