Hanabi is NP-hard, Even for Cheaters who Look at Their Cards

A combinatorial problem which is complete in polynomial space

Shimon Even and Robert E. Tarjan · 1976

Earlier work this paper cites.

Go is polynomial-space hard

David Lichtenstein and Michael Sipser · 1980

Earlier work this paper cites.

Computing a perfect strategy for n × n n\times n chess requires time exponential in n n

Aviezri S. Fraenkel and David Lichtenstein · 1981

Earlier work this paper cites.

A threshold of ln ⁡ n \ln n for approximating set cover

Uriel Feige · 1998

Earlier work this paper cites.

Winning Ways for Your Mathematical Plays (2/e)

Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy · 2001

Earlier work this paper cites.

Tetris is hard, even to approximate

Erik D. Demaine, Susan Hohenberger, and David Liben-Nowell · 2003

Earlier work this paper cites.

Complexity and completeness of finding another solution and its application to puzzles

Takayuki Yato and Takahiro Seta · 2003

Earlier work this paper cites.

Algorithmic Game Theory

Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V Vazirani · 2007

Earlier work this paper cites.

Playing games with algorithms: Algorithmic combinatorial game theory

Erik D. Demaine · 2008

Cited alongside, same era.

Games, Puzzles, and Computation

Robert Hearn and Erik D. Demaine · 2009

Cited alongside, same era.

NP-completeness of Pandemic

Kenichiro Nakai and Yasuhiko Takenaga · 2012

Cited alongside, same era.

On the complexity of trick-taking card games

Édouard Bonnet, Florian Jamain, and Abdallah Saffidine · 2013

Cited alongside, same era.

UNO is hard, even for a single player

Erik D. Demaine, Martin L. Demaine, Nicholas J. A. Harvey, Ryuhei Uehara, Takeaki Uno, and Yushi Uno · 2014

Cited alongside, same era.

Bejeweled, candy crush and other match-three games are (NP-)hard

Luciano Gualà, Stefano Leucci, and Emanuele Natale · 2014

Cited alongside, same era.

How to make the perfect fireworks display: Two strategies for Hanabi

Christopher Cox, Jessica De Silva, Philip Deorsey, Franklin H. J. Kenter, Troy Retter, and Josh Tobin · 2015

Later among the works it cites.

Solving Hanabi: Estimating hands by opponent’s actions in cooperative game with incomplete information

Hirotaka Osawa · 2015

Later among the works it cites.

https://boardgamegeek.com/boardgame/98778/hanabi

BoardGameGeek · 2016

Closest in time.

The complexity of playing durak

Édouard Bonnet · 2016

Closest in time.

Magic: The gathering is Turing complete

Alex Churchill · 2016

Closest in time.

http://www.spieldesjahres.de/en/hanabi

Spiel des Jahres award · 2016

Closest in time.