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

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

6 Citaten (Scopus)
186 Downloads (Pure)

Samenvatting

This paper studies a cooperative card game called Hanabi from an algorithmic combinatorial game theory viewpoint. The aim of the game is to play cards from 1 to n in increasing order (this has to be done independently in c different colors). Cards are drawn from a deck one by one. Drawn cards are either immediately played, discarded or stored for future use (overall each player can store up to h cards). The main feature of the game is that players know the cards their partners hold (but not theirs. This information must be shared through hints). We introduce a simplified mathematical model of a single-player version of the game, and show several complexity results: the game is intractable in a general setting even if we forego with the hidden information aspect of the game. On the positive side, the game can be solved in linear time for some interesting restricted cases (i.e., for small values of h and c).

Originele taal-2Engels
Titel8th International Conference on Fun with Algorithms, FUN 2016
RedacteurenE.D. Demaine, F. Grandoni
Plaats van productieDagstuhl
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's17
Volume49
ISBN van elektronische versie9783959770057
DOI's
StatusGepubliceerd - 1 jun. 2016
Extern gepubliceerdJa
Evenement8th International Conference on Fun with Algorithms (FUN 2016) - La Maddalena, Italië
Duur: 8 jun. 201610 jun. 2016
Congresnummer: 8

Publicatie series

NaamLeibniz International Proceedings in Informatics (LIPIcs)
Volume49
ISSN van geprinte versie1868-8969

Congres

Congres8th International Conference on Fun with Algorithms (FUN 2016)
Verkorte titelFUN 2016
Land/RegioItalië
StadLa Maddalena
Periode8/06/1610/06/16

Vingerafdruk

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

Citeer dit