algorithm हरण गेम 2048 के लिए इष्टतम एल्गोरिदम क्या है?




फ्लो चार्ट बनाने की विधि (12)

मैंने हाल ही में गेम 2048 पर ठोकर खाई है। आप "बड़े" टाइल्स बनाने के लिए चारों दिशाओं में से किसी एक में उन्हें स्थानांतरित करके समान टाइल्स मर्ज करते हैं। प्रत्येक चाल के बाद, 2 या 4 मूल्य के साथ यादृच्छिक खाली स्थिति पर एक नया टाइल दिखाई देता है। खेल समाप्त हो जाता है जब सभी बक्से भर जाते हैं और कोई चाल नहीं होती है जो टाइल मर्ज कर सकती है, या आप 2048 मूल्य के साथ टाइल बनाते हैं।

एक, मुझे लक्ष्य तक पहुंचने के लिए एक अच्छी तरह से परिभाषित रणनीति का पालन करना होगा। तो, मैंने इसके लिए एक कार्यक्रम लिखने के बारे में सोचा।

मेरा वर्तमान एल्गोरिदम:

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

मैं जो भी कर रहा हूं वह किसी भी समय है, मैं टाइल्स को मान 2 और 4 साथ मर्ज करने का प्रयास करूंगा, यानी, मैं जितना संभव हो सके 2 और 4 टाइल्स रखने की कोशिश करता हूं। अगर मैं इसे इस तरह से कोशिश करता हूं, तो अन्य सभी टाइल्स स्वचालित रूप से विलय हो रहे थे और रणनीति अच्छी लगती है।

लेकिन, जब मैं वास्तव में इस एल्गोरिदम का उपयोग करता हूं, तो गेम को समाप्त होने से पहले मुझे केवल 4000 अंक मिलते हैं। अधिकतम अंक AFAIK 20,000 से थोड़ा अधिक अंक है जो मेरे वर्तमान स्कोर से बड़ा तरीका है। क्या ऊपर की तुलना में बेहतर एल्गोरिदम है?


मैं एआई कार्यक्रम के लेखक हूं कि इस धागे में दूसरों ने उल्लेख किया है। आप action में एआई देख सकते हैं या source पढ़ सकते हैं।

वर्तमान में, कार्यक्रम मेरे लैपटॉप पर ब्राउजर में जावास्क्रिप्ट में चल रहे 90% जीत दर के बारे में सोचने के बारे में 100 मिलीसेकंड दिए गए हैं, इसलिए सही नहीं है (अभी तक!) यह बहुत अच्छा प्रदर्शन करता है।

चूंकि गेम एक अलग राज्य स्थान है, सही जानकारी, शतरंज और चेकर्स जैसे बारी आधारित गेम, मैंने उन तरीकों का उपयोग किया जो उन खेलों पर काम करने के लिए साबित हुए हैं, अर्थात् अल्फा-बीटा छंटनी के साथ minimax search । चूंकि वहां पहले से ही उस एल्गोरिदम पर बहुत सारी जानकारी है, इसलिए मैं केवल दो मुख्य हेरिस्टिक्स के बारे में बात करूंगा जो मैं स्थिर मूल्यांकन समारोह में उपयोग करता हूं और जो अन्य लोगों ने यहां व्यक्त किए गए अंतर्ज्ञानों को औपचारिक रूप से कार्यान्वित किया है।

दिष्टता

यह ह्युरिस्टिक यह सुनिश्चित करने की कोशिश करता है कि टाइल्स के मूल्य सभी बाएं / दाएं और ऊपर / नीचे दिशाओं के साथ या तो बढ़ रहे हैं या घट रहे हैं। यह ह्युरिस्टिक अकेले अंतर्ज्ञान को कैप्चर करता है कि कई अन्य ने उल्लेख किया है कि उच्च मूल्यवान टाइल्स को कोने में क्लस्टर किया जाना चाहिए। यह आम तौर पर अनाथ होने से छोटी मूल्यवान टाइल्स को रोक देगा और बोर्ड को बहुत व्यवस्थित रखेगा, जिसमें छोटे टाइल्स कैस्केडिंग और बड़े टाइल्स में भरने होंगे।

यहां एक पूरी तरह से monotonic ग्रिड का एक स्क्रीनशॉट है। मैंने अन्य हेरिस्टिक्स को नजरअंदाज करने के लिए eval function set के साथ एल्गोरिदम चलाकर इसे प्राप्त किया और केवल monotonicity पर विचार करें।

चिकनाई

उपर्युक्त उपरोक्त अकेले संरचनाएं बनाने में काम करती है जिसमें आसन्न टाइल्स मूल्य में घट रहे हैं, लेकिन निश्चित रूप से विलय करने के लिए, आसन्न टाइलों को एक ही मूल्य होना चाहिए। इसलिए, चिकनीपन हेरिस्टिक केवल इस गिनती को कम करने की कोशिश कर पड़ोसी टाइल्स के बीच मूल्य अंतर को मापती है।

हैकर न्यूज़ पर एक टिप्पणीकार ने ग्राफ सिद्धांत के संदर्भ में इस विचार का एक दिलचस्प औपचारिकरण दिया।

इस उत्कृष्ट पैरोडी कांटा की सौजन्य, पूरी तरह चिकनी ग्रिड का एक स्क्रीनशॉट यहां दिया गया है।

नि: शुल्क टाइल्स

और आखिरकार, बहुत कम मुफ्त टाइल्स रखने के लिए जुर्माना है, क्योंकि गेम बोर्ड बहुत क्रैम्प होने पर विकल्प जल्दी से बाहर हो सकते हैं।

और बस! इन मानदंडों को अनुकूलित करते समय गेम स्पेस के माध्यम से खोजना उल्लेखनीय रूप से अच्छा प्रदर्शन करता है। स्पष्ट रूप से कोडित चाल रणनीति की बजाय इस तरह के सामान्यीकृत दृष्टिकोण का उपयोग करने का एक लाभ यह है कि एल्गोरिदम अक्सर दिलचस्प और अप्रत्याशित समाधान ढूंढ सकता है। यदि आप इसे देखते हैं, तो यह अक्सर आश्चर्यजनक लेकिन प्रभावी चाल करेगा, जैसे अचानक दीवार या कोने के खिलाफ यह स्विच करना।

संपादित करें:

यहां इस दृष्टिकोण की शक्ति का प्रदर्शन है। मैंने टाइल मानों को अनदेखा कर दिया (इसलिए यह 2048 तक पहुंचने के बाद जारी रहा) और यहां आठ परीक्षणों के बाद सबसे अच्छा परिणाम है।

हां, यह 2048 के साथ 4096 है। =) इसका मतलब है कि उसने उसी बोर्ड पर तीन बार छिपी हुई 2048 टाइल हासिल की।


I think I found an algorithm which works quite well, as I often reach scores over 10000, my personal best being around 16000. My solution does not aim at keeping biggest numbers in a corner, but to keep it in the top row.

Please see the code below:

while( !game_over ) {
    move_direction=up;
    if( !move_is_possible(up) ) {
        if( move_is_possible(right) && move_is_possible(left) ){
            if( number_of_empty_cells_after_moves(left,up) > number_of_empty_cells_after_moves(right,up) ) 
                move_direction = left;
            else
                move_direction = right;
        } else if ( move_is_possible(left) ){
            move_direction = left;
        } else if ( move_is_possible(right) ){
            move_direction = right;
        } else {
            move_direction = down;
        }
    }
    do_move(move_direction);
}

This is not a direct answer to OP's question, this is more of the stuffs (experiments) I tried so far to solve the same problem and obtained some results and have some observations that I want to share, I am curious if we can have some further insights from this.

I just tried my minimax implementation with alpha-beta pruning with search-tree depth cutoff at 3 and 5. I was trying to solve the same problem for a 4x4 grid as a project assignment for the edX course ColumbiaX: CSMM.101x Artificial Intelligence (AI) .

I applied convex combination (tried different heuristic weights) of couple of heuristic evaluation functions, mainly from intuition and from the ones discussed above:

  1. Monotonicity
  2. Free Space Available

In my case, the computer player is completely random, but still i assumed adversarial settings and implemented the AI player agent as the max player.

I have 4x4 grid for playing the game.

Observation:

If I assign too much weights to the first heuristic function or the second heuristic function, both the cases the scores the AI player gets are low. I played with many possible weight assignments to the heuristic functions and take a convex combination, but very rarely the AI player is able to score 2048. Most of the times it either stops at 1024 or 512.

I also tried the corner heuristic, but for some reason it makes the results worse, any intuition why?

Also, I tried to increase the search depth cut-off from 3 to 5 (I can't increase it more since searching that space exceeds allowed time even with pruning) and added one more heuristic that looks at the values of adjacent tiles and gives more points if they are merge-able, but still I am not able to get 2048.

I think it will be better to use Expectimax instead of minimax, but still I want to solve this problem with minimax only and obtain high scores such as 2048 or 4096. I am not sure whether I am missing anything.

Below animation shows the last few steps of the game played by the AI agent with the computer player:

Any insights will be really very helpful, thanks in advance. (This is the link of my blog post for the article: https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve-2048-game-with-computer/ )

The following animation shows the last few steps of the game played where the AI player agent could get 2048 scores, this time adding the absolute value heuristic too:

The following figures show the game tree explored by the player AI agent assuming the computer as adversary for just a single step:


I wrote a 2048 solver in Haskell, mainly because I'm learning this language right now.

My implementation of the game slightly differs from the actual game, in that a new tile is always a '2' (rather than 90% 2 and 10% 4). And that the new tile is not random, but always the first available one from the top left. This variant is also known as Det 2048 .

As a consequence, this solver is deterministic.

I used an exhaustive algorithm that favours empty tiles. It performs pretty quickly for depth 1-4, but on depth 5 it gets rather slow at a around 1 second per move.

Below is the code implementing the solving algorithm. The grid is represented as a 16-length array of Integers. And scoring is done simply by counting the number of empty squares.

bestMove :: Int -> [Int] -> Int
bestMove depth grid = maxTuple [ (gridValue depth (takeTurn x grid), x) | x <- [0..3], takeTurn x grid /= [] ]

gridValue :: Int -> [Int] -> Int
gridValue _ [] = -1
gridValue 0 grid = length $ filter (==0) grid  -- <= SCORING
gridValue depth grid = maxInList [ gridValue (depth-1) (takeTurn x grid) | x <- [0..3] ]

I thinks it's quite successful for its simplicity. The result it reaches when starting with an empty grid and solving at depth 5 is:

Move 4006
[2,64,16,4]
[16,4096,128,512]
[2048,64,1024,16]
[2,4,16,2]

Game Over

Source code can be found here: https://github.com/popovitsj/2048-haskell


This algorithm is not optimal for winning the game, but it is fairly optimal in terms of performance and amount of code needed:

  if(can move neither right, up or down)
    direction = left
  else
  {
    do
    {
      direction = random from (right, down, up)
    }
    while(can not move in "direction")
  }

संपादित करें: यह एक बेवकूफ एल्गोरिदम है, जो मानव जागरूक विचार प्रक्रिया का मॉडलिंग करता है, और एआई की तुलना में बहुत कमजोर परिणाम प्राप्त करता है जो सभी संभावनाओं को खोजता है क्योंकि यह केवल एक टाइल आगे दिखता है। यह प्रतिक्रिया समयरेखा में जल्दी जमा किया गया था।

मैंने एल्गोरिदम को परिष्कृत किया है और गेम को हराया है! यह अंत के करीब सरल दुर्भाग्य के कारण असफल हो सकता है (आपको नीचे जाने के लिए मजबूर होना पड़ता है, जिसे आपको कभी नहीं करना चाहिए, और एक टाइल दिखाई देती है जहां आपका सर्वोच्च होना चाहिए। बस शीर्ष पंक्ति को भरने की कोशिश करें, इसलिए बाईं ओर चलना नहीं है पैटर्न तोड़ें), लेकिन मूल रूप से आप एक निश्चित भाग और एक मोबाइल भाग के साथ खेलने के लिए समाप्त होता है। यह आपका उद्देश्य है:

यह वह मॉडल है जिसे मैंने डिफ़ॉल्ट रूप से चुना था।

1024 512 256 128
  8   16  32  64
  4   2   x   x
  x   x   x   x

चयनित कोने मनमाने ढंग से है, आप मूल रूप से एक कुंजी (वर्जित चाल) कभी नहीं दबाते हैं, और यदि आप करते हैं, तो आप इसके विपरीत फिर से दबाएं और इसे ठीक करने का प्रयास करें। भविष्य के टाइल्स के लिए मॉडल हमेशा अगले यादृच्छिक टाइल को 2 होने की उम्मीद करता है और वर्तमान मॉडल के विपरीत तरफ दिखाई देता है (जबकि पहली पंक्ति अधूरा है, निचले दाएं कोने पर, पहली पंक्ति पूरी होने के बाद, नीचे बाईं ओर कोने)।

यहां एल्गोरिदम चला जाता है। लगभग 80% जीत (ऐसा लगता है कि अधिक "पेशेवर" एआई तकनीकों के साथ जीतना हमेशा संभव है, हालांकि, मुझे इसके बारे में निश्चित नहीं है।)

initiateModel();

while(!game_over)
{    
    checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point

    for each 3 possible move:
        evaluateResult()
    execute move with best score
    if no move is available, execute forbidden move and undo, recalculateModel()
 }

 evaluateResult() {
     calculatesBestCurrentModel()
     calculates distance to chosen model
     stores result
 }

 calculateBestCurrentModel() {
      (according to the current highest tile acheived and their distribution)
  }

लापता चरणों पर कुछ पॉइंटर्स। यहाँ:

अपेक्षित मॉडल के करीब होने की किस्मत के कारण मॉडल बदल गया है। जिस मॉडल को एआई हासिल करने की कोशिश कर रहा है वह मॉडल है

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

और वहां जाने के लिए श्रृंखला बन गई है:

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

O वर्जित रिक्त स्थान का प्रतिनिधित्व करता है ...

तो यह दाएं फिर से दबाएगा, फिर दाएं, फिर (4 कहां बनाया गया है इसके आधार पर दाएं या ऊपर) फिर श्रृंखला प्राप्त करने तक आगे बढ़ेगा:

तो अब मॉडल और चेन वापस आ गए हैं:

 512 256 128  64
  4   8  16   32
  X   X   x   x
  x   x   x   x

दूसरा सूचक, इसमें दुर्भाग्य है और इसका मुख्य स्थान लिया गया है। ऐसा लगता है कि यह असफल हो जाएगा, लेकिन यह अभी भी इसे प्राप्त कर सकता है:

यहां मॉडल और श्रृंखला है:

  O 1024 512 256
  O   O   O  128
  8  16   32  64
  4   x   x   x

जब यह 128 तक पहुंचने का प्रबंधन करता है तो यह पूरी पंक्ति प्राप्त करता है:

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x

मैं इस खेल के लिए एआई के विचार में दिलचस्पी लेता हूं जिसमें कोई कठोर कोडित बुद्धि नहीं है (यानी कोई हेरिस्टिक, स्कोरिंग फ़ंक्शंस इत्यादि)। एआई को केवल खेल के नियमों को "जानना" चाहिए, और गेम खेलने के बारे में "पता लगाना" चाहिए । यह अधिकांश एआईएस (इस धागे में की तरह) के विपरीत है, जहां खेल का खेल अनिवार्य रूप से क्रूर बल है जो गेम की मानव समझ का प्रतिनिधित्व करने वाले स्कोरिंग फ़ंक्शन द्वारा संचालित होता है।

एआई एल्गोरिदम

मुझे एक सरल लेकिन आश्चर्यजनक रूप से अच्छा खेल एल्गोरिदम मिला: किसी दिए गए बोर्ड के लिए अगला कदम निर्धारित करने के लिए, एआई यादृच्छिक चाल का उपयोग करके खेल को अंत तक खेलती है । अंत स्कोर का ट्रैक रखते हुए यह कई बार किया जाता है। फिर प्रति प्रारंभिक चाल के औसत अंत स्कोर की गणना की जाती है। उच्चतम औसत स्कोर के साथ शुरुआती कदम अगले कदम के रूप में चुना जाता है।

प्रति कदम केवल 100 रनों का उपयोग करके एआई ने 2048 टाइल 80% बार और 4096 टाइल 50% बार प्राप्त किया। 10000 रनों का उपयोग 2048 टाइल 100%, 4096 टाइल के लिए 70%, और 8192 टाइल के लिए लगभग 1% हो जाता है।

इसे क्रिया में देखें

सबसे अच्छा हासिल स्कोर यहां दिखाया गया है:

इस एल्गोरिदम के बारे में एक दिलचस्प तथ्य यह है कि यादृच्छिक-खेल के खेल (असुरक्षित रूप से) काफी खराब होते हैं, सर्वोत्तम (या कम से कम खराब) चाल का चयन करना बहुत अच्छा गेम खेलने की ओर जाता है: एक सामान्य एआई गेम 70000 अंक तक पहुंच सकता है और पिछले 3000 कदमों तक पहुंच सकता है, फिर भी किसी दिए गए पद से यादृच्छिक-नाटक रन 340 अतिरिक्त अंक और मरने से पहले केवल 40 अतिरिक्त चाल उत्पन्न करता है। (आप एआई चलाने और डीबग कंसोल खोलकर इसे अपने लिए देख सकते हैं।)

यह ग्राफ इस बिंदु को दिखाता है: नीली रेखा प्रत्येक चाल के बाद बोर्ड स्कोर दिखाती है। लाल रेखा उस स्थिति से एल्गोरिदम का सबसे अच्छा यादृच्छिक-रन अंतिम स्कोर दिखाती है। संक्षेप में, लाल मान उनके प्रति नीले मानों को ऊपर खींच रहे हैं, क्योंकि वे एल्गोरिदम का सबसे अच्छा अनुमान हैं। यह देखना दिलचस्प है कि लाल रेखा प्रत्येक बिंदु पर नीली रेखा से थोड़ी सी छोटी है, फिर भी नीली रेखा अधिक से अधिक बढ़ती जा रही है।

मुझे यह आश्चर्य की बात है कि एल्गोरिदम को वास्तव में अच्छी गेम खेलने की आवश्यकता नहीं है ताकि इसे उत्पन्न करने वाली चालों को चुना जा सके।

बाद में खोजना मुझे पता चला कि इस एल्गोरिदम को शुद्ध मोंटे कार्लो ट्री सर्च एल्गोरिदम के रूप में वर्गीकृत किया जा सकता है।

कार्यान्वयन और लिंक

सबसे पहले मैंने एक जावास्क्रिप्ट संस्करण बनाया जो यहां कार्रवाई में देखा जा सकता है । यह संस्करण सभ्य समय में 100 रन चला सकता है। अतिरिक्त जानकारी के लिए कंसोल खोलें। ( source )

बाद में, कुछ और खेलने के लिए मैंने @nneonneo अत्यधिक अनुकूलित आधारभूत संरचना का उपयोग किया और सी ++ में अपना संस्करण लागू किया। यदि आपके पास धैर्य है तो यह संस्करण प्रति कदम 100000 रन और यहां तक ​​कि 1000000 तक की अनुमति देता है। प्रदान किए गए निर्देशों का निर्माण। यह कंसोल में चलता है और वेब संस्करण चलाने के लिए रिमोट कंट्रोल भी होता है। ( source )

परिणाम

हैरानी की बात है कि रनों की संख्या में वृद्धि से खेल खेलने में काफी सुधार नहीं होता है। 4096 टाइल और सभी छोटे छोटे, 8192 टाइल प्राप्त करने के बहुत करीब के साथ लगभग 80000 अंक पर इस रणनीति की सीमा प्रतीत होती है। 100 से 100000 तक रनों की संख्या में वृद्धि इस स्कोर सीमा (5% से 40% तक) प्राप्त करने की बाधाओं को बढ़ाती है लेकिन इसके माध्यम से नहीं तोड़ती है।

महत्वपूर्ण स्थिति के पास 1000000 तक अस्थायी वृद्धि के साथ 10000 रनों को चलाने से 12 9 8 9 और 8192 टाइल के अधिकतम स्कोर को प्राप्त करने के 1% से भी कम समय में इस बाधा को तोड़ने में कामयाब रहा।

सुधार

इस एल्गोरिदम को लागू करने के बाद मैंने न्यूनतम या अधिकतम स्कोर, या न्यूनतम, अधिकतम, और औसत का संयोजन सहित कई सुधारों की कोशिश की। मैंने गहराई का उपयोग करने की भी कोशिश की: प्रति चाल चलने की कोशिश करने के बजाय, मैंने किसी दिए गए लम्बाई (उदाहरण के लिए ऊपर, ऊपर, बाएं ") की चाल की चाल की कोशिश की और सर्वोत्तम स्कोरिंग चाल सूची के पहले चरण का चयन किया।

बाद में मैंने एक स्कोरिंग पेड़ लागू किया जिसने किसी दिए गए कदम सूची के बाद एक कदम चलाने में सक्षम होने की सशर्त संभावना को ध्यान में रखा।

हालांकि, इनमें से किसी भी विचार ने सरल पहले विचार पर कोई वास्तविक लाभ नहीं दिखाया। मैंने सी ++ कोड में इन विचारों के लिए कोड छोड़ दिया।

मैंने एक "दीप सर्च" तंत्र जोड़ा जो रन संख्या को अस्थायी रूप से 1000000 तक बढ़ा देता है जब कोई भी रन गलती से अगले उच्चतम टाइल तक पहुंचने में कामयाब रहा। इसने एक समय सुधार की पेशकश की।

मुझे यह जानने में दिलचस्पी होगी कि क्या किसी के पास अन्य सुधार विचार हैं जो एआई की डोमेन-आजादी को बनाए रखते हैं।

2048 प्रकार और क्लोन

बस मस्ती के लिए, मैंने एआई को एक बुकमार्लेट के रूप में भी लागू किया है , जो गेम के नियंत्रण में लगा हुआ है। यह एआई को मूल गेम और इसके कई रूपों के साथ काम करने की अनुमति देता है।

एआई की डोमेन-स्वतंत्र प्रकृति के कारण यह संभव है। कुछ प्रकार अलग-अलग हैं, जैसे हेक्सागोनल क्लोन।


Algorithm

while(!game_over)
{
    for each possible move:
        evaluate next state

    choose the maximum evaluation
}

Evaluation

Evaluation =
    128 (Constant)
    + (Number of Spaces x 128)
    + Sum of faces adjacent to a space { (1/face) x 4096 }
    + Sum of other faces { log(face) x 4 }
    + (Number of possible next moves x 256)
    + (Number of aligned values x 2)

Evaluation Details

128 (Constant)

This is a constant, used as a base-line and for other uses like testing.

+ (Number of Spaces x 128)

More spaces makes the state more flexible, we multiply by 128 (which is the median) since a grid filled with 128 faces is an optimal impossible state.

+ Sum of faces adjacent to a space { (1/face) x 4096 }

Here we evaluate faces that have the possibility to getting to merge, by evaluating them backwardly, tile 2 become of value 2048, while tile 2048 is evaluated 2.

+ Sum of other faces { log(face) x 4 }

In here we still need to check for stacked values, but in a lesser way that doesn't interrupt the flexibility parameters, so we have the sum of { x in [4,44] }.

+ (Number of possible next moves x 256)

A state is more flexible if it has more freedom of possible transitions.

+ (Number of aligned values x 2)

This is a simplified check of the possibility of having merges within that state, without making a look-ahead.

Note: The constants can be tweaked..


मैंने @ ovolve के एल्गोरिदम द्वारा उपयोग की जाने वाली मिनीमैक्स खोज के बजाय, उम्मीदवार अनुकूलन का उपयोग करके 2048 एआई विकसित किया। एआई बस सभी संभावित चालों पर अधिकतमता का प्रदर्शन करता है, इसके बाद सभी संभावित टाइल स्पॉन्स (टाइल्स की संभावना से भारित, यानी 4% के लिए 10% और 2% के लिए 9 0%) पर उम्मीद होती है। जहां तक ​​मुझे पता है, उम्मीदवार अनुकूलन को छूना संभव नहीं है (उन शाखाओं को हटाने के अलावा जो अत्यधिक संभावना नहीं हैं), और इसलिए उपयोग किए गए एल्गोरिदम एक सावधानी से अनुकूलित ब्रूट फोर्स सर्च है।

प्रदर्शन

बोर्ड की स्थिति की जटिलता के आधार पर, एआई इसकी डिफ़ॉल्ट कॉन्फ़िगरेशन (8 की अधिकतम खोज गहराई) में 10ms से 200ms तक ले जाती है। परीक्षण में, एआई पूरे गेम के दौरान प्रति सेकंड 5-10 चालों की औसत गति दर प्राप्त करता है। यदि खोज गहराई 6 चाल तक सीमित है, तो एआई प्रति सेकंड 20+ चाल आसानी से निष्पादित कर सकता है, जो कुछ दिलचस्प देखने के लिए बनाता है।

एआई के स्कोर प्रदर्शन का आकलन करने के लिए, मैंने एआई 100 बार भाग लिया (रिमोट कंट्रोल के माध्यम से ब्राउज़र गेम से जुड़ा हुआ)। प्रत्येक टाइल के लिए, यहां गेम के अनुपात हैं जिनमें उस टाइल को कम से कम एक बार हासिल किया गया था:

2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%

सभी रनों पर न्यूनतम स्कोर 124024 था; अधिकतम स्कोर 794076 था। औसत स्कोर 387222 है। एआई 2048 टाइल प्राप्त करने में कभी विफल नहीं हुआ (इसलिए यह 100 गेम में कभी भी गेम को कभी नहीं खो देता); वास्तव में, यह हर दौड़ में कम से कम एक बार 8192 टाइल हासिल किया!

सर्वश्रेष्ठ रन का स्क्रीनशॉट यहां दिया गया है:

इस गेम ने 96 मिनट में 27830 कदम उठाए, या औसत प्रति सेकंड 4.8 चालें लीं।

कार्यान्वयन

मेरा दृष्टिकोण पूरे बोर्ड (16 प्रविष्टियों) को एक 64-बिट पूर्णांक के रूप में एन्कोड करता है (जहां टाइल्स nybbles हैं, यानी 4-बिट भाग)। 64-बिट मशीन पर, यह पूरे बोर्ड को एक मशीन रजिस्टर में चारों ओर पारित करने में सक्षम बनाता है।

अलग-अलग पंक्तियों और स्तंभों को निकालने के लिए बिट शिफ्ट ऑपरेशंस का उपयोग किया जाता है। एक पंक्ति या स्तंभ 16-बिट मात्रा है, इसलिए आकार 65536 की एक तालिका एक पंक्ति या कॉलम पर चलने वाले परिवर्तनों को एन्कोड कर सकती है। उदाहरण के लिए, चाल को प्रीकंप्यूटेड "मूव इफेक्ट टेबल" में 4 लुकअप के रूप में कार्यान्वित किया जाता है जो वर्णन करता है कि प्रत्येक चाल एक पंक्ति या कॉलम को कैसे प्रभावित करती है (उदाहरण के लिए, "दाएं दाएं" तालिका में "1122 -> 0023" प्रविष्टि है जिसमें वर्णन किया गया है कि कैसे पंक्ति [2,2,4,4] दाएं स्थानांतरित होने पर पंक्ति [0,0,4,8] बन जाती है)।

टेबल लुकअप का उपयोग करके स्कोरिंग भी किया जाता है। सारणी में सभी संभावित पंक्तियों / स्तंभों पर गणना किए गए हेरिस्टिक स्कोर होते हैं, और बोर्ड के परिणामस्वरूप स्कोर प्रत्येक पंक्ति और कॉलम में तालिका मानों का योग होता है।

इस बोर्ड का प्रतिनिधित्व, आंदोलन और स्कोरिंग के लिए टेबल लुकअप दृष्टिकोण के साथ, एआई को थोड़े समय में खेल राज्यों की एक बड़ी संख्या में खोज करने की अनुमति देता है (मेरे मध्य -2013 लैपटॉप के एक कोर पर प्रति सेकंड 10,000,000 से अधिक गेम स्टेटस)।

उम्मीदवार खोज स्वयं को एक पुनरावर्ती खोज के रूप में कोडित किया जाता है जो "अपेक्षा" चरणों के बीच वैकल्पिक होता है (सभी संभावित टाइल स्पॉन स्थानों और मूल्यों का परीक्षण करता है, और प्रत्येक संभावना की संभावना से उनके अनुकूलित स्कोर को भारित करता है), और "अधिकतमकरण" चरण (सभी संभावित चालों का परीक्षण और सबसे अच्छे स्कोर के साथ एक का चयन)। पेड़ की खोज समाप्त होती है जब यह पूर्व-देखी गई स्थिति (एक पारदर्शी तालिका का उपयोग करके) को देखती है, जब यह पूर्वनिर्धारित गहराई सीमा तक पहुंच जाती है, या जब यह बोर्ड की स्थिति तक पहुंच जाती है जो अत्यधिक असंभव है (उदाहरण के लिए यह 6 "4" टाइल्स प्राप्त करके पहुंचा था शुरुआती स्थिति से एक पंक्ति में)। सामान्य खोज गहराई 4-8 चाल है।

heuristics

ऑप्टिमाइज़ेशन एल्गोरिदम को अनुकूल स्थितियों की ओर निर्देशित करने के लिए कई हेरिस्टिक्स का उपयोग किया जाता है। हेरिस्टिक की सटीक पसंद एल्गोरिदम के प्रदर्शन पर एक बड़ा प्रभाव डालती है। विभिन्न हेरिस्टिक को भारित किया जाता है और एक स्थितित्मक स्कोर में जोड़ा जाता है, जो निर्धारित करता है कि दी गई बोर्ड स्थिति "अच्छी" कैसे होती है। ऑप्टिमाइज़ेशन सर्च का लक्ष्य सभी संभावित बोर्ड पदों के औसत स्कोर को अधिकतम करना होगा। गेम द्वारा दिखाए गए वास्तविक स्कोर का उपयोग बोर्ड स्कोर की गणना करने के लिए नहीं किया जाता है, क्योंकि यह विलय विलय के पक्ष में बहुत अधिक भारित होता है (जब विलंब विलय से बड़ा लाभ हो सकता है)।

प्रारंभ में, मैंने दो बहुत ही सरल हेरिस्टिक का उपयोग किया, खुले वर्गों के लिए "बोनस" और किनारे पर बड़े मूल्य रखने के लिए। इन हेरिस्टिक्स ने बहुत अच्छी तरह से प्रदर्शन किया, अक्सर 16384 प्राप्त किया लेकिन 32768 तक कभी नहीं मिला।

पेट्र मोरावेक (@xificurk) ने मेरी एआई ली और दो नए हेरिस्टिक्स जोड़े। पहला हेरिस्टिक एक गैर-मोनोटोनिक पंक्तियों और स्तंभों के लिए जुर्माना था, जो रैंकों में वृद्धि के रूप में बढ़े थे, यह सुनिश्चित करना कि छोटी संख्याओं की गैर-मोनोटोनिक पंक्तियां स्कोर को दृढ़ता से प्रभावित न करें, लेकिन बड़ी संख्या में गैर-मोनोटोनिक पंक्तियों ने स्कोर को काफी नुकसान पहुंचाया। दूसरी ह्युरिस्टिक ने खुली जगहों के अलावा संभावित विलय (आसन्न बराबर मान) की संख्या की गणना की। इन दो हेरिस्टिक्स ने मोनोटोनिक बोर्डों (जो विलय करना आसान है) की तरफ एल्गोरिदम को धक्का दिया, और बोर्ड विलयों की ओर बहुत सारे विलय (इसे अधिक प्रभाव के लिए संभवतः विलय को संरेखित करने के लिए प्रोत्साहित किया)।

इसके अलावा, पेट्र ने "मेटा-ऑप्टिमाइज़ेशन" रणनीति ( CMA-ES नामक एल्गोरिदम का उपयोग करके) का उपयोग करके उदारवादी वजन को भी अनुकूलित किया, जहां वजन को उच्चतम संभव औसत स्कोर प्राप्त करने के लिए समायोजित किया गया।

इन परिवर्तनों का प्रभाव बेहद महत्वपूर्ण है। एल्गोरिदम समय के 90% से अधिक प्राप्त करने के लिए लगभग 13% 16384 टाइल प्राप्त करने से चला गया, और एल्गोरिदम ने समय के 1/3 से अधिक 32768 प्राप्त करना शुरू किया (जबकि पुराने हेरिस्टिक्स ने कभी 32768 टाइल का उत्पादन नहीं किया) ।

मेरा मानना ​​है कि हेरिस्टिक्स पर सुधार के लिए अभी भी जगह है। यह एल्गोरिदम निश्चित रूप से अभी तक "इष्टतम" नहीं है, लेकिन मुझे लगता है कि यह बहुत करीब हो रहा है।

कि एआई अपने खेल के एक तिहाई से अधिक 32768 टाइल प्राप्त करता है एक विशाल मील का पत्थर है; मुझे यह जानकर आश्चर्य होगा कि क्या किसी भी मानव खिलाड़ी ने आधिकारिक गेम (यानी savestates या पूर्ववत जैसे उपकरण का उपयोग किए बिना) 32768 हासिल किया है। मुझे लगता है कि 65536 टाइल पहुंच के भीतर है!

आप अपने लिए एआई की कोशिश कर सकते हैं। कोड https://github.com/nneonneo/2048-ai पर उपलब्ध है।


Many of the other answers use AI with computationally expensive searching of possible futures, heuristics, learning and the such. These are impressive and probably the correct way forward, but I wish to contribute another idea.

Model the sort of strategy that good players of the game use.

उदाहरण के लिए:

13 14 15 16
12 11 10  9
 5  6  7  8
 4  3  2  1

Read the squares in the order shown above until the next squares value is greater than the current one. This presents the problem of trying to merge another tile of the same value into this square.

To resolve this problem, their are 2 ways to move that aren't left or worse up and examining both possibilities may immediately reveal more problems, this forms a list of dependancies, each problem requiring another problem to be solved first. I think I have this chain or in some cases tree of dependancies internally when deciding my next move, particularly when stuck.

Tile needs merging with neighbour but is too small: Merge another neighbour with this one.

Larger tile in the way: Increase the value of a smaller surrounding tile.

आदि...

The whole approach will likely be more complicated than this but not much more complicated. It could be this mechanical in feel lacking scores, weights, neurones and deep searches of possibilities. The tree of possibilities rairly even needs to be big enough to need any branching at all.


मेरा प्रयास उपरोक्त अन्य समाधानों की तरह उम्मीदवार का उपयोग करता है, लेकिन बिना बिटबोर्ड के। Nneonneo का समाधान 10 मिलियन चालों की जांच कर सकता है जो कि 6 टाइल्स के साथ 4 की गहराई है और 4 चाल संभव है (2 * 6 * 4) 4 । मेरे मामले में, इस गहराई को एक्सप्लोर करने में बहुत लंबा समय लगता है, मैं फ्री टाइल्स की संख्या के अनुसार उम्मीदवार खोज की गहराई को समायोजित करता हूं:

depth = free > 7 ? 1 : (free > 4 ? 2 : 3)

बोर्डों के स्कोर की गणना मुफ्त टाइल्स की संख्या के वर्ग के भारित योग और 2 डी ग्रिड के डॉट उत्पाद के साथ की जाती है:

[[10,8,7,6.5],
 [.5,.7,1,3],
 [-.5,-1.5,-1.8,-2],
 [-3.8,-3.7,-3.5,-3]]

जो ऊपरी बाएं टाइल से सांप के प्रकार में अवरोही से टाइल व्यवस्थित करने के लिए मजबूर करता है।

नीचे कोड या jsbin :

  
var n = 4,
	M = new MatrixTransform(n);

var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles

var snake= [[10,8,7,6.5],
            [.5,.7,1,3],
            [-.5,-1.5,-1.8,-2],
            [-3.8,-3.7,-3.5,-3]]
snake=snake.map(function(a){return a.map(Math.exp)})

initialize(ai)

function run(ai) {
	var p;
	while ((p = predict(ai)) != null) {
		move(p, ai);
	}
	//console.log(ai.grid , maxValue(ai.grid))
	ai.maxValue = maxValue(ai.grid)
	console.log(ai)
}

function initialize(ai) {
	ai.grid = [];
	for (var i = 0; i < n; i++) {
		ai.grid[i] = []
		for (var j = 0; j < n; j++) {
			ai.grid[i][j] = 0;
		}
	}
	rand(ai.grid)
	rand(ai.grid)
	ai.steps = 0;
}

function move(p, ai) { //0:up, 1:right, 2:down, 3:left
	var newgrid = mv(p, ai.grid);
	if (!equal(newgrid, ai.grid)) {
		//console.log(stats(newgrid, ai.grid))
		ai.grid = newgrid;
		try {
			rand(ai.grid)
			ai.steps++;
		} catch (e) {
			console.log('no room', e)
		}
	}
}

function predict(ai) {
	var free = freeCells(ai.grid);
	ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3);
	var root = {path: [],prob: 1,grid: ai.grid,children: []};
	var x = expandMove(root, ai)
	//console.log("number of leaves", x)
	//console.log("number of leaves2", countLeaves(root))
	if (!root.children.length) return null
	var values = root.children.map(expectimax);
	var mx = max(values);
	return root.children[mx[1]].path[0]

}

function countLeaves(node) {
	var x = 0;
	if (!node.children.length) return 1;
	for (var n of node.children)
		x += countLeaves(n);
	return x;
}

function expectimax(node) {
	if (!node.children.length) {
		return node.score
	} else {
		var values = node.children.map(expectimax);
		if (node.prob) { //we are at a max node
			return Math.max.apply(null, values)
		} else { // we are at a random node
			var avg = 0;
			for (var i = 0; i < values.length; i++)
				avg += node.children[i].prob * values[i]
			return avg / (values.length / 2)
		}
	}
}

function expandRandom(node, ai) {
	var x = 0;
	for (var i = 0; i < node.grid.length; i++)
		for (var j = 0; j < node.grid.length; j++)
			if (!node.grid[i][j]) {
				var grid2 = M.copy(node.grid),
					grid4 = M.copy(node.grid);
				grid2[i][j] = 2;
				grid4[i][j] = 4;
				var child2 = {grid: grid2,prob: .9,path: node.path,children: []};
				var child4 = {grid: grid4,prob: .1,path: node.path,children: []}
				node.children.push(child2)
				node.children.push(child4)
				x += expandMove(child2, ai)
				x += expandMove(child4, ai)
			}
	return x;
}

function expandMove(node, ai) { // node={grid,path,score}
	var isLeaf = true,
		x = 0;
	if (node.path.length < ai.depth) {
		for (var move of[0, 1, 2, 3]) {
			var grid = mv(move, node.grid);
			if (!equal(grid, node.grid)) {
				isLeaf = false;
				var child = {grid: grid,path: node.path.concat([move]),children: []}
				node.children.push(child)
				x += expandRandom(child, ai)
			}
		}
	}
	if (isLeaf) node.score = dot(ai.weights, stats(node.grid))
	return isLeaf ? 1 : x;
}



var cells = []
var table = document.querySelector("table");
for (var i = 0; i < n; i++) {
	var tr = document.createElement("tr");
	cells[i] = [];
	for (var j = 0; j < n; j++) {
		cells[i][j] = document.createElement("td");
		tr.appendChild(cells[i][j])
	}
	table.appendChild(tr);
}

function updateUI(ai) {
	cells.forEach(function(a, i) {
		a.forEach(function(el, j) {
			el.innerHTML = ai.grid[i][j] || ''
		})
	});
}
updateUI(ai)

function runAI() {
	var p = predict(ai);
	if (p != null && ai.running) {
		move(p, ai)
		updateUI(ai)
		requestAnimationFrame(runAI)
	}
}
runai.onclick = function() {
	if (!ai.running) {
		this.innerHTML = 'stop AI';
		ai.running = true;
		runAI();
	} else {
		this.innerHTML = 'run AI';
		ai.running = false;
	}
}


hint.onclick = function() {
	hintvalue.innerHTML = ['up', 'right', 'down', 'left'][predict(ai)]
}
document.addEventListener("keydown", function(event) {
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai)
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai)
}


function stats(grid, previousGrid) {

	var free = freeCells(grid);

	var c = dot2(grid, snake);

	return [c, free * free];
}

function dist2(a, b) { //squared 2D distance
	return Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2)
}

function dot(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		r += a[i] * b[i];
	return r
}

function dot2(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		for (var j = 0; j < a[0].length; j++)
			r += a[i][j] * b[i][j]
	return r;
}

function product(a) {
	return a.reduce(function(v, x) {
		return v * x
	}, 1)
}

function maxValue(grid) {
	return Math.max.apply(null, grid.map(function(a) {
		return Math.max.apply(null, a)
	}));
}

function freeCells(grid) {
	return grid.reduce(function(v, a) {
		return v + a.reduce(function(t, x) {
			return t + (x == 0)
		}, 0)
	}, 0)
}

function max(arr) { // return [value, index] of the max
	var m = [-Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] > m[0]) m = [arr[i], i];
	}
	return m
}

function min(arr) { // return [value, index] of the min
	var m = [Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] < m[0]) m = [arr[i], i];
	}
	return m
}

function maxScore(nodes) {
	var min = {
		score: -Infinity,
		path: []
	};
	for (var node of nodes) {
		if (node.score > min.score) min = node;
	}
	return min;
}


function mv(k, grid) {
	var tgrid = M.itransform(k, grid);
	for (var i = 0; i < tgrid.length; i++) {
		var a = tgrid[i];
		for (var j = 0, jj = 0; j < a.length; j++)
			if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j]
		for (; jj < a.length; jj++)
			a[jj] = 0;
	}
	return M.transform(k, tgrid);
}

function rand(grid) {
	var r = Math.floor(Math.random() * freeCells(grid)),
		_r = 0;
	for (var i = 0; i < grid.length; i++) {
		for (var j = 0; j < grid.length; j++) {
			if (!grid[i][j]) {
				if (_r == r) {
					grid[i][j] = Math.random() < .9 ? 2 : 4
				}
				_r++;
			}
		}
	}
}

function equal(grid1, grid2) {
	for (var i = 0; i < grid1.length; i++)
		for (var j = 0; j < grid1.length; j++)
			if (grid1[i][j] != grid2[i][j]) return false;
	return true;
}

function conv44valid(a, b) {
	var r = 0;
	for (var i = 0; i < 4; i++)
		for (var j = 0; j < 4; j++)
			r += a[i][j] * b[3 - i][3 - j]
	return r
}

function MatrixTransform(n) {
	var g = [],
		ig = [];
	for (var i = 0; i < n; i++) {
		g[i] = [];
		ig[i] = [];
		for (var j = 0; j < n; j++) {
			g[i][j] = [[j, i],[i, n-1-j],[j, n-1-i],[i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left]
			ig[i][j] = [[j, i],[i, n-1-j],[n-1-j, i],[i, j]]; // the inverse tranformations
		}
	}
	this.transform = function(k, grid) {
		return this.transformer(k, grid, g)
	}
	this.itransform = function(k, grid) { // inverse transform
		return this.transformer(k, grid, ig)
	}
	this.transformer = function(k, grid, mat) {
		var newgrid = [];
		for (var i = 0; i < grid.length; i++) {
			newgrid[i] = [];
			for (var j = 0; j < grid.length; j++)
				newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]];
		}
		return newgrid;
	}
	this.copy = function(grid) {
		return this.transform(3, grid)
	}
}
body {
	text-align: center
}
table, th, td {
    border: 1px solid black;
    margin: 5px auto;
}
td {
    width: 35px;
    height: 35px;
    text-align: center;
}
<table></table>
<button id=init>init</button><button id=runai>run AI</button><button id=hint>hint</button><span id=hintvalue></span>


मैं यहां अपने ब्लॉग पर एक पोस्ट की सामग्री कॉपी करता हूं

मैं प्रस्तावित समाधान बहुत सरल और कार्यान्वित करने में आसान है। हालांकि, यह 131040 के स्कोर तक पहुंच गया है। एल्गोरिदम प्रदर्शन के कई मानक प्रस्तुत किए गए हैं।

कलन विधि

ह्युरिस्टिक स्कोरिंग एल्गोरिदम

जिस धारणा पर मेरा एल्गोरिदम आधारित है, वह सरल है: यदि आप उच्च स्कोर प्राप्त करना चाहते हैं, तो बोर्ड को जितना संभव हो उतना साफ रखा जाना चाहिए। विशेष रूप से, इष्टतम सेटअप टाइल मानों के रैखिक और monotonic घटते क्रम द्वारा दिया जाता है। यह अंतर्ज्ञान आपको टाइल मान के लिए ऊपरी बाउंड भी देगा: जहां एन बोर्ड पर टाइल की संख्या है।

(आवश्यकता होने पर 2-टाइल के बजाय 4-टाइल यादृच्छिक रूप से जेनरेट होने पर 131072 टाइल तक पहुंचने की संभावना है)

बोर्ड को व्यवस्थित करने के दो संभावित तरीके निम्नलिखित छवियों में दिखाए जाते हैं:

एक monotonic घटते क्रम में टाइल्स के समन्वय को लागू करने के लिए, स्कोर अनुपात लाइन के रैखिक मूल्यों के योग के रूप में गणना की गई है जो सामान्य अनुपात आर <1 के साथ एक ज्यामितीय अनुक्रम के मानों से गुणा किया जाता है।

कई रैखिक पथ का मूल्यांकन एक बार में किया जा सकता है, अंतिम स्कोर किसी भी पथ का अधिकतम स्कोर होगा।

निर्णय नियम

लागू निर्णय नियम काफी स्मार्ट नहीं है, पाइथन में कोड यहां प्रस्तुत किया गया है:

@staticmethod
def nextMove(board,recursion_depth=3):
    m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
    return m

@staticmethod
def nextMoveRecur(board,depth,maxDepth,base=0.9):
    bestScore = -1.
    bestMove = 0
    for m in range(1,5):
        if(board.validMove(m)):
            newBoard = copy.deepcopy(board)
            newBoard.move(m,add_tile=True)

            score = AI.evaluate(newBoard)
            if depth != 0:
                my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)
                score += my_s*pow(base,maxDepth-depth+1)

            if(score > bestScore):
                bestMove = m
                bestScore = score
    return (bestMove,bestScore);

Minmax या Expectiminimax का एक कार्यान्वयन निश्चित रूप से एल्गोरिदम में सुधार होगा। जाहिर है कि एक अधिक परिष्कृत निर्णय नियम एल्गोरिदम को धीमा कर देगा और इसे लागू करने के लिए कुछ समय की आवश्यकता होगी। मैं निकट भविष्य में एक मिनीमैक्स कार्यान्वयन का प्रयास करूंगा। (बने रहें)

बेंचमार्क

  • टी 1 - 121 परीक्षण - 8 अलग-अलग पथ - आर = 0.125
  • टी 2 - 122 परीक्षण - 8-अलग पथ - आर = 0.25
  • टी 3 - 132 परीक्षण - 8-अलग पथ - आर = 0.5
  • टी 4 - 211 परीक्षण - 2-अलग पथ - आर = 0.125
  • टी 5 - 274 परीक्षण - 2-अलग पथ - आर = 0.25
  • टी 6 - 211 परीक्षण - 2-अलग पथ - आर = 0.5

टी 2 के मामले में, दस में चार परीक्षण औसत स्कोर के साथ 4096 टाइल उत्पन्न करते हैं 42000

कोड

कोड निम्न लिंक पर GiHub पर पाया जा सकता है: https://github.com/Nicola17/term2048-AI यह term2048 पर आधारित है और यह पायथन में लिखा गया है। मैं जितनी जल्दी हो सके सी ++ में एक और अधिक कुशल संस्करण लागू करेगा।





2048