Solving 2048 Using A* Search

ne 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

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.

The Pseudocode

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

Screenshots