{"id":5288,"date":"2014-05-02T12:16:20","date_gmt":"2014-05-02T16:16:20","guid":{"rendered":"https:\/\/blogs.mathworks.com\/pick\/?p=5288"},"modified":"2020-10-09T00:17:11","modified_gmt":"2020-10-09T04:17:11","slug":"2048-algorithms","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/pick\/2014\/05\/02\/2048-algorithms\/","title":{"rendered":"2048 Algorithms"},"content":{"rendered":"
\r\n

Jiro<\/a>'s picks this week are 2048 algorithms submitted by Oliver Woodford, Athi Narayanan, and Viktor.\r\n <\/p>\r\n

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

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

load summaryTable<\/span>\r\nsummaryTable(:,{'Algorithm'<\/span>,'Author'<\/span>,'HighScore'<\/span>,'HighBlock'<\/span>,'Time'<\/span>})<\/pre>
ans = \r\n          Algorithm             Author      HighScore    HighBlock     Time  \r\n    ______________________    __________    _________    _________    _______\r\n    oliverAI_v2               Oliver W      60540        4096          504.96\r\n    myAI_athi                 Athi N        49132        4096             NaN\r\n    viktorAI                  Viktor        36600        2048          4.5363\r\n    oliverAI_v1               Oliver W      36276        2048          13.848\r\n    myAI_JRM                  Jeremy M      35448        2048            3570\r\n    myAI_kasztel              kasztel       31052        2048           2.567\r\n    myAIFinal                 Boon          19752        1024          8.7533\r\n    greedyAI                  Guanfeng L    16764        1024          42.379\r\n    recurAI                   Guanfeng L    16356        1024          177.27\r\n    downAI                    Keith          8388         512          1.1215\r\n    myAI_Pooya                Pooya R        7400         512          1.2279\r\n    myAI_sequential           Seth D         7052         512         0.24592\r\n    myAISmart                 Jiro D         7016         512          0.9444\r\n    myAI_left                 John T         6616         512         0.31477\r\n    myAI_move2pair_v2         John T         5688         512          15.995\r\n    myAI_sequential_double    John T         5288         512         0.20424\r\n    myAI                      Jiro D         3052         256         0.43289\r\n<\/pre>
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\r\n      of 4096! His algorithm is one of the algorithms that heavily make use of the look-ahead technique. But you can also see that\r\n      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.<\/i> What was impressive was that Viktor's algorithm reached 36600 points (high block of 2048) in only 4.5 seconds. In fact, you\r\n      can see quite a variation in execution times across different algorithms.\r\n   <\/p>\r\n   
But this table is only looking at the best score out of 1000 simulations. Let's now look at the distribution of the highest\r\n      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\r\n      order of HighScore).\r\n   <\/p>\r\n   
 <\/p>\r\n   
In general, there seems to be a correlation between the distribution of the high blocks and the highest score achieved. It's\r\n      impressive to see that Oliver's algorithm was able to get 2048 or higher over 70% of the time. Very nice!\r\n   <\/p>\r\n   
Other analyses<\/b><\/p>\r\n   
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\r\n      be a good one. However, in general the scores and the high blocks were correlated, so I would expect a similar-looking heat\r\n      map.\r\n   <\/p>\r\n   
Animation of the algorithms<\/b><\/p>\r\n   
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\r\n      the true computation time of the algorithms. The left one is Oliver's algorithm and the right one is Viktor's algorithm. You\r\n      can clearly see the differences in the strategies. Viktor's algorithm tries to stack the blocks to the bottom left, while\r\n      Oliver's has a more spread out approach trying to bring together similar blocks, even if they're far apart.\r\n   <\/p>\r\n   
\r\n\r\n
\nhttps:\/\/blogs.mathworks.com\/pick\/files\/Oliver.mp4<\/a><\/video><\/div> 
https:\/\/blogs.mathworks.com\/pick\/files\/Viktor.mp4<\/a><\/video><\/div>\r\n      \r\n   <\/p>\r\n   
Winner<\/b><\/p>\r\n   
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\r\n      down the winners to a few people. Even though I had defined a clear metric in my previous post<\/a>, I'm going to slightly modify it and give prizes to three people - Oliver Woodford, Athi Narayanan, and Viktor. Both Oliver\r\n      and Athi were able to very successfully achieve 2048, while Viktor was able to get the 3rd highest score with a fast algorithm.\r\n      Congratulations!! We'll contact you so that we can send you some MathWorks prizes.\r\n   <\/p>\r\n   
I hope you all enjoyed this mini-challenge. If you have any comments on this topic, please post here<\/a>.\r\n   <\/p>