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 :)

31 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