File Exchange Pick of the Week

Our best user submissions

2048 Algorithms

Jiro's picks this week are 2048 algorithms submitted by Oliver Woodford, Athi Narayanan, and Viktor.

4 weeks ago, I posted this blog post asking people to submit algorithms for solving my 2048 App. I just want to say "WOW and Thanks!!" to everyone who participated. It was great to have so many entries. I received 15 different entries, most of which were posted as comments for the blog post. The entries ranged from simple algorithms (including my random-direction strategy, "myAI") to very sophisticated algorithms that looked ahead multiple moves to find the best move.

For this blog post, I'm simply going to reveal the results from the 1000-run simulations for each algorithm. Let's take a look at the summary of the simulations.

load summaryTable
summaryTable(:,{'Algorithm','Author','HighScore','HighBlock','Time'})
ans = 
          Algorithm             Author      HighScore    HighBlock     Time  
    ______________________    __________    _________    _________    _______
    oliverAI_v2               Oliver W      60540        4096          504.96
    myAI_athi                 Athi N        49132        4096             NaN
    viktorAI                  Viktor        36600        2048          4.5363
    oliverAI_v1               Oliver W      36276        2048          13.848
    myAI_JRM                  Jeremy M      35448        2048            3570
    myAI_kasztel              kasztel       31052        2048           2.567
    myAIFinal                 Boon          19752        1024          8.7533
    greedyAI                  Guanfeng L    16764        1024          42.379
    recurAI                   Guanfeng L    16356        1024          177.27
    downAI                    Keith          8388         512          1.1215
    myAI_Pooya                Pooya R        7400         512          1.2279
    myAI_sequential           Seth D         7052         512         0.24592
    myAISmart                 Jiro D         7016         512          0.9444
    myAI_left                 John T         6616         512         0.31477
    myAI_move2pair_v2         John T         5688         512          15.995
    myAI_sequential_double    John T         5288         512         0.20424
    myAI                      Jiro D         3052         256         0.43289

It looks like we have a clear winner! Oliver's second version was able to get a high score of over 60000, with a high block of 4096! His algorithm is one of the algorithms that heavily make use of the look-ahead technique. But you can also see that his highest score took over 500 seconds to complete. Athi's algorithm had the 2nd highest score of 49132. I had some problems with my analysis code for reproducing runs, so I don't have the time for Athi's best run. What was impressive was that Viktor's algorithm reached 36600 points (high block of 2048) in only 4.5 seconds. In fact, you can see quite a variation in execution times across different algorithms.

But this table is only looking at the best score out of 1000 simulations. Let's now look at the distribution of the highest blocks that were achieved. We'll take a look at it as a heat map. Note that the order is the same as the table above (in descending order of HighScore).

In general, there seems to be a correlation between the distribution of the high blocks and the highest score achieved. It's impressive to see that Oliver's algorithm was able to get 2048 or higher over 70% of the time. Very nice!

Other analyses

There are other metrics, which I haven't been able to look at for this blog post. A similar heat map for the scores would be a good one. However, in general the scores and the high blocks were correlated, so I would expect a similar-looking heat map.

Animation of the algorithms

Let's take a look at a couple of the high scoring algorithms. Note that this animation is a "replay", so it doesn't reflect the true computation time of the algorithms. The left one is Oliver's algorithm and the right one is Viktor's algorithm. You can clearly see the differences in the strategies. Viktor's algorithm tries to stack the blocks to the bottom left, while Oliver's has a more spread out approach trying to bring together similar blocks, even if they're far apart.

Winner

So who is the winner? Well, everyone's a winner! :) It was a lot of fun seeing the various algorithms. Okay, okay. I'll narrow down the winners to a few people. Even though I had defined a clear metric in my previous post, I'm going to slightly modify it and give prizes to three people - Oliver Woodford, Athi Narayanan, and Viktor. Both Oliver and Athi were able to very successfully achieve 2048, while Viktor was able to get the 3rd highest score with a fast algorithm. Congratulations!! We'll contact you so that we can send you some MathWorks prizes.

I hope you all enjoyed this mini-challenge. If you have any comments on this topic, please post here.




Published with MATLAB® R2014a

|

Comments

To leave a comment, please click here to sign in to your MathWorks Account or create a new one.