[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)