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?!