Today we are going to write a bot using Clojure to beat the game 2048. We are going to use a variation of the minimax algorithm called expectimax.

1. game rules

You can merge tiles by merging the whole board either horizontally or vertically. If you manage to get the 2048 tile, you win. After a merge (= player’s turn), a tile will appear randomly on an empty slot. The chance of that tile being a 4 is 0.1, the chance of it being a 2 is 0.9. After reaching the 2048 you can keep playing and the same rules apply.

In fact we are going to write a bot that is able to get the 8192 tile.

2. heuristic

First of all, we need a measure of how well the bot performs. If you want to come up with your own heuristic, pause here and play a few rounds.

After a few rounds, you probably realize that the largest tile should stay in a corner. Intuitively the larger tiles should stick together.

We can formalize these observations by splitting up the heursitic score into two parts:

cluster score

The cluster score is simply the actual board weighted by a matrix:

This is a measure of how monotone the board is. It leads to the highest tile sticking to the upper-left corner.

heterogeneous score

This score is actually a penalty. The higher this score, the worse for the player. It is calculated by summing the differences of all tiles to all their adjacent neighbours.

Finally, substract the penalty score from the cluster score:

And we are left with a function that maps a game board to a score. We are going to implement an algorithm that tries to maximize this score.

3. game simulation

The next part consists of a function to simulate moves. A move is either a player move, or a move by the environment (= spawning tiles). This distinction is important as we will see later on. The function we are looking for has following signature:

The first observation is, considering only horizontal moves, that each row merges independently. Our second observation reveals, that vertical moves can easily be transformed to horizontal moves by transposing the board. The last observation shows, that a left-merge equals a right-merge of the reversed vector.

If we solve merging of a single row along a single axis, we solve simulating player moves:

It is noteworthy, that we memoize the function merge-row-left. Assuming the maximum tile we want to reach is 8192 (= 2^13), there are only 13^4 possible combinations to make up a row. This function will potentially be called millions of times per second while searching for the score maximizing player move.

Introducing some transpose functions leads to our goal function execute-move:

4. expectimax

We are using a search algorithm with an adaptive depth of search. While searching the bot alternates between the chance layer and the max layer. The chance layer is where the environment spawns a tile randomly. We don’t know where it’s going to happen and we don’t know what tile it’s going to be: We have to calculate using the expectancy value of all possible boards:

At the max layer on the other hand, we are in control. We can simply execute all possible moves given a board and return the highest heuristic score using calculate-max.

Lastly, we expose our magnificent AI through a single function best-move returning the best move given a board:

Using pmap I am able to get 100% CPU usage on Java 8 HotSpot VM and a dual core machine. At most there are only 4 functions getting executed in parallel, so the performance gain through parallelization is probably not that great on machines with more cores.

You can find the source in this repo.