LIPIcs.FUN.2016.1.pdf
- Filesize: 2.67 MB
- 14 pages
Document
2048 Without New Tiles Is Still 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
Ahmed Abdelkader, Aditya Acharya, and Philip Dasler. 2048 Without New Tiles Is Still Hard. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FUN.2016.1
Abstract
We study the computational complexity of a variant of the popular 2048 game in which no new tiles are generated after each move. As usual, instances are defined on rectangular boards of arbitrary size. We consider the natural decision problems of achieving a given constant tile value, score or number of moves. We also consider approximating the maximum achievable value for these three objectives. We prove all these problems are NP-hard by a reduction from 3SAT. Furthermore, we consider potential extensions of these results to a similar variant of the Threes! game. To this end, we report on a peculiar motion pattern, that is not possible in 2048, which we found much harder to control by similar board designs.
Subject Classification
Keywords
- Complexity of Games
- 2048
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Ahmed Abdelkader. 2048 gadgets. URL: http://cs.umd.edu/~akader/projects/2048/index.html.
-
Ahmed Abdelkader, Aditya Acharya, and Philip Dasler. 2048 is NP-Complete. CGYRF, 2015.
- 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.
- Christopher Chen. 2048 is in NP. URL: http://blog.openendings.net/2014/03/2048-is-in-np.html.
- Erik D. Demaine, Martin L. Demaine, and Joseph O'Rourke. PushPush is NP-hard in 2D. CoRR, cs.CG/0001019, 2000. URL: http://arxiv.org/abs/cs.CG/0001019.
-
Luciano Guala, Stefano Leucci, and Emanuele Natale. Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard. In 2014 IEEE Conference on Computational Intelligence and Games, pages 1-8. IEEE, 2014.
- Stefan Langerman and Yushi Uno. Threes!, Fives, 1024!, and 2048 are Hard. CoRR, abs/1505.04274, 2015. URL: http://arxiv.org/abs/1505.04274.
-
Stefan Langerman and Yushi Uno. Threes!, Fives, 1024!, and 2048 are Hard. In 8th International Conference on Fun with Algorithms (FUN 2016), volume 49 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1-22:14, 2016.
- Rahul Mehta. 2048 is (PSPACE) Hard, but Sometimes Easy. CoRR, abs/1408.6315, 2014. URL: http://arxiv.org/abs/1408.6315.