LIPIcs.FUN.2016.22.pdf
- Filesize: 0.9 MB
- 14 pages
Document
Threes!, Fives, 1024!, and 2048 are Hard
Authors
-
Part of:
Volume:
8th International Conference on Fun with Algorithms (FUN 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-06-02
Cite As Get 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.
Subject Classification
Keywords
- algorithmic combinatorial game theory
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- 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,
-
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.
-
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.
- 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.
- Gabriele Cirulli. 2048. http://gabrielecirulli.github.io/2048/, March 2014.
- 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.
-
Rodney G. Downey and Michael R. Fellows. Parameterized complexity. Springer Heidelberg, 1999.
- Rahul Mehta. 2048 is (PSPACE) hard, but sometimes easy. CoRR, abs/1408.6315, 2014. URL: http://arxiv.org/abs/1408.6315,
- Phenomist. 2048 variants. http://phenomist.wordpress.com/2048-variants/, 2014.
- 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.
- A.J. Richardson. Evil 2048. http://aj-r.github.io/Evil-2048/, March 2014.
- Saming. 2048. http://saming.fr/p/2048/, March 2014.
- Asher Vollmer, Greg Wohlwend, and Jimmy Hinson. Threes! http://asherv.com/threes/, January 2014.