गणित और खेल 2048

पहली बार खेल 2048 को यहां हब्रहाब पर प्रस्तुत किया गया था। पांच दिनों से भी कम समय में, उन्होंने इसके पारित होने के लिए एक सरल रणनीति का रहस्य उजागर किया। यह वास्तव में सरल है - आपको टाइल्स से एक साँप बनाने की जरूरत है (चित्र में)।



हालांकि, एक समझा जाने वाला लक्ष्य हमेशा अपनी आसान उपलब्धि का मतलब नहीं होता है। Mrrl और मैंने उत्तराधिकार में अपनी सफलताओं को साझा किया: उन्होंने 8, 16, 32 और 65 हजार के ब्लाकों को अंधा कर दिया। अब मैंने वह काम किया जिसकी मुझे खुद से उम्मीद नहीं थी - खेल में अधिकतम संभव टाइल एकत्र करने के लिए - 131 072 या 2 ¹⁷ , 2 मिलियन जमा करना। अंक।



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

- क्या 2 ¹⁷ वास्तव में अधिकतम संभव ब्लॉक है?

- खेल के अपरिहार्य अंत के रास्ते पर आप कितने अंक सिद्धांत रूप में स्कोर कर सकते हैं?

- पहेली कितनी चाल चलती है?



यह पता लगाने के लिए थोड़ा गणित लगता है ...

अधिकतम संभव टाइल

ब्लॉक 2 ¹⁷ के निर्माण के लिए एक सांप के साथ तस्वीर को देखते हुए, यह स्पष्ट है कि इस विशेष रणनीति का उपयोग करके एक बड़ी टाइल को इकट्ठा करना संभव नहीं होगा। हालांकि, क्या यह निष्कर्ष सही है कि 131,072 वास्तव में अधिकतम है? अंतर्ज्ञान हमें उत्तर बताता है कि हां, लेकिन मैं अधिक ठोस तर्क देना चाहूंगा। और अध्ययन का यह हिस्सा मेरे लिए सबसे कठिन निकला। कई दृष्टिकोणों ने एक मृत अंत तक नेतृत्व किया, आखिरकार, मैं अगले डिजाइन पर आया।



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



तस्वीर के रूप में मामले में, राज्य एक सेट (4, 4, 8, 16, ..., 65536) होगा। और खेल की शुरुआत में यह हो सकता है, उदाहरण के लिए, एक वेक्टर (0, 0, ..., 0, 2, 2)। प्रत्येक चाल (मानव और मशीन दोनों) एक नए राज्य की ओर ले जाती है, जो, हालांकि, मनमाना नहीं हो सकता है। तो, खेल के नियम आपको एक बार में (0, ..., 0, 2, 2, 8) से (0, ..., 0, 4, 16) कूदने की अनुमति नहीं देते हैं।



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

- किसी व्यक्ति के पाठ्यक्रम में - या तो कुछ भी नहीं बदलता है, या समान संख्याओं के एक या एक से अधिक जोड़े एक जोड़ी में तत्वों के योग द्वारा प्रतिस्थापित किए जाते हैं, फिर शून्य की आवश्यक संख्या जोड़ी जाती है और वेक्टर का आदेश दिया जाता है;

- कार के पाठ्यक्रम में - या तो एक ड्यूस या एक चार सेट में जोड़ा जाता है (ताकि ऑर्डर को परेशान न करें), और एक शून्य हटा दिया जाता है, या (यदि राज्य में शून्य नहीं हैं), तो खिलाड़ी हार जाता है।

प्रारंभिक अवस्था (अर्थात, पहेली की शुरुआत में स्थिति) (0, ..., 0, 2, 2), (0, ..., 0, 2, 4) या (0, ..., 0, 4, 4) हो सकती है। आदमी और कार बारी में जाते हैं, खिलाड़ी पहले शुरू होता है।



इन नियमों को 2048 गेम मॉडल का स्वयंसिद्ध माना जा सकता है। जैसा कि अपेक्षित था, यह एक मॉडलिंग ऑब्जेक्ट की तुलना में सरल है, लेकिन इसमें महत्वपूर्ण गुण हैं:

- यदि मूल पहेली में आप एक टाइल बना सकते हैं, उदाहरण के लिए, 2 ¹⁷ , तो नए में भी;

- और इसके विपरीत, यदि एक सरलीकृत खेल में 2 नंबर ^{18 के} साथ राज्य में जाना असंभव है, तो इस तरह के ब्लॉक की मूल रचना में असंभव है।



इस प्रकार, प्रश्न का उत्तर देने के लिए "क्या 131 072 वास्तव में अधिकतम संभव टाइल है?", यह साबित होता है कि मॉडल में 2 नंबर ^{18 के} साथ एक राज्य में स्विच करना संभव नहीं होगा।



प्रमाण: इसके विपरीत मानें और प्रारंभिक 2 से राज्यों की एक श्रृंखला पर विचार करें जब नंबर 2 ¹⁸ पहली बार दिखाई दिया। मॉडल के स्वयंसिद्धों के आधार पर, अंतिम वेक्टर केवल एक व्यक्ति को फॉर्म की स्थिति में ले जाने के बाद दिखाई दे सकता है (..., 2 ¹⁷ , 2 ¹⁷ )।



हमारी श्रृंखला में सामने आई पहली ऐसी स्थिति पर विचार करें। यह पहले (फिर से स्वीकृत स्वयंसिद्धों के अनुसार) या तो (..., 2 ¹⁶ , 2 ¹⁶ , 2 ¹⁷ ) या (..., 2 ¹⁶ , 2 ¹⁶ , 2 ¹⁶ , 2 ¹⁶ ) था, और पाठ्यक्रम की बारी व्यक्ति के लिए है।



बदले में इसका मतलब है कि पहले खिलाड़ी को एक स्थिति में होना था: (..., 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁶ , 2 ¹⁷ ), (..., 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁷ ), (..., 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁶ , 2 ¹⁶ , 2 ¹⁶ ), (..., 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁶ , 2 ¹⁶ ), (..., 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁶ ) या (..., 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ , 2 ¹⁵ )।



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



इस तरह के तर्क के प्रत्येक बाद के चरण में श्रृंखला में उपस्थित होने के लिए आवश्यक वेक्टर के कड़ाई से निर्दिष्ट घटकों की संख्या की कम से कम एक इकाई की वृद्धि होती है। इस मामले में, निश्चित मानों का सबसे छोटा हिस्सा आधा है।



परिणामस्वरूप, 15 से अधिक चरणों में, सभी 16 घटकों को स्पष्ट रूप से परिभाषित किया जाएगा। फिर हम इस निष्कर्ष पर पहुंचेंगे कि श्रृंखला में फॉर्म (2 ^k , ...) की स्थिति होनी चाहिए, जहां k person 3, और एक व्यक्ति चल रहा है।



हालांकि, खिलाड़ी ऐसी स्थिति में नहीं हो सकता है, क्योंकि मशीन की कार्रवाई के बाद वेक्टर में दर्शाए गए सबसे छोटे नंबर केवल 0, 2 या 4 हो सकते हैं। हम एक विरोधाभास पर आए, जो इसके विपरीत हमारी प्रारंभिक धारणा का खंडन करता है, जिससे यह साबित होता है कि क्या आवश्यक है।



नतीजतन, 2 ¹⁷ वास्तव में 2048 के खेल में अधिकतम संभव टाइल है । इसका मतलब यह भी है कि एक पहेली को पारित करना सीमित संख्या में अंकों के साथ कुछ निश्चित संख्या में चालों से अधिक नहीं हो सकता है। मुझे आश्चर्य है कि हमारे निपटान में कितने बिंदु और कार्य हैं?

अधिकतम अंक

मेरे लिए स्कोरिंग बहुत आसान थी। शुरू करने के लिए, हम 2048 में सर्वश्रेष्ठ खिलाड़ी के लिए प्रयास कर सकते हैं। अंकों के आधार पर एक चैंपियन का गोल गोल (और इस तरह से भी, चालें) वेक्टर (2, 8, 16, 32, ..., 131 072) या () द्वारा वर्णित स्थिति है। 4, 8, 16, 32, ..., 131 072)। इस मामले में, खेल समाप्त हो जाता है, जबकि किसी अन्य राज्य को संकेतित लोगों द्वारा "हावी" किया जाता है, अर्थात, अतिरिक्त अंक प्राप्त करके (अतिरिक्त कार्यों को पूरा करके) इसे निश्चित रूप से बेहतर किया जा सकता है।



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



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



हम एफ (2) = 4. अगला:

f (3) = 16 (हम दो आवश्यक ब्लॉकों में से प्रत्येक 4 के लिए 4 अंक प्राप्त करेंगे, फिर 8 में उनके संयोजन के लिए एक और 8),

f (4) = 48 (= 16 + 16 + 16),

f (5) = 128 (= 48 + 48 + 32), आदि।



पुनरावृत्ति संबंध इस प्रकार है: f ( n ) = 2 f ( n - 1 ) + 2 ⁿ सभी धनात्मक पूर्णांकों के लिए n , 3, n। 16. इसे हल करने का एक तरीका यह है कि समानता पर विचार किया जाए f ( n ) = 2 (2 f - n) 2 ) + 2 ^{एन - 1} ) + 2 ^एन = 4 एफ ( एन - 2 ) + 2 * 2 ^एन , एफ ( एन ) = 4 (2 एफ ( एन - 3 ) + 2 ^{एन - 2} ) + 2 * 2 ^एन = 2 ³ एफ ( एन - 3 ) + 3 * 2 ^एन , ..., एफ ( एन ) = 2 ^{एन - 2} एफ ( 2 ) + ( एन - 2) * 2 ^एन । F (2) = 4 को देखते हुए, हम f ( n ) = 2 ⁿ ( n - 1) प्राप्त करते हैं, जो कि 3 for n । 16 के लिए सही, रीकॉल है।



टाइल 2 ^{17 को} इकट्ठा करने पर हमें फॉर्मूले से 4 अंक कम मिलेंगे, क्योंकि हम मशीन द्वारा हमें प्रस्तुत किए गए चार में से एक का उपयोग करने के लिए मजबूर होंगे। अर्थात, f (17) = 2 ¹⁷ * 16 - 4 या 2 097 148।



यह केवल यह समझने के लिए बना हुआ है कि अधिकतम ब्लॉक बनाने के बाद, हमें पहली बार 2 ¹⁶ टाइल "इकट्ठा" करना है, च (16) प्राप्त करना है - इसके लिए 4 अंक (जुर्माना फिर से चार का उपयोग करने के लिए है), फिर 2 ¹⁵ , परिचर एफ (15) प्राप्त करना ) - 4 अंक, और इतने पर 2 ³ और f (3) - गुल्लक में 4 अंक।



राशि च (17) + एफ (16) - 4 + एफ (15) - 4 + ... + एफ (3) - 4 की गणना करते हुए, हमें 3 932 100 मिलते हैं, जो कि खेल 2048 में अंकों की अधिकतम संभव संख्या है ।



एक छोटी टिप्पणी: परिभाषा के अनुसार, f ( n ) उस समय तक अर्जित की गई सबसे छोटी संभव संख्या है जो टाइल 2 ⁿ पहली बार मैदान पर दिखाई देती है। हालांकि, अंतिम गेम में, अर्जित अंकों की संख्या 3 से 17 के लिए कार्यों के मूल्यों के योग के बराबर है (शून्य से जुर्माना)। इसमें कोई अतिशयोक्ति नहीं है, क्योंकि इन्हें छोटे ब्लॉकों के संदर्भ में ध्यान में रखा जाता है।

खिलाड़ी की अधिकतम संभव संख्या चलती है

चालों की संख्या का कार्य मुझे सबसे कठिन लगता था। लेकिन तर्क काफी सरल है: हम फ़ंक्शन जी ( एन ) का परिचय देते हैं, कुछ हद तक एफ के समान है। इसका मान ब्लॉक 2 ^एन को इकट्ठा करने के लिए आवश्यक टाइल 2 की न्यूनतम संख्या के रूप में परिभाषित किया गया है। चालों की संख्या को अधिकतम करने के लिए, हम इस धारणा पर भी काम करते हैं कि मशीन हर बार (15 विशेष मामलों के अपवाद के साथ) हमें ड्यूस देती है।



तो, जी (2) = 2 (चार को इकट्ठा करने के लिए आपको 2 डोज़ मर्ज करने की आवश्यकता है), जी (3) = 4 (आठ को इकट्ठा करने के लिए आपको दो चौकों को मर्ज करने की ज़रूरत है, जिनमें से प्रत्येक को 2 डोज़ की आवश्यकता है), जी (4) (8) = 4 + 4) और इसी तरह। साधारण पुनरावृत्ति संबंध g ( n ) = 2 g ( n - 1) सूत्र g ( n ) = 2 ^{n - 1} को 3 for n । 16 के लिए देता है।



ब्लॉक 2 ¹⁷ बनाते समय ^, हमें ऊपर बताई गई अभिव्यक्ति की तुलना में दो कम 2 टाइलों की आवश्यकता होती है, क्योंकि वे हमें तुरंत एक चार देते हैं, हमें इसे इकट्ठा करने की आवश्यकता नहीं है। इसलिए, जी (17) = 2 ¹⁶ - 2 = 65 534. उसी तरह से जैसे अंक के मामले में, दो अंतिम राज्यों में से एक के लिए रास्ते में शामिल टवीस की कुल संख्या की गणना करने के लिए, फ़ंक्शन जी ( n ) के मानों को n से जोड़ें। 3 से 17 तक जुर्माना सहित। हमें जी (17) + जी (16) - 2 + ... + जी (3) - 2, 131 038 के बराबर मिलता है। पूर्ण आदेश के लिए, हमें इस संख्या में एक जोड़ने की आवश्यकता है यदि हम अंतिम स्थिति (2, 8, 16,) तक पहुंचते हैं ..., 131 072)।



अब वापस अपने काम पर। दो टाइलें 2 हमें शुरू से ही दी गई हैं। शेष 131,036 (फाइनल में अंतिम में से एक की गिनती नहीं) प्राप्त करने के लिए, आपको उचित संख्या में क्रियाएं करनी चाहिए (आखिरकार, प्रत्येक मशीन हमें एक दो देता है)। साथ ही, आपको एक और 15 चौके (अंतिम में से एक में भी गिनती नहीं) की आवश्यकता है। और अंत में, एक और कार्रवाई अंतिम दो या चार की उपस्थिति को जन्म देगी।



कुल, पेरफोर्स, 131,036 + 15 + 1 = 131,052 कीस्ट्रोक्स (या टच स्क्रीन पर टच) करना होगा - यह गेम 2048 में उपयोगकर्ता की वांछित अधिकतम संख्या है ।

खेल में मेरी वर्तमान उपलब्धियों का विश्लेषण 2048

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



इसलिए, पहले से परीक्षण किए गए तर्क के बाद, अगर केवल दो और एक चार मेरे लिए पूरा खेल गिर गया, तो जी (16) + जी (15) + ... + जी (2) + 1 - 2 = 65,533 चालों के परिणामस्वरूप मुझे डायल करना पड़ा बिंदु f (16) + f (15) + f (14) + ... + f (2) = 1 835 012 अंक। हालाँकि, जैसा कि आप देख सकते हैं, केवल 1,811,320 अर्जित किया गया था। 23 692 की कमी है, अर्थात्, कार ने मुझे 5,923 चौके दिए, जिससे अंक प्राप्त करना असंभव हो गया, लेकिन इसी क्रम की चाल को सहेजना।



निष्कर्ष:

- आज तक, मैंने खेल 2048 में पूरी जीत के रास्ते पर लगभग 60 हजार सही कार्रवाई की है;

- दो अपरिहार्य फाइनल में से एक तक अभी भी लगभग 71 हजार कीस्ट्रोक्स (एक आदर्श खेल और भाग्य के साथ) हैं;

- मेरे द्वारा प्राप्त अंकों की कुल संख्या (अधिकतम टाइल और उसके बगल में चार-हजारवें ब्लॉक को इकट्ठा करने के बाद) 2,117,800 है, यानी अधिकतम संभव का 54%। आधे से ज्यादा! यहां तक ​​कि यादृच्छिक संख्या जनरेटर के कारण लगभग 24 हजार अंकों की अपूरणीय क्षति को ध्यान में रखते हुए।



अगर अचानक मैं खिलौना को अंत तक खत्म कर देता हूं - मैं इस पोस्ट में तस्वीर पोस्ट करूंगा। सभी को अच्छा मूड!



युपीडी:

वाक्यांश गेम ओवर, जो स्क्रीन शॉट के तुरंत बाद दिखाई दिया, मुझे लगता है कि इस मामले में पूरी तरह से उपयुक्त नहीं है। दरअसल, दो संभावित अंतिम राज्यों में से एक के रास्ते पर, विजय ब्लॉक 2048 को 127 बार एकत्र किया जाना था। कुल 119 322 सही चाल चली गई। मशीन ने मैदान पर 11 730 चौके फेंके (ऊपरी बाएं कोने में अंतिम नहीं), जिसने जीत को तेज किया, लेकिन 46 920 अंक खो दिए।