Wednesday, 26 March 2014

An Artificial Intelligence for the 2048 game

Lately the 2048 game reached a good notoriety on the internet.


A discussion about possible algorithms which solve the 2048 game arose on StackOverflow.

The main discussed algorithms are:

The solution I propose is very simple and easy to implement. Although, it has reached the score of 131040. Several benchmarks of the algorithm performances are presented.


Algorithm

Heuristic scoring algorithm

The assumption on which my algorithm is based is rather simple: if you want to achieve higher score, the board must be kept as tidy as possible. In particular, the optimal setup is given by a linear and monotonic decreasing order of the tile values.

This intuition will give you also the upper bound for a tile value: $2^{n} \rightarrow 2^{16} = 65536$ where $n$ is the number of tile on the board. (There's a possibility to reach the 131072 tile if the 4-tile is randomly generated instead of the 2-tile when needed)

Two possible ways of organizing the board are shown in the following images



To enforce the ordination of the tiles in a monotonic decreasing order, the score si computed as the sum of the linearized values on the board multiplied by the values of a geometric sequence with common ratio $r<1$ .

$p_n \in Path_{0 \cdots N-1}$

$score = \sum_{n=0}^{N-1} value(p_n) * r^n$

Several linear path could be evaluated at once, the final score will be the maximum score of any path.

Decision rule

The decision rule implemented is not quite smart, the code in Python is presented here:

An implementation of the minmax or the Expectiminimax will surely improve the algorithm. Obviously a more
sophisticated decision rule will slow down the algorithm and it will require some time to be implemented.I will try a minimax implementation in the near future. (stay tuned)

Benchmark


  • T1 - 121 tests - 8 different paths - $r = 0.125$ 
  • T2 - 122 tests - 8-different paths - $r = 0.25$ 
  • T3 - 132 tests - 8-different paths - $r = 0.5$
  • T4 - 211 tests - 2-different paths - $r = 0.125$
  • T5 - 274 tests - 2-different paths - $r = 0.25$
  • T6 - 211 tests - 2-different paths - $r = 0.5$



In case of T2, four tests in ten generate the 4096 tile with an average score of $\sim 42000$

Code

The code can be found on GiHub at the following link: https://github.com/Nicola17/term2048-AI
It is based on term2048 and it's written in Python. I will implement a more efficient version in C++ as soon as possible.

StackOverflow

You can upvote my answer on StackOverflow here :)

89 comments :

  1. 2048 cupcakes reverse game is a alteration of 2048 game designed and developed by Italian Programmer.

    ReplyDelete
  2. Attend The Artificial Intelligence course From ExcelR. Practical Artificial Intelligence course Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Artificial Intelligence course.
    Artificial Intelligence course

    ReplyDelete
  3. Excellent! I love to post a comment that "The content of your post is awesome" Great work!
    digital marketing courses mumbai

    ReplyDelete
  4. Yuk Gabung di NAGAQQ: AGEN BANDARQ BANDARQ ONLINE ADUQ ONLINE DOMINOQQ TERBAIK

    Yang Merupakan Agen Bandarq, Domino 99, Dan Bandar Poker Online Terpercaya di asia hadir untuk anda semua dengan permainan permainan menarik dan bonus menarik untuk anda semua

    Bonus yang diberikan NagaQQ :
    * Bonus rollingan 0.5%,setiap senin di bagikannya
    * Bonus Refferal 10% + 10%,seumur hidup
    * Bonus Jackpot, yang dapat anda dapatkan dengan mudah
    * Minimal Depo 15.000
    * Minimal WD 20.000

    Memegang Gelar atau title sebagai Agen BandarQ Terbaik di masanya

    Games Yang di Hadirkan NagaQQ :
    * Poker Online
    * BandarQ
    * Domino99
    * Bandar Poker
    * Bandar66
    * Sakong
    * Capsa Susun
    * AduQ
    * Perang Bacarrat (New Game)

    Tersedia Deposit Via pulsa :
    Telkomsel & XL

    NAGAQQ: AGEN BANDARQ BANDARQ ONLINE ADUQ ONLINE DOMINOQQ TERBAIK

    Info Lebih lanjut Kunjungi :
    Website : NagaQQ
    Facebook : NagaQQ Official
    Kontakk : Info NagaQQ
    linktree : Agen Judi Online
    WHATSAPP 1 : +855977509035
    Line : Cs_nagaQQ
    TELEGRAM : +855967014811


    BACA JUGA BLOGSPORT KAMI YANG LAIN:
    agen bandarq terbaik
    Winner NagaQQ
    Daftar NagaQQ
    Agen Poker Online

    ReplyDelete
  5. 2048 gameshas a very low cost to entry, all things considered. The game is free and most people already have a phone or computer capable of running the game and there is plenty of free software out there to record runs.

    ReplyDelete
  6. Google started using site speed as a ranking signal in their algorithm way back in 2010, and it continues to serve as one of the many factors that determine where your website shows up in the search results. We help you WordPress Speed Optimization are Page Caching, PHP latest version, Image optimization and resizing, jquery update, Cache Preloading, Sitemap Preloading, GZIP Compression, Browser Caching, Database Optimization, Google Fonts Optimization, Lazyload, Minifying JS CSS HTML files, Deferring Unused JS/CSS, CDN setup, Mobile Detection, Stop unused CSS and JS file and many more optimization your WordPress website. So, your website super-fast loading within 1-5 seconds. WordPress Speed Optimization

    ReplyDelete
  7. Thanks for the informative and helpful post, obviously in your blog everything is good.. ExcelR Data Analyst Course

    ReplyDelete
  8. I quite like reading an article that can make people think. Also, thanks for allowing for me to comment!
    business analytics course

    ReplyDelete
  9. Thank you for sharing this amazing piece of content. You are doing a great job, thanks for it.
    Sad Shayari with Hindi Images, Sad Shayari for Facebook Whatsapp in Hindi Sad Quotes Hindi Best Sad Shayari Collection in Hindi

    ReplyDelete
  10. Well Said, you have furnished the right information that will be useful to anyone at all time. Thanks for sharing your Ideas.

    Oracle Dba training in bangalore
    Oracle Dba institutes in bangalore

    ReplyDelete
  11. neuramis filler
    Just a little background. We are a skincare retailer that specializes in Hyaluronic Acid Fillers and microneedling along with Korean Skincare/Kbeauty. I have listed a chunk of keywords below.

    ReplyDelete
  12. Anuvaa has the best Digital marketing Course in Mumbai

    ReplyDelete
  13. Thanks for Sharing this article. It is very much vauable content Anuvaa offers the best Digital Marketing Courses in Mumbai

    ReplyDelete
  14. Thanks for Sharing this article. It is very much vauable contentMahesh Mattta Sanda Wellness

    ReplyDelete
  15. Thanks for Sharing this article. It is very much vauable content Mahesh Matta

    ReplyDelete
  16. Одним з класичних способів підрізати нігті є короткий стиль. Короткі нігті часто вважаються більш практичними, але не завжди є багато класних дизайнів для них.

    ReplyDelete
  17. I wish more writers of this sort of substance would take the time you did to explore and compose so well. I am exceptionally awed with your vision and knowledge.
    data scientist training in hyderabad

    ReplyDelete
  18. Register now to participate in the intensive AI Training in Hyderabad program taught by experts at the AI Patasala training center.

    ReplyDelete
  19. You’re so cool! I do not believe I’ve truly read through a single thing like this before. So good to find somebody with a few original thoughts on this issue. Really.. many thanks for starting this up. This site is one thing that is required on the internet, someone with a little originality.

    야동

    ReplyDelete
  20. Hi there! I just want to offer you a huge thumbs up for the great information you have here on this post. I’ll be coming back to your website for more soon.

    오피

    ReplyDelete
  21. This website is really a walk-through for every one of the details you wanted concerning this and also didn't know who to ask. Glimpse right here, and also you'll absolutely uncover it.

    외국인출장

    ReplyDelete
  22. I'm satisfied, I must claim. Truly seldom do I run into a blog that's both educative as well as enjoyable, and let me tell you, you have struck the nail on the head. Your concept is impressive; the issue is something that inadequate individuals are speaking smartly about. I am very happy that I came across this in my search for something relating to this.마사지

    ReplyDelete
  23. Amazing Article! I would like to thank you for the efforts you had made for writing this awesome article. This article inspired me to read more. keep it up.
    Data science course in pune

    ReplyDelete
  24. I am a new user of this site, so here I saw several articles and posts published on this site, I am more interested in some of them, will provide more information on these topics in future articles.
    data science course in london

    ReplyDelete
  25. Great job get the best shayaries visit Shayarisove

    ReplyDelete
  26. This was an extremely wonderful post. Thanks for providing this info. little joe cartwright jacket

    ReplyDelete
  27. Our the purpose is to share the reviews about the latest Jackets,Coats and Vests also share the related Movies,Gaming, Casual,Faux Leather and Leather materials available Squid Game Pink Jacket

    ReplyDelete
  28. Amazingly by and large very interesting post. I was looking for such an information and thoroughly enjoyed examining this one. Keep posting. An obligation of appreciation is all together for sharing.data analytics course in gwalior

    ReplyDelete
  29. Thanks for this valuable information!
    This Comment Form

    ReplyDelete
  30. I love to recommend you Where can crawl Exciting Products latest Jackets, Coats and Vests Click Here Big Boss Leather Jacket

    ReplyDelete
  31. Wow. That is so elegant and logical and clearly explained. Brilliantly goes through what could be a complex process and makes it obvious. Thanks for Sharing This Article. It is very so much valuable content. Digital marketing training Mumbai

    ReplyDelete
  32. Very nice blogs!!! i have to learning for lot of information for this sites…Sharing for wonderful information. Thanks for sharing this valuable information to our vision. You have posted a trust worthy blog keep sharing digital marketing course Mumbai

    ReplyDelete
  33. Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!data scientist course in ghaziabad

    ReplyDelete
  34. I am a new user of this site, so here I saw several articles and posts published on this site, I am more interested in some of them, will provide more information on these topics in future articles.
    data science course in london

    ReplyDelete
  35. Best website to download Web Series movierulz4

    ReplyDelete
  36. Get the latest Movies on movierulz4 for free you can also download movies on this website

    ReplyDelete
  37. I really enjoyed reading your article. I found this as an informative and interesting post, so i think it is very useful and knowledgeable. I would like to thank you for the effort you made in writing this article. Hhh Leather Jacket

    ReplyDelete

  38. I like your post. I appreciate your blogs because they are really good. Please go to this website for Data Science course in Bangalore. These courses are wonderful for professionals.

    ReplyDelete
  39. this blog was really great, never seen a great blog like this before. i think im gonna share this to my friends.. data analytics course in mysore

    ReplyDelete
  40. I was basically inspecting through the web filtering for certain data and ran over your blog. I am flabbergasted by the data that you have on this blog. It shows how well you welcome this subject. Bookmarked this page, will return for extra.https://360digitmg.com/course/certification-program-on-digital-marketing

    ReplyDelete
  41. Great very helpful blog. Thanks For Sharing Such A Wonderful Blog. I will definitely go ahead and take advantage of this. Your Blog Is Very Informative. Again Thanks For Sharing This Blogs With Us. For more learning go through Skillslash.
    For Data Science Course Data Science Course In Bangalore

    ReplyDelete
  42. We are looking for an informative post it is very helpful thanks for sharing it. We are offering all types of leather jackets with worldwide free shipping.
    Black Leather Jacket
    Leather Bomber Jacket
    Mens Biker Leather Jacket
    Western Leather Jackets

    ReplyDelete
  43. Nice Blog! such a informative things you are sharing ,I really liked your content. If you wanna know about "Skillslash | Training with live industry experience that gets you hired" go to Data science courses in bangalore

    ReplyDelete
  44. I am very impressed to read this blog. I hope you will continue to upload similar blogs. Thank you very much. I have an online store with the name FLYING LEATHER JACKET please visit for an awesome collection.
    MEN AVIATOR LEATHER JACKETS
    B3 BOMBER JACKETS
    MOTOGP LEATHER SUIT
    MOTOGP LEATHER JACKETS

    ReplyDelete
  45. 360DigiTMG, the top-rated organisation among the most prestigious industries around the world, is an educational destination for those looking to pursue their dreams around the globe. The company is changing careers of many people through constant improvement, 360DigiTMG provides an outstanding learning experience and distinguishes itself from the pack. 360DigiTMG is a prominent global presence by offering world-class training. Its main office is in India and subsidiaries across Malaysia, USA, East Asia, Australia, Uk, Netherlands, and the Middle East.

    ReplyDelete
  46. You put really very helpful information. Keep it up. Keep blogging. Looking to reading your next post. urdu poetry 2 lines

    ReplyDelete
  47. My Tractor Forum A family friendly forum community dedicated to all Tractor owners and enthusiasts. Come join the discussion about specifications, modifications, huawei manager 7 apk, huawei manager version 7, huawei manager 2022, huawei manager, huawei manager 6.1 apk, huawei manager apk, download huawei manager 6.1 apk, huawei manager v7 2022, huawei manager v7, huawei manger is one of the best apps that supports Huawei ..

    ReplyDelete
  48. Nice thanks for sharing informative post like this keep posting if like more details mylearnnest.com visit my website linkhttps://www.mylearnnest.com/best-sap-training-in-hyderabad/

    ReplyDelete
  49. Thanks for sharing such beautiful information with us. We hope you will share some more information about it. We really enjoy your blog & content.
    ericemanuelshop.com

    ReplyDelete
  50. Thanks for sharing such beautiful information with us. We hope you will share some more information about it. We really enjoy your blog & content.
    https://www.officialdreammerch.com/

    ReplyDelete
  51. I really like this blog thanks for sharing with us hope for more blog like this one.

    Ribera Jacket

    ReplyDelete
  52. Thanks for this. This is the simplest explanation I can understand given the tons of Explanation here.
    trapstarshop

    ReplyDelete
  53. This is incredibly cute! I've never seen this. I am going to feature this at somedaycrafts.blogspot.com. Grab my "featured" button.
    대구출장샵
    부산출장샵
    울산출장샵
    서울출장샵
    인천출장샵

    ReplyDelete
  54. I like your blog because it is so informative. I learned a lot from your post thank you.
    https://shophoodies.co.uk/

    ReplyDelete
  55. Thanks for the bloghttps://chukkabootsmaker.com/ loaded with so many information. Stopping by your blog helped me to get what I was looking for.

    ReplyDelete
  56. I enjoyed over read your blog post. Your blog have nice information, I got good ideas from this amazing blog. I am always searching like this type blog post.광양출장아로마
    나주출장아로마
    목포출장아로마
    순천출장아로마
    여수출장아로마
    익산출장아로마

    ReplyDelete
  57. Thanks for the blog loaded with so muchhttps://theboyfriendjeans.com/ information. Stopping by your blog helped me to get what I was looking for.

    ReplyDelete