A few months ago I ran out of 4g data on my cellphone and decided to install an offline game. This game was 2048 (you can try it here).
After a while I managed to finish it but I noticed that there were sequence of moves that got me better results quicker. One of those involved shoving all the number to the top-left corner by pushing Top and Left repeteadly. After a while I started thinking ‘Could there be another sequence of moves that would get me further in the game?’.
This post is about exactly that.
I started off by describing what a sequence of moves would be: ‘A sequence of moves I would repeat until I lost the game’. This would also need to include another sequence for when no other move in could be performed and I needed to ‘unstuck’ myself.
Now, if I want to compare how good the strategies are, I would have to play a couple of games using each sequence and see how far I got. Obviously the number of sequences was too big for me to try manually so I decided to grab a 2048 implementation of the game by yangshun and automate the playing in python. Some rules had to be set up beforehand though:
- I would have to play each sequence at least 100 games so that I could get a fair sample of scores for each sequence.
- The sequence would have to be smaller than 6 moves otherwise I would not be able to memorize it and this whole thing would have been pointless.
So, I started thinking about how many possible strategies there could be, and for a second there I was quite worried. However, soon enough, I realised that this board had a bunch of strange simmetries and a lot of sequences were actually the same. Take the example on the left. Each of the sequences can be obtained by either flipping and rotating the board. Furthermore, most sequences can be compressed into smaller sequences. In the example on the right, if we consider the first sequence we will see that using moves on the ‘unstuck’ sequence that exist on our main sequence is non-sensical since by the time we find ourselves stuck we must have already tried them. For the same reason, having the same move twice in the ‘unstuck’ sequence would not help. Finally, having smaller sequences inside your main sequence is redundant since you will be repeating that sequence anyway. In the end, as you see in the picture, the first sequence can be compressed into the last (smaller) sequence.
If you take all these factors into consideration you are left with about 1600 different strategies (maybe even less but I will leave that for another post). Finding and running them for 100 games seemed to take about 1h 30min even when I paralellized the whole thing to run each game in a different processor (maybe I could have done a better job but this was a side project so I was happy to get 6-7x improvements in speed)
At this point I wanted to try and make if faster. I was computing the score of each game by summing all the squares in the board (which is not how the score of the game is calculated) but there are a couple of different ways of computing the efficacy of each strategy (maybe getting stuck a lot is annoying for example) so, if i speed up the process up i could give them a try. So, I started devising a way of getting to the solution by not having to compute every single sequence and running it for 100 games each. This is what I first came up with:
- We start by generating a couple of random strategies
- We run those strategies for a couple of games (not 100, let’s say.. 10)
- We order those strategies by average score and keep the best
- We add a couple of other random strategies and go back to 1.
Eventually the score of the top solutions will stop improving significantly. Below is an example of the average score of the strategies at each point 3 and how the average score stops improving with time.
This method seemed to get to the best solution about 80% of the time and took 2 minutes to get there (obviously if we let it run for longer it would eventually find the best solution every time). At this point I was quite happy but wanted to see if I could improve the method still. Having tried a couple of genetic algorithms in college I decided to create a similar version of my own by tweaking the previous algorithm a bit. Now, instead of generating new random sequences in 3. I woulde creat ‘mutants’ of the best sequences and populate our ‘pool’ of strategies with them:
This method turned to be much better than my previous ‘random’ method. It got to the solution much faster (less than a minute) and more times (91%):
At some point around here I decided that I should stop, I had already found the best solution and all of this was really just a nice reason for me to try new things. It seems like the best sequence of moves is similar to the one I was using except that instead of trying to push the numbers to the corner you just try to push them to the top and create a sort of pyramid on the top. This means that you are less likely to have to press the Down direction that could otherwise ruin your whole plan. In fact, searching online, most methods/AI’s describe that you should have a taboo move (which in this case would be Down). 
There might be other methods out there that are better and this is not a solution that you could just brainless follow but it does seem to speed up the game a lot. All I can say is that since I started using it my highscore went through the roof and this was the score of my last game (and it will probably stay that way):
If you try it let me know how it goes!
You can find the code at: https://github.com/TMMV/howtobeat2048
You can also check the presentation I gave at pydata here.