Threes!, Fives, 1024!, and 2048 are Hard

Authors Stefan Langerman, Yushi Uno



PDF
Thumbnail PDF

File

LIPIcs.FUN.2016.22.pdf
  • Filesize: 0.9 MB
  • 14 pages

Document Identifiers

Author Details

Stefan Langerman
Yushi Uno

Cite AsGet BibTex

Stefan Langerman and Yushi Uno. Threes!, Fives, 1024!, and 2048 are Hard. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FUN.2016.22

Abstract

We analyze the computational complexity of the popular computer games Threes!, 1024!, 2048 and many of their variants. For most known versions expanded to an m*n board, we show that it is NP-hard to decide whether a given starting position can be played to reach a specific (constant) tile value.
Keywords
  • algorithmic combinatorial game theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Ahmed Abdelkader, Aditya Acharya, and Philip Dasler. On the complexity of slide-and-merge games. CoRR, abs/1501.03837, 2015. URL: http://arxiv.org/abs/1501.03837,
  2. Ahmed Abdelkader, Aditya Acharya, and Philip Dasler. 2048 without new tiles is still hard. Proceedings of the 8th International Conference on Fun with Algorithms, LIPICS volume 49, 2016. Google Scholar
  3. Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom, Walter A. Kosters, and David Liben-Nowell. Tetris is hard, even to approximate. International Journal of Computational Geometry and Applications, 14(1-2):41-68, 2004. Google Scholar
  4. Christopher Chen. 2048 is in NP. http://blog.openendings.net/2014/03/2048-is-in- http://blog.openendings.net/2014/03/2048-is-in-np.html, March 2014.
  5. Gabriele Cirulli. 2048. http://gabrielecirulli.github.io/2048/, March 2014.
  6. Erik D. Demaine and Robert A. Hearn. Playing games with algorithms: Algorithmic combinatorial game theory. In Michael H. Albert and Richard J. Nowakowski, editors, Games of No Chance 3, volume 56 of Mathematical Sciences Research Institute Publications, pages 3-56. Cambridge University Press, 2009. URL: http://arxiv.org/abs/cs.CC/0106019.
  7. Rodney G. Downey and Michael R. Fellows. Parameterized complexity. Springer Heidelberg, 1999. Google Scholar
  8. Rahul Mehta. 2048 is (PSPACE) hard, but sometimes easy. CoRR, abs/1408.6315, 2014. URL: http://arxiv.org/abs/1408.6315,
  9. Phenomist. 2048 variants. http://phenomist.wordpress.com/2048-variants/, 2014.
  10. QuadmasterXLII. Solve a deterministic version of 2048 using the fewest bytes. http://codegolf.stackexchange.com/questions/24885/solve-a-deterministic- http://codegolf.stackexchange.com/questions/24885/solve-a-deterministic-version-of-2048-using-the-fewest-bytes, 2014.
  11. A.J. Richardson. Evil 2048. http://aj-r.github.io/Evil-2048/, March 2014.
  12. Saming. 2048. http://saming.fr/p/2048/, March 2014.
  13. Asher Vollmer, Greg Wohlwend, and Jimmy Hinson. Threes! http://asherv.com/threes/, January 2014.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail