How many possible board states in 2048?
I recently found out about the famous 2048 game. For those of you who don't know how it works, it consists on a 4x4 board on where tiles which are powers of 2 are placed. On every turn, you "swipe" the board in any of the four directions, and a 2 (90% chance) or a 4 (10% chance) are placed randomly in any of the blank spaces. If two adjacent tiles are of the same value $n$, they can be merged into a tile of value $2n$. The game starts with 14 blank spaces and 2 randomly placed tiles (following the same rules as above).
I have written a considerably strong AI for it, but now I want to know how many possible different board states can be achieved (to see if the game can actually be mathematically solved).
Knowing the highest tile achievable is $2^{17}$, this means each tile can be in exactly 18 distinct positions (including 'blank' or zero). This yields an upper bound of $18^{16}$ different possible board states. However, it is obvious that all positions can't be achieved (for example, a board filled of 16 tiles of the same value, or a number higher than 4 being 'isolated' from the rest. Also, only one $2^{17}$, three $2^{16}$s, five $2^{15}$s, etc can exist at the same time on the board).
Then, you can also take into account rotations and simmetries. For example, there are 480 starting positions, but if you group together those that are rotations and/or simmetries of each other, you end up with only 75 distinct and unique starting positions (computed with a simple script). Edit: the number of boards achieved after two turns I calculated and that appeared here was wrong.
Giving an exact result for achievable board states is probably quite a difficult task, so I'm asking for a good upper bound for these possible states (counting groups of rotated/simmetric boards as one, if possible).
Edit for clarification: I'm not asking for any AI strategy, or this question is in any way related to my AI. It's a question to get deeper knowledge of the game, that's all.
Solution 1:
I think I have a solution... isnt not as beauty as I would like but my maths knowledge is limited. I will go point by point.
1.FIRST CONSIDERATIONS
We can think the board in the more simple way eliminating all symmetries: specular symmetries and rotational symmetries. So I will think the positions something like a tetris of 4 columns, i.e., the movement is from top to down.
Thinking this way cannot be possible to have any multiplicity of any number more than a pair (2) in any column but this formed by the suddenly apparition of a 2 or 4. So our pairs (or lines of three or four equal tiles) only can appear seeing by files instead of columns.
The pairs that we can have are of two types: contiguous and not contiguous. Contiguous pairs on columns only can appear after a collapse, so they are prohibited on columns of cardinality 4. And contiguous pairs of 2's are completely prohibited no matter what.
We think column as the position of elements but the sudden and random apparition of a 2 or 4 that occur in any board state.
2.COLUMS AND VARIATIONS ON COLUMS
From this we can have 5 types of columns, i.e., of cardinality 0 to 4, I will name as $C_i$ where i is the cardinality. The variations on the columns will depend if:
a) all tiles are different, in this case it will be $(17)_i$ where this is the representation of a falling factorial
b) there is some pair (or pairs), where we want that the pairs of 2 are not contiguous because you can have two contiguous pairs just if one of the number was generated by collapse (you cant generate a 2 by collapse). We will process the pair as a single, so for a column of 3 with a pair and a different number we will count it as $(17)_2$, i.e., the variations over two positions of 17 different values.
c) we must consider the geometry of pairs to compute variations only when the pair can be arranged in a different position. For a column of 3 if there is a pair of 2 it only can be as the extremes of the list because contiguity is prohibited for pair of 2's: 2o2. But for the case that the column have cardinality 4 we must consider the distributions 2o2c and the distribution o2c2. The singles values (the c and the o) from a point of view of the hipervariations (aka variations of level 2) are equivalents. But the case with two pairs different of 2's in xoxo cannot have any type of variation because the structure oxox in terms of the first variation level is equal.
d) to clarify: we calculate on columns over two levels of variations, just considering the different groups over the different distribution of singles and pairs of 2's or pairs of others numbers. Something like a variation level and a hipervariation level. We have then 3 types of sets: singles, pairs of 2's and others pairs, and a multiplicity bigger than a pair isnt possible on columns.
So the variations that we have by cardinality of the columns are: $C_0=1, C_1=17, C_2=(17)_2+16, C_3=(17)_3+3(17)_2-2\cdot 16, and\ C_4=(17)_4+2(17)_3+(17)_2$
This need a explanation: the first addend for each $C_i$ are the variations with all elements different, the others addends are the variations with valid pairs (any pairs are valid but the contiguous 2's). Example: for $C_2$ the variations of 17 different elements over two positions are $(17)_2$ and the valid pairs are just any pair but the 2's (16 type of pairs that arent 2's).
For $C_4$ the valid pairs are all with no contiguity at all because contiguity just can happen after a collapse of numbers that doesnt occur on a full column. You can have a column of 4 after a collapse by the apparition of a 2 or 4 but this is considered as a column of cardinality 3.
For $C_3$ the second number are permutations with repetition of 2 groups (multiplicity 1 and 2) multiplied by combinations of 17 elements in groups of two, i.e. $\binom{3}{2}\binom{17}{2}$. The third number are the invalid combinations with pair of 2's that are contiguous, i.e. $16\cdot 2$
3.VARIATIONS OF COLUMNS: COMPOSITION OF THE BOARD
The next level is to calculate all the variations of these 5 columns over the 4 possible positions (the board is 4x4) eliminating all the duplicates by specular and rotational symmetries.
First I will show a formula to express the variations of $C_i$
$$C_i=(17)_i+\binom{2/3}{i-3}3(17)_{i-1}+\binom{1}{i-4}(17)_{i-2}+(-2)^{i-2}16\cdot\delta_{2, 14\ \text{mod}\ i+1}$$
We need to add to the mix the presence of a 2 or 4 that is generated in every move of the board in any of the free positions, and the cases where one occupied tile is 2048. This is a factor that depends of the free (or blank) positions. And we need to fix the number of valid starting positions too, so
$$B(i)=(2(16-\Sigma i))^{1-\delta_{16,\Sigma i}}(1-\delta_{0,\Sigma i})$$
i.e. the total spaces less the cardinalities of the columns on this composition multiplied by 2 because we can have a 2 or a 4. The exponent is a Kronecker delta that prevent the zero when all columns have cardinality 4 (full board).
The second Kronecker delta eliminates the start with just one tile because you start with 2 tiles placed (you start with a column of cardinality 1).
(After is a fix for a few "floating" starting position, when both tiles arent on the borders of board).
We need to fix, from here, the duplicates that come from specular symmetry and rotational symmetry.
Fix for specular symmetry duplicates
All columns are duplicated by specularity in the sums but the compositions where columns have a perfect specular symmetry on cardinality (think about Rorschach images). So the formula need a general factor of $\frac{1}{2}$ to eliminate all of these duplicities and an internal factor that preserve the original multiplicity of these compositions with perfect symmetry (that are not duplicated).
This internal factor will be a Kronecker delta function that "see" when the composition have a perfect specular cardinality of columns.
The formula at this moment will be
$$S_1=\frac{1}{2}\sum_{a,b,c,d=0}^{4}C_aC_bC_cC_d\cdot B(i)\cdot 2^{\delta_{a,d}\delta_{b,c}}$$
But we need to add a fix for rotational duplicates too.
Fixing rotational duplicates
The rotational duplicates have a condition to exist: that cardinalities had a partial order what ensure a "stairs" shape that make possible for these composition to be rotated, so $a\geq b\geq c\geq d$. See that this law of composition prevent any duplicity by specularity.
This is because we are seeing the board as a tetris with a "gravity" so if the shape isnt something like a stairs the figure cant be rotated because isnt a valid shape with the fall mechanic.
So the fix for the rotational symmetry have this form
$$S_2=\sum_{a=1}^{4}\sum_{b=0}^{a}\sum_{c=0}^{b}\sum_{d=0}^{c}C_aC_bC_cC_d\cdot B(i)\cdot F(i)$$
Where F is a function that eliminates the false duplicates, i.e., the configurations that cant be rotated because they have pairs of contiguous 2's or more than pairs contiguous with other numbers.
In any position, talking of files of 3 or 4 contiguous and equals numbers, the probability for any number in any tile is $\frac{1}{17}$. So the probability that the same number appear contiguous is approximately $\frac{1}{17^3}$ if we are talking of 3 contiguous numbers or $\frac{1}{17^4}$ if we are talking of a full row. For the case of pairs of 2's the probability is $\frac{1}{18^2 17}$ that is an approximation of the mean of apparition (it changes depending on what tiles make the pair).
The amount of possible full rows of the same number is $d$, i.e., the cardinality of the last column in our stairs model for rotational duplicates.
The amount of possible trios will be $c+d$, and the amount of possible pairs of 2's will be $b+c+d$.
We will apply a factor (that is a probability) over each addend of $S_2$ (this is the F function). This is a binomial that is
$$P(X=0)=(1-p)^n, n\in\{d,c+d,b+c+d\}$$
So
$$F(i)=(1-\frac{1}{17^4}(1-\frac{1}{18^4 17}))^d(1-\frac{1}{17^3})^{c+d}(1-\frac{1}{18^2 17})^{b+c+d}$$
The second multiplier is a fix for duplicated full rows considering any numbers and two pairs of 2's.
4.FINAL FORMULA
The final (by now :p) formula is....:
$$S\approx S_1-S_2+S_3$$
Where $S_3=6$ that are a very little amount of starting positions where the first two tiles that appear are out of the borders.
P.S.: maybe a better approach to the problem a generating function... but my maths knowledge about it is near to zero.
P.S.2: sry, I had A LOT of edit of stupids and tiny mistakes (more) and some heavy mistakes (less). The formula of $C_i$ can be written in many different ways... I let one but surely isnt the more efficient on computational or symbolic sense.