दिलचस्प पोस्ट
पायथन मेटप्ललिब में एक्स-अक्ष और y- अक्ष के तराजू को कैसे समतल करना है? NetBeans में .jar फ़ाइलों का उपयोग कैसे करें? कैसे एक वस्तु है कि BufferedImages शामिल serialize करने के लिए अंतर्निहित नाम बदलने के बजाय पर्ल नाम बदलें उपयोगिता प्राप्त करें नियम इंजन को कैसे कार्यान्वित करें? मानचित्र () मिल () भ्रम वादा / स्थगित पुस्तकालय कैसे लागू होता है? Google Translate TTS एपीआई अवरुद्ध जावास्क्रिप्ट में स्ट्रिंग में स्ट्रिंग को कैसे परिवर्तित करें? UINavigationBar पृष्ठभूमि छवि बदलना एक्शनबार पाठ रंग डायरेविन / ओएसएक्स में कार्यक्रम की जानकारी निर्धारित करें यूटीएफ -8 को बीओएम से यूटीएफ -8 में परिवर्तित करें, जिसमें पायमॉन में कोई बीओएम नहीं है * एनजीएन्सर 2 में अनंत लूप चलाने के लिए Base64 यूआरएल सुरक्षित एन्कोडिंग सी # में कैसे प्राप्त करें?

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

मैंने हाल ही में खेल 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 अंक से थोड़ा अधिक है जो कि मेरे वर्तमान स्कोर से बड़ा है। क्या उपरोक्त से बेहतर एल्गोरिदम है?

Solutions Collecting From Web of "खेल 2048 के लिए इष्टतम एल्गोरिदम क्या है?"

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

प्रदर्शन

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

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

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

सभी रनों पर न्यूनतम स्कोर 124024 था; प्राप्त अधिकतम स्कोर 794076 था। औसत स्कोर 387222 है। ऐ कभी 2048 टाइल प्राप्त करने में नाकाम रही थी (इसलिए उसने कभी भी 100 खेलों में एक बार खेल नहीं खोया); वास्तव में, उसने प्रत्येक रन में कम से कम एक बार 8192 टाइल हासिल की!

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

32768 टाइल, स्कोर 794076

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

कार्यान्वयन

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

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

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

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

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

heuristics

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

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

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

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

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

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


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

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

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

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

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

दिष्टता

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

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

एक पूरी तरह से मोनोटोनिक 2048 बोर्ड

चिकनाई

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

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

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

एक बिल्कुल चिकनी 2048 बोर्ड

नि: शुल्क टाइलें

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

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

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

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

4096

हां, यह 20 9 8 के साथ 40 9 0 है। =) इसका मतलब है कि उसने एक ही बोर्ड पर मायावी 2048 टाइल को तीन बार हासिल किया।

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

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

समाप्त करने के लिए तैयार

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

 1024 512 256 128 8 16 32 64 4 2 xx xxxx 

चुना कोने मनमानी है, आप मूल रूप से एक कुंजी (निषिद्ध चाल) को कभी नहीं दबाते हैं, और यदि आप करते हैं, तो आप इसके विपरीत फिर से दबाएं और उसे ठीक करने का प्रयास करें। भविष्य की टाइलों के लिए मॉडल हमेशा अगले यादृच्छिक टाइल को 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 XX xx XX xx xxxx 

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

  512 256 64 O 8 16 32 O 4 xxx xxxx 

O प्रतिबंधित स्थान का प्रतिनिधित्व करता है …

तो यह सही दबाएगा, फिर दाएं फिर, फिर (सही या शीर्ष 4 के आधार पर जहां पर निर्भर करता है) तब तक चैन को पूरा करने तक आगे बढ़ेगा जब तक यह नहीं हो जाता है:

चेन ने पूरा किया

तो अब मॉडल और श्रृंखला वापस आ जाती है:

  512 256 128 64 4 8 16 32 XX xx xxxx 

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

यहां छवि विवरण दर्ज करें

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

  O 1024 512 256 OOO 128 8 16 32 64 4 xxx 

जब यह 128 तक पहुंचने में सफल होता है, तो उसे एक पूर्ण पंक्ति प्राप्त होती है:

  O 1024 512 256 xx 128 128 xxxx xxxx 

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

ए एल्गोरिदम

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

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

इसे कार्रवाई में देखें

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

सर्वश्रेष्ठ अंक

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

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

स्कोरिंग ग्राफ़

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

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

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

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

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

परिणाम

हैरानी की बात है कि, रनों की संख्या में तेजी लाने के खेल खेल में तेजी से सुधार नहीं करता है। इस रणनीति की सीमा करीब 40,000 टाइल और 8,192 टाइल को प्राप्त करने के करीब करीब 40,000 टाइल वाले 80000 अंकों के साथ एक सीमा होती है। 100 से 100000 तक की संख्या में बढ़ोतरी इस स्कोर सीमा (5% से 40%) तक पहुंचने की बाधाओं को बढ़ाती है लेकिन इसके माध्यम से तोड़ नहीं रही है

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

सुधार

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

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

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

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

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

2048 वेरिएंट और क्लोन

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

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

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


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

स्कोर

कलन विधि

अनुमानी स्कोरिंग एल्गोरिथम

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

(13-1072 टाइल तक पहुंचने की संभावना है यदि 4-टाइल बेतरतीब ढंग से 2-टाइल के बजाय जेनरेट की जाती है)

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

यहां छवि विवरण दर्ज करें

एक मोनोटोनिक घटते क्रम में टाइल्स के समन्वयन को लागू करने के लिए, स्कोर सी को रैखिक मानों के योग के रूप में गणना की जाती है, जो एक समान अनुपात के साथ एक ज्यामितीय अनुक्रम के मूल्यों से गुणा करता है r <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); 

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

बेंचमार्क

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

यहां छवि विवरण दर्ज करेंयहां छवि विवरण दर्ज करेंयहां छवि विवरण दर्ज करेंयहां छवि विवरण दर्ज करें

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

कोड

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

मेरा प्रयास ऊपर दूसरों के समाधान की तरह उम्मीदवार का उपयोग करता है, लेकिन बिना बिटबोर्ड के न्ननेनो का समाधान 10 मीलियन की चालों की जांच कर सकता है, जो लगभग 4 की गहराई है, जिसमें 6 टाइल शेष हैं और 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> 

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); } 

I am the author of a 2048 controller that scores better than any other program mentioned in this thread. An efficient implementation of the controller is available on github . In a separate repo there is also the code used for training the controller's state evaluation function. The training method is described in the paper .

The controller uses expectimax search with a state evaluation function learned from scratch (without human 2048 expertise) by a variant of temporal difference learning (a reinforcement learning technique). The state-value function uses an n-tuple network , which is basically a weighted linear function of patterns observed on the board. It involved more than 1 billion weights , in total.

प्रदर्शन

At 1 moves/s: 609104 (100 games average)

At 10 moves/s: 589355 (300 games average)

At 3-ply (ca. 1500 moves/s): 511759 (1000 games average)

The tile statistics for 10 moves/s are as follows:

 2048: 100% 4096: 100% 8192: 100% 16384: 97% 32768: 64% 32768,16384,8192,4096: 10% 

(The last line means having the given tiles at the same time on the board).

For 3-ply:

 2048: 100% 4096: 100% 8192: 100% 16384: 96% 32768: 54% 32768,16384,8192,4096: 8% 

However, I have never observed it obtaining the 65536 tile.

There is already an AI implementation for this game: here . Excerpt from README:

The algorithm is iterative deepening depth first alpha-beta search. The evaluation function tries to keep the rows and columns monotonic (either all decreasing or increasing) while minimizing the number of tiles on the grid.

There is also a discussion on ycombinator about this algorithm that you may find useful.

कलन विधि

 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..

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 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 4×4 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 4×4 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:

यहां छवि विवरण दर्ज करें यहां छवि विवरण दर्ज करें यहां छवि विवरण दर्ज करें यहां छवि विवरण दर्ज करें यहां छवि विवरण दर्ज करें यहां छवि विवरण दर्ज करें

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") } 

Many of the other answers use AI with computationally expensive searching of possible futures, or are a sort of artificial mind that can learn, and the such, these are very 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 the current one, then try to merge another tile of the same value into this square.

To resolve this problem their are 2 ways to move that arn't left or worse up and examining both possibilities may emmidatly 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 sometimes 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 aproach will likely be complicated than this, and even as I write it seems to contain too much hidden issues behind implementing every part of the strategy, but could perhaps be this mechanical in feel, without scores, weights, neurones and deep searches of possibilities.