# Submit your algorithms to solve 2048! 18

Posted by **Jiro Doke**,

Jiro's pick this week is 2048 MATLAB.

**"2048"**

Need I say more? I'm certain that many of you know what I'm talking about. 2048 is an online and mobile game created by Gabriele Cirulli recently. All I can say is that it is an addictive game that has already resulted in a few MATLAB implementations.

A couple of weekends ago, I also spent a day implementing a MATLAB version. I probably spent more time than I needed to on trying to make it look as close as possible to the original version, but it was a lot of fun.

But then, one of my colleagues, Seth (who was also just featured in this blog last week), suggested including a mechanism for feeding in different algorithms to solve the game. There must be an AI algorithm that would solve the game or produce a high score consistently.

In the app, I've included the ability to select a MATLAB function as the solving algorithm. Then you can see the algorithm in action as it tries to solve the game. The algorithm must be defined as a MATLAB function that takes in a 4x4 matrix representing the game board (NaN for empty spots) and returns a character array representing the direction to move ('up', 'down', 'right', or 'left'). Here's an example of a simple algorithm that randomly chooses a direction.

function direction = myAI(board) d = {'up', 'down', 'right', 'left'}; direction = d{randi(4)};

I've also included a command line simulator, which you can use to do a montecarlo simulation of a particular algorithm.

game = Game2048Simulator(@myAI); simulate(game, 1000) % 1000 simulations viewResult(game, 25) % 25 histogram bins

We can display the highest score and compute what percentages of the simulation resulted in each of the highest block.

% Display highest score disp(['Highest score: ', num2str(max(game.Result.Score))]) disp(' ') % Get the unique values for high blocks highblocks = game.Result.HighestBlock; blocks = unique(highblocks); % Compute the percentage of occurrance for each high block value nSims = length(highblocks); for id = 1:length(blocks) percentage = nnz(highblocks == blocks(id)) / nSims; disp([num2str(blocks(id)), ' ', num2str(percentage*100), '%']) end

Highest score: 3172 16 0.2% 32 6.8% 64 34.5% 128 49.7% 256 8.8%

**Submit your algorithm!**

So here's a challenge for you. Submit your algorithm and win some MathWorks swag! I will give prizes for each of the following criteria:

- Highest score - In the example above,
**3172**. - Highest block OR in the case of a tie for "Highest block", the one with the highest percentage for the highest block. In the
example above,
**8.8% for 256**.

*It was brought to my attention that since the simulator I've included with the File Exchange entry would stop the game once
you reach 2048, I am limiting the highest score you could get. For my next update, I will change it so that the game will
continue until no more blocks can move.*

If your algorithm is fairly short, please submit the algorithm through the comments for this blog post. Be sure to use code formatting. For lengthy algorithms or multi-function algorithms, feel free to email them to me (as ASCII text).

In the next blog post I write, I will go over some of the winning algorithms you have submitted.

Enjoy!!

Get
the MATLAB code

Published with MATLAB® R2014a

## 18 CommentsOldest to Newest

Interestingly, going clockwise around the 4 directions has significantly better performance than random directions. For 1000 simulations, this strategy had a mean score of 2319, a median of 2354, and a max score of 7000:

A slight modification that simply doubles each move.

Output:

It’s not very clever and it gets stuck occasionally, but it doubled my last attempt.

Results from 100 iterations:

Typo in the above algorithm.

The last conditional should read:

The 4 is an error. Now the algorithm will not get stuck.

Focusing on one (e.g. top left) corner gives some improvement to the above. For 1000 simulations, this strategy had a mean score of 2604.5, a median of 2500, and a max score of 7548:

Output:

A simple greedy algorithm. At each step, try to make a move in all 4 directions, and pick the one that results in most blocks empty. Ties are broken randomly. With 100 runs, it achieves highest score 12640.

A boolean property “isMoved” is added to the class TwentyFortyEight to keep an record if a “move” actually moves any block. It’s updated towards the end of the move() method.

Output:

Implemented a look-ahead-n-step greedy algorithm. The AI entry point is the following. “level” specifies how many steps to look ahead.

Then “emptyAndScoreAIRecur” is called recursively to find the best level-step move. In evaluating a move, it’s first ranked according to the number of empty cells it will lead to. If tied in empty cell number, then ranked according to the score the move leads to.

With 2-level recursion (look ahead 2 steps), it gets this in 100 runs:

Following on from Guanfeng’s approach, I compute all combinations of 3 moves, with all possible new tiles considered. At the end, every board reachable after 3 moves has a probability, and I marginalize the number of empty spaces left over the first of the 3 moves, to give the expected number of free spaces. I then simply choose the move which maximizes this.

The first game I ran this on it scored 12000+. The second game it got a 2048 square and continued on to score 32188! I have to say it is breathtaking to watch in action.

I haven’t tried getting it to look more moves ahead. It’s a trivial change to the code but the memory and computational requirements increase exponentially.

Anyway, here’s the code:

I just ran my code looking 4 moves ahead. It is much slower, but it speeds up when the board gets more cluttered (as there are fewer possible new tiles to consider). Of course, when the board gets more cluttered is exactly when you might want to look more moves ahead, so some dynamic selection of the number of moves to look ahead might be sensible. Having said that, it only made 12476 on the first go, so it doesn’t seem to offer much improvement over 3 looking moves ahead.

Wow, this is great, everyone! I’m impressed at these algorithms!

@Guanfeng Liang, at least for this post, I don’t want to change the original class definition, in order to keep everything the same and fair for everyone. So I simply replaced your

with

These should be equivalent. You also had

which I replaced with

Keep them coming!

I thought a bit more about how I choose the direction based on the marginalization, and made a few improvements. Firstly, instead of marginalizing over the first move, I marginalize over sets of N moves. Secondly, instead of maximizing expected number of free squares, I maximize expected gain in score. Finally, I do some dynamic selection of number of moves to look ahead; when the board is more cluttered, I look more moves ahead.

I have run this code on one game only so far. It mostly runs as fast as a human could play (just pressing random keys), but does slow down when you get to only 2 free tiles, as I look 5 moves ahead at that point. However, it’s only about a second in that case too (on my decent PC). The result was: score – 36560, highest square – 2048, moves – 1900.

I’m sure improvements could be made, especially in taking into account the probability of the game ending, and minimizing this.

Here’s the code:

Clearly there is a way to go, though, as this page, which I’ve just found, demonstrates:

http://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048

My algorithm is similar to the expctimax algorithm of nneonneo, though they are looking 8 moves ahead and have a different cost function.

This attempt reflects how I usually start my (manual) games in such a way that doesn’t require too much thinking.

A thousand iterations yields the following scores

Hi Everyone :)

My strategy is to focus on filling up the last row, trying to keep the largest number in the bottom-left corner by avoiding “right” steps when the bottom row is not filled with numbers. I oly allow “up” moves when there is no other way to go.

I implemented a function that executes steps so I can look 2 level deep into the game and the move that I choose is the one that results in the maximum profit (score gain) in the upcoming 2 moves.

Hi Everyone!

I improved a bit my previous code. Now, while keeping the main strategy, I look 3 steps ahead. This leads to a significant improvement. I only post the modified code segment now.

This code solves the puzzle, although not necessarily every time. Early moves are made quickly, although it slows down during later stages of the puzzle as it looks further ahead. (See comments in code for details.)

I am newbie compare to those before me. I just do it for fun and to learn Matlab OOP.

I used sum of square of the elements in the board. If else statements are used to keep the max tile in right bottom direction and prevent the invalid move. Is a bit of mess and some of the if else statement might be redundant but i don’t have time to clean them up. Well, it gives me 11.5% chance to get the 2048 tile.

Class:

Other custom function:

I also used the max2 function downloaded from mathwork for the codes above.