How to work out the complexity of the game 2048?

Question

I've been reading A question about the game 2048 which discusses strategies for creating an algorithm that will perform well playing the game.

The accepted answer mentions that:

the game is a discrete state space, perfect information, turn-based game like chess

which got me thinking about its complexity. For deterministic games like chess, it's possible (in theory) to work out all the possible moves that lead to a win state and work backward, selecting the best moves that keep leading towards that outcome. I know this leads to a large number of possible moves (something in the range of the number of atoms in the universe).. but is 2048 more or less complex?

Pseudocode:

for the current arrangement of tiles

- work out the possible moves

- work out what the board will look like if the program adds a 2 to the board

- work out what the board will look like if the program adds a 4 to the board

- move on to working out the possible moves for the new state

At this point, I'm thinking I will be here a while waiting on this to run...

So my question is - how would I begin to write this algorithm - what strategy is best for calculating the complexity of the game?

The big difference I see between 2048 and chess is that the program can select randomly between 2 and 4 when adding new tiles - which seems to add a massive number of additional possible moves.

Ultimately I'd like the program to output a single figure showing the number of possible permutations in the game. Is this possible?!

Answer 1

Now first we have to assume that all numbers are spawned as '4' to create as few moves as possible.

Let's start with small numbers first.

• Creating an '8' will require 1 move (2^0).

• Creating a '16, 2^4' will require 3 moves (2^0+2^1)

• Creating a '32, 2^5' will require 7 moves (2^2+2^1+2^0) and so on.

• Creating a '2^n' will require (2^(n-3)+...) moves.

You will then realize that the number of moves required is a summation of a geometric sequence.

sigma (2^k). The lower limit of k will be 0 and the upper limit being the 7.