Expected halting time for "The 2^n Game" (aka 2048) -- with random moves

Question

Recently I encountered an online flash game that features an m-by-m grid and input from the directional pad (up, down, left, right). At any point in the game, the grid contains numbers ('blocks') from the set $\{2^i\},1\le i\lt n$. So at each step in the game, every cell on the grid is either empty or contains such a block.

The game proceeds in discrete steps, with the player choosing a direction to move the blocks (i.e., non-empty cells) on the grid; all blocks move in the direction specified by the player, if they can - but for instance, if an entire row is filled with blocks, a left or right move by the player will not move any blocks, assuming none of the blocks are eligible to be 'merged' into one another, as we explain below.

Blocks can merge together if they have the same number, and naturally the value of the resulting block is twice that of either of the input blocks. That is, the blocks are summed. If two blocks are in fact so eligible to be merged, they will merge if they are adjacent and if the player's specified direction moves one block towards the other; so we can say that one block ('source block') is 'merged into' another ('target block'), with the former moving in the direction specified by the player, and the latter remaining in place. Then, all blocks 'behind' the source block also move in the specified direction, and of course the blocks 'starting with' the target block stay in place. This is all very intuitive from the player's standpoint, but perhaps worth spelling out.

The player wins if two blocks are merged into a block with value $2^n$, but loses if the grid fills and there are no merges to be made. The source of randomness in the game is the random appearance of blocks with value $2$ or $4$; these blocks can also appear in a position already held by a $2$ or $4$ block, respectively, in which case the new block is merged with the old block. But note that this possible merging can only take place AFTER the blocks have moved, as specified by the player's direction choice. In any case, the new block(s)' position(s) are chosen uniformly from the set of empty cells union the set of mergeable blocks for that new block (i.e., set of $2$ or $4$ blocks, respectively).

So the question is, given $m$ and $n$, random moves by the player, and some suitable small set of starting blocks, what is the expected time until the game halts, with the player either winning or losing? Beyond an elementary level, I cannot imagine how to proceed with actually solving the problem, so I will stop here (I'm not a mathematician). But I hope the explanation has been clear enough, although I'm not 100% certain that the problem is actually solvable as stated. (For example, is there a well-defined notion of 'expected' here?)

Anyway, here is an example of the game for $m = 4$ and $n = 11$, which will probably make the problem much clearer compared with the above explanation, but I thought I'd provide the explanation anyway for completeness' sake.

http://gabrielecirulli.github.io/2048/

And another, for $m=8$ and $n=53$, which features a mechanism for automatically playing random moves:

http://www.csie.ntu.edu.tw/~b01902112/9007199254740992/

NOTES

For the sake of consistency among the answers, suppose the grid is empty to start with. Of course anyone is welcome to change this / request for it to be changed if there is a better choice of starting blocks.

Following Dpiz's comment below, I figured we might as well consider the probabilities for uniform insertion of $2$ and $4$ blocks (as discussed above) to be equal, that is, either number is equally likely to be chosen to be inserted in an eligible cell. But then note that, at a given point in the game, the set of cells eligible for random insertion by $2$ may be of a different size than that of $4$; in particular, aside from the empty cells which are eligible for both numbers, a $2$ can be randomly inserted where a $2$ exists (and so immediately merged into a $4$), whereas a $4$ can be inserted where a $4$ exists, being likewise merged immediately into an $8$. So I'm not sure whether the random insertion algorithm should choose destination cell first, and then choose the number to be placed there (in which case the probabilities $2$ and $4$ being randomly inserted anywhere will depend on the state of the game); or whether a number $a\in\{2,4\}$ is chosen first, and then its destination is chosen uniformly among the cells eligible for $a$. I hope this was clear. In any case, I'm not sure what the actual game does - it seems like maybe $2$ will appear slightly more often than $4$? Shall we denote the prob that $2$ is selected to be $\rho_2$, and likewise $\rho_4$ for $4$?

Additionally, I think it is safe to further constrain the problem to $n\ge 3$, so that we don't have for example a $4$ being randomly inserted and ending the game.

Answer 1

I don't know what the strategy should be, but for large enough $n$, you lose with probability $1$. At each step, the sum of the blocks increases by $2$ or $4$, so at least one of $4\times 2^{m^2}-4$ and $4\times2^{m^2}-2$ is hit. These numbers have at least $m^2$ $1$s in their binary expansions. If you write either as a sum of powers of $2$, you need at least $m^2$ terms, and if you only use $m^2$ then they must all be different. This means the board would be filled, and no merges would be possible.