As a computer scientist I can't help but now ask: what is the complexity of this problem? If it's in P then this game is not very interesting (in that I can't hope to fool the AI).
Stop me if I'm wrong, but it seems misleading to ask whether or not the problem is in P. It seems to me that it is better to ask more generally whether the problem is tractable. There are a lot of games that are solvable in exponential time (not in P) that are still tractable because the branching factor is low enough that simple methods like minimax searches work well.
Take chess as an example. It's an EXP-TIME complete game with a branching factor of 35, and AI techniques win pretty much all of the time. In this case you're looking at a much simpler game (if you treat it as an expectiminimax problem, you alternate between turns with a branching factor of less than or equal to 4 and ones with a branching factor of less than or equal to 32). The game is much less complicated than chess. The game tree is really small, meaning that it should be tractable to most AI techniques.
Even though it is reasonable to 'solve' the problem, there are board setups that are unwinnable. Since the player has a lot more power over the game in placing tiles than the agent does in moving them, it is easier for the player to force the game to one of the unwinnable states than it is for the agent to prevent these things. Even if the agent is acting optimally, the player should still be able to win.
What's really misleading is when people try to push the question aside by saying "AI techniques should work." It's dodging the question. What I ask is whether there is an efficient algorithm to determine if one player can force a win, given a position on an arbitrary size board. Forget whether the game is imbalanced. It's just a mathematical question.
You say this game is less complicated than chess, but what measure of complexity are you talking about? Might it be computational complexity? Computer scientists of all people know that simple rules can provide arbitrary complexity.
That's not a problem, because there are impossible games. Your task is just to form an impossible situation.
This game is MUCH easier than the original, at least for me. I never managed to beat the original, but on the other hand I've yet to be beaten by the AI.
No, because the problem is deciding whether, for all possible moves you make, there is a move that the opponent can make, such that for all possible moves you make, there is a move the opponent can make, ... that will force a win or lose for one player.
This makes it smell like a PSPACE-hard problem (if you make the board size arbitrary).
[EDIT] Now I see what you mean, that you could start in a position where you can guarantee a win and so being in P doesn't matter (the computer would just be able to tell quickly that it cannot win if you play optimally). But this also isn't satisfying because it seems unlikely that a random starting position would put you in such a state (since it's so early in the game!).
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.
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)
... Much higher than P pretty obviously. 16 possible drop points and 4 possible moves each turn maximum, let's say only half of each is available on average. That gives ((2)(8))^N for N amount of turns.
Take chess as an example. It's an EXP-TIME complete game with a branching factor of 35, and AI techniques win pretty much all of the time. In this case you're looking at a much simpler game (if you treat it as an expectiminimax problem, you alternate between turns with a branching factor of less than or equal to 4 and ones with a branching factor of less than or equal to 32). The game is much less complicated than chess. The game tree is really small, meaning that it should be tractable to most AI techniques.
Even though it is reasonable to 'solve' the problem, there are board setups that are unwinnable. Since the player has a lot more power over the game in placing tiles than the agent does in moving them, it is easier for the player to force the game to one of the unwinnable states than it is for the agent to prevent these things. Even if the agent is acting optimally, the player should still be able to win.