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

DOI10.1016/J.TCS.2018.03.018zbMATH Open1402.68101arXiv1505.04274OpenAlexW2790674930MaRDI QIDQ1623263FDOQ1623263

Authors: Stefan Langerman, Yushi Uno 

Publication date: 23 November 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

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 x 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.

Full work available at URL: https://arxiv.org/abs/1505.04274

Recommendations

• Threes!, Fives, 1024!, and 2048 are hard
• 2048 without new tiles is still hard
• Trainyard is NP-hard
• Trainyard is NP-hard
• TETRIS IS HARD, EVEN TO APPROXIMATE

zbMATH Keywords

algorithmic combinatorial game theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Cites Work

• Playing games with algorithms: algorithmic combinatorial game theory
• Title not available (Why is that?)
• TETRIS IS HARD, EVEN TO APPROXIMATE
• 2048 without new tiles is still hard
• Threes!, Fives, 1024!, and 2048 are hard

Cited In (7)

• Systematic selection of \(N\)-tuple networks for 2048
• Trainyard is NP-hard
• Threes!, Fives, 1024!, and 2048 are hard
• 2048 without new tiles is still hard
• HOW DIFFICULT IS IT TO INVENT A NONTRIVIAL GAME?
• Trainyard is NP-hard
• Making change in 2048

This page was built for publication: Threes!, Fives, 1024!, and 2048 are hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1623263)