16
$\begingroup$

Games got me on math. I always want to play best.

I don't know how to answer my question. My question is : How to show that the game 2048 is (always) solvable>? Is there any method other than brute force?

There is a sudko grid and you use arrow keys to move even number, starting near 2, around so that combine to value 2048. Play, it is very fun.

$\endgroup$
  • 1
    $\begingroup$ What is game 2048? $\endgroup$ – Stephen Montgomery-Smith Mar 21 '14 at 3:33
  • 2
    $\begingroup$ gabrielecirulli.github.io/2048 $\endgroup$ – Adriano Mar 21 '14 at 3:40
  • 2
    $\begingroup$ jennypeng.me/2048 this is always solvable. I assure you. $\endgroup$ – Guy Mar 21 '14 at 3:55
  • 4
    $\begingroup$ Problem can be posed more generally: When the game is won at small values (like 16) it is always winnable, but at some point must become unwinnable, as some numbers are too large to be made on the board. Given a board of dimensions $n \times m$, what is the smallest target value at which the game cannot be won? $\endgroup$ – Jonny Lomond Mar 21 '14 at 22:20
  • 4
    $\begingroup$ According to Zermelo's theorem, because 2048 is a finite game with perfect information, a winning strategy exists for either the computer or the player (where the computer is said to "win" if the player does not win). Zermelo's theorem is constructive, and gives a way to determining who has the winning strategy, but it would be computationally intensive. There are very few general tools that are known for these kinds of problems. If you want to see what the game looks like when the computer places tiles intelligently, see: sztupy.github.io/2048-Hard $\endgroup$ – Marcel Besixdouze Apr 6 '14 at 6:27
8
$\begingroup$

On the contrary, I think the game is not solvable. You can get convinced of it by taking a look here: http://sztupy.github.io/2048-Hard/ It is the same game, except that randomness is replaced by the worst possible choice for new tiles to appear. It seems obvious after a little practice that this version is impossible, and it just corresponds to being unlucky in the original game. A rigorous proof that this version is impossible will likely be very tedious though...

$\endgroup$
3
$\begingroup$

It was claimed that the 2048-game is NP-hard in this arXiv preprint: http://arxiv.org/pdf/1501.03837v1.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.