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-2Engels
Pagina's (van-tot)43-55
Aantal pagina's13
TijdschriftTheoretical Computer Science
Volume675
DOI's
StatusGepubliceerd - 2 mei 2017
Extern gepubliceerdJa

Vingerafdruk Duik in de onderzoeksthema's van 'Hanabi is NP-hard, even for cheaters who look at their cards'. Samen vormen ze een unieke vingerafdruk.

Citeer dit