The game Hanabi is a cooperative, hidden-information game. You can read the rules elsewhere, but broadly speaking the players are attempting to cooperatively build a fireworks display by playing cards from their hand. The goal is to get as high a score as possible, by playing as many valid fireworks card as possible. The catch is that you hold your cards facing away from you, so without information from other players you are just blindly guessing which card to play. On your turn, you can either

- Play a card (without looking at it). If it is not valid, there is a penalty.
- Give a clue to another player. This uses up a clue token, and the clues are of a restricted form.
- Discard a card. This gets a clue token back.

My question is: is the game NEXPTIME-complete? In order to put it into the framework of a formal game, we should think of it as a game with two sides: all the players (collectively), and Nature, who shuffled the deck and deals out the cards when players draw new cards. This then fits it into the context of a team game with hidden information, in the language of Hearn and Demaine's book Games, Puzzles, and Computation. More precisely, in their language, it is a bounded team game with hidden information. According to the handy chart in their book, a "generic" such game is expected to be NEXPTIME-complete: $$ \begin{array}{rcccc} & \mathrm{0\ player} & \mathrm{1\ player} & \mathrm{2\ player} & \mathrm{Team} \\ \mathrm{Bounded} & \mathrm{P} & \mathrm{NP} & \mathrm{PSPACE} & \mathrm{NEXPTIME} \\ \mathrm{Unbounded} & \mathrm{PSPACE} & \mathrm{PSPACE} & \mathrm{EXPTIME} & \mathrm{RE\ (undecidable)} \end{array} $$ For everything that isn't in the "Team" column, many examples of real games of the given complexity class are known. But as far as I know, no games of the "generic" complexity class are know in the team case. Hanabi strikes me as a good candidate, as it has (a) a fairly simple rule set but (b) in practice, requires quite complicated deductions about other player's states of knowledge.

Of course, to make this a precise question, the game needs to be suitably generalized, increasing the number of colors and/or cards of a given color. A precise problem also has to be given: probably the problem of "given this initial play state, common knowledge to all players, do the players have a strategy that guarantees a win?"

One complication is going to be that the optimal strategy will almost certainly be quite artificial, of the form of giving a clue that is a hash function of all the cards that you can see. Maybe there's some way to vary the rules to forbid such conventions. (Perhaps just restricting to the two player case.)

Has anyone thought about this problem?

5more comments