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

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

Screenshot of the output of the 2048 game, with the text "Solution Found!", and an in-progress 2048 game with a maximum score of 2048

Screenshot of the output of the 2048 game, with the text "Solution Found!", and an in-progress 2048 game with a maximum score of 4096