In my last 2048 post, I found that it takes at least 938.8 moves on average to win a game of 2048. The main simplification that enabled that calculation was to ignore the structure of the board — essentially to throw the tiles into a bag instead of placing them on a board. With the ‘bag’ simplification, we were able to model the game as a Markov chain with only 3486 distinct states.
In this post, we’ll make a first cut at counting the number of states without the bag simplification. That is, in this post a state captures the complete configuration of the board by specifying which tile, if any, is in each of the board’s cells. We would therefore expect there to be a lot more states of this kind, now that the positions of the tiles (and cells without tiles) are included, and we will see that this is indeed the case.
To do so, we will use some (simple) techniques from enumerative combinatorics to exclude some states that we can write down but which can’t actually occur in the game, such as the one above. The results will also apply to 2048-like games played on different boards (not just 4×4) and up to different tiles (not just the 2048 tile). We’ll see that such games on smaller boards and/or to smaller tiles have far fewer states than the full 4×4 game to 2048, and that the techniques used here are relatively much more effective at reducing the estimated number of states when the board size is small. As a bonus, we’ll also see that the 4×4 board is the smallest square board on which it is possible to reach the 2048 tile.
The (research quality) code behind this article is open source, in case you would like to see the implementation or code for the plots.