My intuition and experience tells me that, with optimal play, you can almost always — but not always — win 2048.
2048 is a wonderful puzzle game that I’ve spent far too much time playing (although probably not as much as what it’s based on, Threes.)
I’ve never done real proofs in my life, but I know that to prove that you can always win, I need to prove that a malicious and omnipotent computer cannot defeat you.
I’ll assume you know how the game works. The rules that are most likely to end your game are:
- tiles spawn randomly in empty spots, with 90% odds it’s a 2 tile, 10% odds it’s a 4 tile.
- for a move to be legal, some tiles must slide.
The point at when you’re most likely to lose is right before the final cascade of combining of the final tiles, i.e. when your board is most congested with non-matching tiles. On the way to making 2048, that means something like this:
This sequential snaking of ascending tiles is near optimal play (just from personal experience). Notice there are only eight tiles, not counting the spawn-able 2s and 4s, which gives you a rather lot of wiggle room to form the last 8 and win. Let’s see if I can throttle a nearly full board by shoving 2s and 4s in inconvenient places and corner you into making bad moves.
Yay big flow charts!
What’s happening: I’m spawning 2s and 4s (green tiles) in empty spaces and you’re responding with slides (blue arrows).
I know it’s grossly incomplete, but you’ll find the vast majority of spawns will let you win trivially. I drew out some harder cases, which turn out to be where you spawn mismatching tiles on the side, thereby constricting possible moves.
If you’ve played enough 2048, you’ll know that your worst nightmare is the “lock,” a 4×3 solid block, which requires you to slide opposite of your big tiles, thus compromising your organization. From there, it usually takes some dumb luck to cascade back into few enough tiles to reorganize.
Things get really messy, but let’s take a look.
Indeed, it’s not easy (it’s basically just spawning lots of 4s in the worst places possible), but it seems like astronomically bad luck can guarantee a loss, no matter how well you play. Seriously, it’s so unlikely. Every move, a 4 only has ~ 0.1 * 1/4 of falling in the wrong place, so for it to happen just 10 times in a row is p = .025^10 = 0.0000000000000009%. *
Admittedly, I just checked the optimal setup before the endgame. Of course, any time you mess up before that it gets even worse by taking up one of the slots of your wiggle room. To illustrate:
Left case: Even though the tiles of the 2nd row are out of order, as soon as you create a 8 above and drop it down, things still combine smoothly.
Right case: because you have the largest tile (64) somewhere in the middle, that row has a bit of “dead space”. That is, the 32 and 16 contribute nothing to winning, and you have to convert that 8 into a 64 if you want to use the bottom row cascade.
You can imagine that rows with dead space can stack on top of each other:
Ouch, that was no fun. This is why getting your big tiles into the corners is so important; otherwise, you create dead space and congestion.
Of course, I know that “messing up” is not the fabled optimal play, but surely there’s a way to force sub-optimal setting up with bad spawns. The point is, anything less than the optimal intermediate state shown above will have less “wiggle room” and be much more likely to have forced losses.
In conclusion, I reason that playing 2048 optimally usually lets you win, but with vanishingly small probability, extraordinarily bad luck can force you to lose. (p < 1E-700 probably, iono)
* It’s nearly impossible to calculate actual probabilities about 2048 because it’s game tree is BIG. There are 2048 / (2*0.9+4*0.1) + 9 = 940 turns to make a choice out of ~ 4 options each (slide up/right/left/down), so roughly 4^940 = A LOT of game states. I could calculate better expected values or build a simulator to brute force endgame, but I don’t have any more free time to pour into this project. (#medschool)
originally posted on Quora here.