Is the game Hanabi NEXPTIME-complete?

Question

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?

Answer 1

There's an article at https://arxiv.org/pdf/1603.01911.pdf showing that a cheating solitaire variant is NP-complete. It's not very explicit about the membership of NP, but here's an argument that works: a witness is a sequence of moves; whether a sequence wins can be computed in linear time in the deck size (it's O(1) to make each update to the game state; it's linear time in the number of colors to check that the maxnum in each color has beed player, and there are no more colors than cards).

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

Since the information channel is very narrow and the set of possibilities is large, I'm not convinced that using a more complicated hash function (say, poly-31 or some very weak cryptographic hash) is a big gain, but every little win is still a win.