[anon4]

What I meant is that no matter how the computer plays, you can always serve it a sequence of 2s and 4s that will never reach 2048. Easiest is to make sure there's exactly one 2 on the board, then spawn 4s in the corners, always picking the corner farthest away from the other tiles. From time to time spawn a 2 if you can guarantee it won't align with the other 2 in a couple of moves. Near the endgame it is trivial to have three 2 tiles which you keep always separate with careful placement of 4s. At that point the game becomes literally impossible to win.

Edit: Try to play it the other way, too. Try dropping tiles in the best most convenient pattern for the AI. Notice the amount of clutter that inevitably results when reaching higher numbers. An interesting question would be, if you control both the tile placement and movement, what is the highest number you can reach? With the constraint you can place only 2s.

[j2kun]

When you say things like, "you need a careful placement of 4s" it makes me think, "well that's not a proof."

So let me be formal. I'm posing the following decision problem: given a target score n and some initial board configuration of size (k * k), can one player force a score of at least n? I conjecture this problem is PSPACE-hard.

Your claim is that if n >= 2048 and k = 4 then the answer is always no (though I don't buy your justification). My question is more general, and it's clear that there is not a constant answer (e.g. if n is 2 the answer is always yes, but for some sufficiently large n the answer is always no)