Assuming you're not trolling, it's because this AI is using a heuristic approach rather than a guaranteed correct approach.
Heuristics rely on simplified rules which don't accurately model the system on which they're acting 100% of the time. Good heuristics can come close to 100%, however.
But why? Glad you asked!
A 100% correct solution would be to write an algorithm which enumerates all of the possible moves as a decision tree, and walks the decision tree to find the correct answer.
However, given that there are four possible moves the user can make (up, down, left, right) and an upper bound of 32 possible moves the computer can make (computer places "2" or "4" anywhere in a 4x4 grid), each level of the tree could require up to 128 times the number of computations that it took to compute the previous level of the tree.
For example, calculating the first turn is on the order of 128 calculations. Calculating the second move is on the order of 128^2 calculations. Calculating the third is 128^3, an so on. By order of magnitude, how many moves do you think it takes on average to get to 2048? 10^3? Even if we were being really optimistic, maybe it's 10^2. In that case, you'd have to perform somewhere around 128^100 computations in order to solve the game perfectly every time.
Actually, to make a 2048 you need to make two 1024s. It's unlikely that you'll make two 1024s at the same time. Similarly for the lower tiles. As a sort of upper bound you expect the game to be over in about 1024 moves and it's likely to not be much less than that. I think a more realistic number is somewhere in the 500s
I'm not sure I follow, but I think we're saying the same thing.
It's been too long since I've taken any hardcore discrete math for me to reliably reason about the bounds on the number of moves required to win. All I can do is make estimates based on simplifications.
How I arrived at my estimates for the order of magnitude of the minimum number of moves required to win:
At most, you can merge 4 tiles in one move. Assuming you were doing 4 tiles every move, and the game just didn't produce twos, it'd take just 128 moves. Order of magnitude: 10^2.
Assuming exactly one merge per move, and that the game only produces twos, it'd take 1024 moves. Order of magnitude: 10^3.
Heuristics rely on simplified rules which don't accurately model the system on which they're acting 100% of the time. Good heuristics can come close to 100%, however.
But why? Glad you asked!
A 100% correct solution would be to write an algorithm which enumerates all of the possible moves as a decision tree, and walks the decision tree to find the correct answer.
However, given that there are four possible moves the user can make (up, down, left, right) and an upper bound of 32 possible moves the computer can make (computer places "2" or "4" anywhere in a 4x4 grid), each level of the tree could require up to 128 times the number of computations that it took to compute the previous level of the tree.
For example, calculating the first turn is on the order of 128 calculations. Calculating the second move is on the order of 128^2 calculations. Calculating the third is 128^3, an so on. By order of magnitude, how many moves do you think it takes on average to get to 2048? 10^3? Even if we were being really optimistic, maybe it's 10^2. In that case, you'd have to perform somewhere around 128^100 computations in order to solve the game perfectly every time.
Incidentally, python tells me that'd be
calculations.Or for fun, this is 128^1000:
So throwing a few assumptions in there isn't a bad idea...