Solving 2048 Using A* Search
One of my recent projects has been to attempt to solve the game 2048 using A* Search - it all started from a bet with my girlfriend about who could get the highest score, and I decided I’d “cheat” and just get my computer to do it for me. It didn’t work, she still managed to get to the 2048 tile first.
To start with, I wrote a command-line version of the 2048 game in Java - it was fairly simple, if a little unncessary, and worked well - I even had a little play of it before implementing the A* algorithm, and it was fairly fun to play. There were no real issues here, just a small amount of confusion about how to implement the “gravity” style of tile movement, but a little thought sorted that one out.
Then it came to actually writing the A* Search. I was lucky, in that I had a template from a previous University assignment to work from. All there really was to do was swap a few classes and methods, and change the heuristics.
The heuristic I am using at the minute is a less-than-optimal one, but it was the first one I tried. I was actually quite surprised at how effective it was.
(0 - sum of tiles) + solution depth
Like I say, this is not optimal, and certainly does not provide the highest-scoring solutions. But it does give fairly high scores, and certainly finds the 2048 tile - and even the 4096 tile.
Oher possible heuristics include:
- (0 - score) + solution depth
- Difference between largest tile and 2048 tile
- Mean value of tiles
There are a lot of options, and I have seen some impressive implementations. I look forward to improving this further.
Here’s a snippet of pseudocode for the A* algorithm:
While queue is not empty if game is solved print current state end running else get next state from queue add children of current state to queue endwhile