2048 - Solving 2048 with AI 🤖

Leveraging Monte-Carlo (MC) Move Evaluation

Image for post
Image for post

In today’s article, I am going to show you how to solve the famous 2048 game with Artificial Intelligence. You will learn the essentials behind the Monte-Carlo algorithm and at the end of this article, you will be able to create an agent that without any domain-specific knowledge beats average human scores in 2048.

AI gameplay

Table of Contents

If you are an iOS user, feel free to check my 2048 AI app that allows to both play 2048 and watch how AI solves it! It would definitely help you follow this article.

About 2048

2048 is a single-player sliding block puzzle game designed by Italian web developer Gabriele Cirulli. The game’s objective is to slide numbered tiles on a grid to combine them to create a tile with the number 2048. However, one can continue to play the game after reaching the goal, creating tiles with larger numbers.

Candy Crush for math geeks”, Wall Street Journal

How to play?

Swipe ↑, →, , or ← to move the tiles. Every move generates a new tile at a random unoccupied position.

Image for post
Image for post
Moving tiles with ← swipe

How to score?

Merge tiles with the same values. Every merged tile is added to your score.

Image for post
Image for post
Merging tiles with ↓ action

What’s the goal of the game?

To score as many points as possible.

Image for post
Image for post
Gameplay example

Before proceeding to the AI solver part, I would recommend you to play the game yourself. You will get more familiar with its rules and possibilites.

Monte-Carlo (MC)

One of the possible ways to solve the game of 2048 is to exploit the MC algorithm. Its biggest advantage is that it is a general-purpose solver, which means that it can yield output without any game specific input.

So how does it work?

Monte-Carlo is as a heuristic search algorithm that is based on applying the most promising moves.

But how can we determine which one of the available moves (↑, →, ↓, ←) is the most promising?

In order to do so, we can for every move:

  1. Execute a series of background runs.
  2. Group them by the initial move.
  3. Count an average final score for each initial move.
  4. Pick the initial move with the highest average final score.

For the more detailed explanation of the magic behind the MC algorithm, please check the following article that was deeply focused on the general purpose solvers.

Now that we know the underlying concept of the MC algorithm, let’s apply it to the game of 2048!

2048 AI Solver

Let’s get straight to the point. Our goal is to predict the best move for a given board state.

Line 1

To receive the best move (ShiftDirection), we are supplying our getBestMove function with the current board state i.e an array of tiles, where each tile has a value and a position.

Lines 2–5

We need to copy our board n times, where n is the number of runs that we are going to perform.

Lines 6–11

For each copied board, we are going to perform a random run. Generating random run is very simple, we just need to execute random actions until we have no available moves left. Ultimately we are going to persist its initial move and the final score.

Line 12

From the collected runs we are going to derive the best move.

It may look tricky at a first sight, so let’s dive into an example to get a better understanding of what’s going on.

Given a following initial state.

Initial state

Let’s ask our MC AI what’s the best move in such a situation. For the sake of simplicity, let’s perform only 10 background runs starting from the given state.

Our random background runs’ results look as follows, they are already grouped by their initial moves.

Now let’s calculate an average final score for a given initial move.

Finally, let’s select an initial move associated with the maximum value.

MC AI’s prediction would be to swipe Up.

Results

To measure AI Solver’s performance, I’ve decided to perform 10 full games for every configuration. By configuration I mean how many background runs should be performed to calculate each move, i.e 100, 500 or 1000 runs.

Results look as follows.

Image for post
Image for post

As expected, the more background runs we perform the higher the final score.

Image for post
Image for post
Image for post
Image for post

Similarly to the final score, the top tile that we reach also gets higher if we increase the number of background runs.

Image for post
Image for post
Image for post
Image for post

Above results are more than satisfying! 2048 AI Solver performs not only on an ‘above human’ level but what’s most surprising, it does so without any knowledge about the game i.e domain-specific inputs or hardcoded rules. It is a general-purpose solver that because of its versatility can be applied to a wide majority of applications.

Bonus

If you are a true 2048 fan, check my other 2048-based game called Tetris X 2048. As the name suggests, it combines the classic Tetris with 2048. It’s very challenging but definitely rewarding. Don’t hesitate to check it out!

What’s next?

While MC algorithm proved to be very successful in solving the game of 2048, we don’t have to stop here. MC can be implemented in other games and applications as well and I encourage you to try it. I am looking forward to seeing your results!

Questions? Comments? Feel free to leave your feedback in the comments section or contact me directly at https://gsurma.github.io.

And don’t forget to 👏 if you enjoyed this article 🙂.

Image for post
Image for post