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

DOI10.4230/LIPICS.FUN.2016.4zbMATH Open1369.68228MaRDI QIDQ5282800FDOQ5282800

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

Publication date: 17 July 2017

Recommendations

• Hanabi is NP-hard, even for cheaters who look at their cards
• How to make the perfect fireworks display: two strategies for Hanabi
• UNO is hard, even for a single player
• On the computational complexity of bridgecard
• The complexity of solitaire

zbMATH Keywords

sortingalgorithmic combinatorial game theoryHanabi

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Cited In (9)

• The Hanabi challenge: a new frontier for AI research
• Rikudo is NP-complete
• \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\)
• How to make the perfect fireworks display: two strategies for Hanabi
• The computational complexity of Evil Hangman
• Magic: The Gathering is Turing complete
• On the computational complexity of bridgecard
• Hanabi is NP-hard, even for cheaters who look at their cards
• UNO is hard, even for a single player

This page was built for publication: Hanabi is NP-complete, even for cheaters who look at their cards

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5282800)