Document Open Access Logo

2048 Without New Tiles Is Still Hard

Authors Ahmed Abdelkader, Aditya Acharya, Philip Dasler



PDF
Thumbnail PDF

File

LIPIcs.FUN.2016.1.pdf
  • Filesize: 2.67 MB
  • 14 pages

Document Identifiers

Author Details

Ahmed Abdelkader
Aditya Acharya
Philip Dasler

Cite AsGet 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.
Keywords
  • Complexity of Games
  • 2048

Metrics

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

References

  1. Ahmed Abdelkader. 2048 gadgets. URL: http://cs.umd.edu/~akader/projects/2048/index.html.
  2. Ahmed Abdelkader, Aditya Acharya, and Philip Dasler. 2048 is NP-Complete. CGYRF, 2015. Google Scholar
  3. 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.
  4. Christopher Chen. 2048 is in NP. URL: http://blog.openendings.net/2014/03/2048-is-in-np.html.
  5. 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.
  6. 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. Google Scholar
  7. Stefan Langerman and Yushi Uno. Threes!, Fives, 1024!, and 2048 are Hard. CoRR, abs/1505.04274, 2015. URL: http://arxiv.org/abs/1505.04274.
  8. 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. Google Scholar
  9. Rahul Mehta. 2048 is (PSPACE) Hard, but Sometimes Easy. CoRR, abs/1408.6315, 2014. URL: http://arxiv.org/abs/1408.6315.
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