2 views

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

by (108k points)

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

• 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.