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.
- Category:
- Picks
Comments
To leave a comment, please click here to sign in to your MathWorks Account or create a new one.