TY - JOUR
T1 - Hanabi is NP-hard, even for cheaters who look at their cards
AU - Baffier, Jean François
AU - Chiu, Man Kwun
AU - Diez, Yago
AU - Korman, Matias
AU - Mitsou, Valia
AU - van Renssen, André
AU - Roeloffzen, Marcel
AU - Uno, Yushi
PY - 2017/5/2
Y1 - 2017/5/2
N2 - 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.
AB - 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.
KW - Algorithmic combinatorial game theory
KW - Computational complexity
KW - Solitaire games
KW - Sorting
UR - http://www.scopus.com/inward/record.url?scp=85017570809&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2017.02.024
DO - 10.1016/j.tcs.2017.02.024
M3 - Article
AN - SCOPUS:85017570809
SN - 0304-3975
VL - 675
SP - 43
EP - 55
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -