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

DOI10.1016/J.TCS.2017.02.024MaRDI QIDQ528493zbMATH OpenOpenAlexFDO

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

Publication date 12 May 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.01911

zbMATH Keywords

algorithmic combinatorial game theorycomputational complexitysolitaire gamessorting

Mathematics Subject Classification ID

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

Abstract: 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.

Recommendations

• Hanabi is NP-complete, 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

Cites work

• A Combinatorial Problem Which Is Complete in Polynomial Space
• A threshold of ln n for approximating set cover
• Algorithmic Game Theory
• Computing a perfect strategy for nxn chess requires time exponential in n
• Games, puzzles, and computation
• GO Is Polynomial-Space Hard
• How to make the perfect fireworks display: two strategies for Hanabi
• scientific article; zbMATH DE number 1834637 (Why is no real title available?)
• Tetris is Hard, Even to Approximate
• The computational complexity of the game of Set and its theoretical applications
• UNO is hard, even for a single player
• Winning ways for your mathematical plays. Vol. 1.

Cited in

(7)

• Backgammon is hard
• The Hanabi challenge: a new frontier for AI research
• How to make the perfect fireworks display: two strategies for Hanabi
• UNO is hard, even for a single player
• Hanabi is NP-complete, even for cheaters who look at their cards
• Characterizing the decidability of finite state automata team games with communication
• NP-completeness of Hanabi game with minimal parameters

This page was built for publication: Hanabi is NP-hard, 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 Q528493)