How to work out the complexity of the game 2048?

Question

Edit: This question is not a duplicate of What is the optimal algorithm for the game 2048?

That question asks 'what is the best way to win the game?'
This question asks 'how can we work out the complexity of the game?'

They are completely different questions. I'm not interested in which steps are required to move towards a 'win' state - I'm interested in in finding out whether the total number of possible steps can be calculated.

I've been reading this 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, its possible (in theory) to work out all the possible moves that lead to a win state and work backwards, 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?

Psudocode:

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

Is there something which explains the rules of that thing? edit: now i get it... — deviantfan
As there are two random components and you want the exact number (not a theoretical maximum)...i think there isn´t a better solution than trying all possibilities. (By the way, this game is fun :D) — deviantfan
Yeah so what I'm asking is something like - 'is there a standard way to calculate that exact number programatically, or is only possible to guess at it due to the practicalities of calculating' e.g. my psudocode is going to take a long time and probably run out of memory before it finishes — finoutlook
Added note to the top of the question. Quite clearly not a duplicate. Don't know why people have jumped on the chance to mark it as such. — finoutlook

Bernhard Barker Bernhard Barker · Accepted Answer · 2014-03-19T15:21:32

Let's determine how many possible board configurations there are.

Each tile can be either empty, or contain a 2, 4, 8, ..., 512 or 1024 tile.

That's 12 possibilities per tile. There are 16 tiles, so we get 16¹² = 2⁴⁸ possible board states - and this most likely includes a few unreachable ones.

Assuming we could store all of these in memory, we could work backwards from all board states that would generate a 2048 tile in the next move, doing a constant amount of work to link reachable board states to each other, which should give us a probabilistic best move for each state.

To store all bits in memory, let's say we'd need 4 bits per tile, i.e. 64 bits = 8 bytes per board state.

2⁴⁸ board states would then require 8*2⁴⁸ = 2251799813685248 bytes = 2048 TB (not to mention added overhead to keep track of the best boards). That's a bit beyond what a desktop computer these days has, although it might be possible to cleverly limit the number of boards required at any given time as to get down to something that will fit on, say, a 3 TB hard drive, or perhaps even in RAM.

For reference, chess has an upper bound of 2¹⁵⁵ possible positions.

If we were to actually calculate, from the start, every possible move (in a breadth-first search-like manner), we'd get a massive number.

This isn't the exact number, but rather a rough estimate of the upper bound.

Let's make a few assumptions: (which definitely aren't always true, but, for the sake of simplicity)

There are always 15 open squares
You always have 4 moves (left, right, up, down)
Once the total sum of all tiles on the board reaches 2048, it will take the minimum number of combinations to get a single 2048 (so, if placing a 2 makes the sum 2048, the combinations will be 2 -> 4 -> 8 -> 16 -> ... -> 2048, i.e. taking 10 moves)
A 2 will always get placed, never a 4 - the algorithm won't assume this, but, for the sake of calculating the upper bound, we will.
We won't consider the fact that there may be duplicate boards generated during this process.

To reach 2048, there needs to be 2048 / 2 = 1024 tiles placed.

You start with 2 randomly placed tiles, then repeatedly make a move and another tile gets placed, so there's about 1022 'turns' (a turn consisting of making a move and a tile getting placed) until we get a sum of 2048, then there's another 10 turns to get a 2048 tile.

In each turn, we have 4 moves, and there can be one of two tiles placed in one of 15 positions (30 possibilities), so that's 4*30 = 120 possibilities.

This would, in total, give us 120¹⁰³² possible states.

If we instead assume a 4 will always get placed, we get 120⁵¹⁹ states.

Calculating the exact number will likely involve working our way through all these states, which won't really be viable.

How to work out the complexity of the game 2048?

1 Answers