# Is the game Hanabi NEXPTIME-complete?

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

• Lots of upvotes here, but no answers or discussion! Does anyone know any related work? – Dylan Thurston Oct 28 '15 at 2:34
• I think this question would be more suitable for cstheory.stackexchange.com. I also think that from any position any player can calculate the optimal move by going through all combinations in a brute force search and computing probabilities in PSPACE. – domotorp Nov 1 '15 at 21:27
• Thanks for the cstheory suggestion, I didn't think of that. The reason it's not obviously in PSPACE is that in addition to the state of the cards, you also need to model the state of knowledge of what the other players know, and there's no obvious bound on that. Note the "undecidable" entry in the table I posted. – Dylan Thurston Nov 2 '15 at 12:43
• Position = own cards in hand + complete history of what happened in the game so far. Then you can make the brute force search over the possibilities of what's in the hands of the others, imo. – domotorp Nov 3 '15 at 1:01
• dmotorp, you're omitting the search over all possible systems of conventions. – Dylan Thurston Nov 3 '15 at 19:18

At https://sites.google.com/site/rmgpgrwc/research-papers/Hanabi_final.pdf?attredirects=0 there's an article with an idea for how to clue efficiently: map each possible clue you can give onto $\{1, \ldots, n\}$. Then, for each player, determine based on common knowledge in the current game state (including past clues, plays and discards) which card is most likely to be playable, and which suit/rank combination that card can possibly be; divide the set of possibilities into $n$ subsets (in some publicly known fashion), and assign to each player $p$ the number $k_p$ of the subset that contains the actual suit/rank combination. Give the hint which encodes as the sum of all the $k_p$ values, modulo $n$. Each player $p$ can then look at all other hands and compute $k_p = clue - \sum_{i \ne p} k_i\ (mod\ n)$.
It's not the most interesting hash function ever, but I think it qualifies as one. An expansion on this idea: once enough cards have been played, the number of non-dead rank/suit combinations is at most $\sqrt n - 1$, so you can clue each player two cards independently. Or, before this point, if the set of possibilities for a particular card is very narrow, you can divide the possibility set into $m$ singleton subsets and say one out of $n/m$ things about the next likely card .
Note that with at least 4 players and 0-card clues allowed, $n \ge 30$ and there are at most 30 different rank/suit combinations across the standard variants, so this allows the perfect identification of one card (perhaps with a tiny bit of side information in the 5-player case or 6 clue colors).