Hanabi is NP-hard, even for cheaters who look at their cards

Jean François Baffier, Man Kwun Chiu, Yago Diez, Matias Korman, Valia Mitsou, André van Renssen, Marcel Roeloffzen, Yushi Uno

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

4 Citaten (Scopus)

Samenvatting

In this paper we study a cooperative card game called Hanabi from the viewpoint of algorithmic combinatorial game theory. In Hanabi, each card has one among c colors and a number between 1 and n. The aim is to make, for each color, a pile of cards of that color with all increasing numbers from 1 to n. At each time during the game, each player holds h cards in hand. Cards are drawn sequentially from a deck and the players should decide whether to play, discard or store them for future use. One of the features of the game is that the players can see their partners’ cards but not their own and information must be shared through hints. We introduce a single-player, perfect-information model and show that the game is intractable even for this simplified version where we forego both the hidden information and the multiplayer aspect of the game, even when the player can only hold two cards in her hand. On the positive side, we show that the decision version of the problem—to decide whether or not numbers from 1 through n can be played for every color—can be solved in (almost) linear time for some restricted cases.

Originele taal-2 Engels 43-55 13 Theoretical Computer Science 675 https://doi.org/10.1016/j.tcs.2017.02.024 Gepubliceerd - 2 mei 2017 Ja