मैंने कैसे डरना बंद कर दिया और एक गेम बॉट लिखा

या आपके तंत्रिका नेटवर्क के बिना अच्छी पुरानी गतिशील प्रोग्रामिंग।

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


कोडेनजॉय प्रोजेक्ट सर्वर से गेम स्क्रीन

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

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

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

खेल से सभी उदाहरण एक सरलीकृत प्रदर्शन में दिए जाएंगे, जिसका उपयोग कार्यक्रम लॉग में किया गया था:

सिद्धांत की बिट

कुछ प्रकार के गणित का उपयोग करके बॉट को लागू करने के लिए, हमें कुछ उद्देश्य फ़ंक्शन सेट करना होगा जो बॉट की उपलब्धियों का वर्णन करता है और उसे अधिकतम करने वाली क्रियाएं ढूंढता है। उदाहरण के लिए, सोना इकट्ठा करने के लिए हमें +100 मिलते हैं, मृत्यु -100500 के लिए, इसलिए सोने का कोई भी संग्रह संभावित मौत को नहीं मारेगा।

एक अलग प्रश्न, और वास्तव में हम उद्देश्य फ़ंक्शन को क्या निर्धारित करते हैं, अर्थात्। खेल की स्थिति क्या है? सबसे सरल मामले में, खिलाड़ी के निर्देशांक पर्याप्त हैं, लेकिन हमारे यहां सब कुछ बहुत अधिक जटिल है:

• खिलाड़ी के निर्देशांक
• सभी खिलाड़ियों द्वारा छेद किए गए सभी छेदों के निर्देशांक
• मानचित्र पर सभी सोने के निर्देशांक (या हाल ही में खाए गए सोने के निर्देशांक)
• अन्य सभी खिलाड़ियों के निर्देशांक

यह डरावना लगता है। इसलिए, आइए कार्य को थोड़ा सरल करें और जब तक हम अपने द्वारा खाए गए सोने को याद नहीं कर लेते हैं (हम बाद में इस पर लौट आएंगे), हमें अन्य खिलाड़ियों और राक्षसों के निर्देशांक भी याद नहीं होंगे।

इस प्रकार, खेल की वर्तमान स्थिति है:

• खिलाड़ी के निर्देशांक
• सभी गड्ढों के निर्देशांक

खिलाड़ी की गतिविधियाँ समझ में आने वाली स्थिति को बदल देती हैं:

• गति निर्देश संगत निर्देशांक में से एक को बदलते हैं
• गड्ढे खोदने वाली टीम एक नया गड्ढा जोड़ती है
• किसी सहारे के बिना खिलाड़ी को गिराना ऊर्ध्वाधर समन्वय को कम करता है
• समर्थन पर खड़े खिलाड़ी की निष्क्रियता राज्य को नहीं बदलती है

अब हमें यह समझने की आवश्यकता है कि फ़ंक्शन को अधिकतम कैसे करें। खेल एन की गणना के लिए आदरणीय क्लासिक विधियों में से एक है गतिशील प्रोग्रामिंग। सूत्रों के बिना ऐसा करना असंभव है, इसलिए मैं उन्हें एक सरलीकृत रूप में दूंगा। आपको पहले बहुत सारे संकेतन पेश करने होंगे।

सादगी के लिए, हम वर्तमान रिपोर्ट से समय रिपोर्ट रखेंगे, अर्थात्। वर्तमान चाल t = 0 है।
हम टी के दौरान खेल की स्थिति को निरूपित करते हैं$$$x^t$।
बहुत सारा$$ बॉट के सभी वैध कार्यों को निरूपित करेगा (एक विशिष्ट स्थिति में, लेकिन सादगी के लिए हम राज्य सूचकांक नहीं लिखेंगे), के माध्यम से $$हम पाठ्यक्रम टी पर एक विशिष्ट कार्रवाई को दर्शाते हैं (हम सूचकांक को छोड़ देते हैं)।
स्थिति$$$x^t$ प्रभाव में $$राज्य में जाता है $$$x^{t+1}_a$।

जीत जब कार्रवाई राज्य में है$$$x^t$ हम इसे निरूपित करते हैं $$$P(x^t, x^{t+1}_a)$। इसकी गणना करते समय, हम मानते हैं कि अगर हमने सोना खाया, तो यह G = 100 के बराबर है, यदि वे मर गए, तो D = -100500, अन्यथा 0.

लेट$$$F(x^t)$यह बॉट के इष्टतम खेल के लिए पेऑफ फ़ंक्शन है जो समय टी में राज्य x में है। फिर हमें केवल एक क्रिया खोजने की आवश्यकता है जो अधिकतम हो$$$F(x^0)$।

अब हम पहला सूत्र लिखते हैं, जो बहुत महत्वपूर्ण है और एक ही समय में लगभग सही है:

$$

$$F(x^0) = \max_{a \in A} F(x^1_a) + P(x^0, x^1_a)$$

या समय में एक मनमाना बिंदु के लिए

$$

$$F(x^t) = \max_{a \in A} F(x^{t+1}_a) + P(x^t, x^{t+1}_a)$$

यह बहुत ही भद्दा लगता है, लेकिन अर्थ सरल है - वर्तमान चाल के लिए इष्टतम समाधान में अगले कदम के लिए इष्टतम समाधान और वर्तमान चाल में लाभ शामिल हैं। यह बेलमैन का कुटिल रूप से निर्मित इष्टतम सिद्धांत है। हमें चरण 1 में इष्टतम मानों के बारे में कुछ भी पता नहीं है, लेकिन अगर हम उन्हें जानते थे, तो हम एक ऐसी कार्रवाई पाएंगे जो कि बॉट की सभी क्रियाओं पर ध्यान केंद्रित करके फ़ंक्शन को अधिकतम करती है। पुनरावृत्ति संबंधों की सुंदरता यह है कि हम पा सकते हैं$$$F(x^1)$इसके माध्यम से इष्टतम सिद्धांत को लागू करना, इसे उसी सूत्र में व्यक्त करना $$$F(x^2)$। हम किसी भी कदम पर आसानी से भुगतान समारोह को व्यक्त कर सकते हैं।

ऐसा लगता है कि समस्या हल हो गई है, लेकिन यहां हम इस समस्या का सामना कर रहे हैं कि यदि प्रत्येक चरण में हमें 6 खिलाड़ी क्रियाओं के माध्यम से छंटनी होती है, तो पुनरावर्तन के एन चरण में हमें 6 ^ एन विकल्पों के माध्यम से छंटनी होगी, जो कि N = 8 के लिए पहले से ही एक बहुत ही सभ्य संख्या है ~ 1.6 लाख मामले। दूसरी ओर, हमारे पास गीगाहर्ट्ज़ माइक्रोप्रोसेसर हैं जिनके पास करने के लिए कुछ नहीं है, और ऐसा लगता है कि वे पूरी तरह से कार्य के साथ सामना करेंगे, और हम खोज की गहराई को ठीक 8 चालों तक सीमित कर देंगे।

और इसलिए, हमारी योजना क्षितिज 8 चाल है, लेकिन मूल्यों को कहां प्राप्त करना है$$$F(x^9)$? और यहाँ हम सिर्फ इस विचार के साथ आते हैं कि हम किसी भी तरह से स्थिति की संभावनाओं का विश्लेषण करने में सक्षम हैं, और इसे अपने उच्चतम विचारों के आधार पर कुछ मूल्य प्रदान करते हैं। रहने दो$$$F(x^9)=S(x^9)$कहाँ पे $$$S(x)$यह रणनीति का एक कार्य है, सरलतम संस्करण में यह सिर्फ एक मैट्रिक्स है जिसमें से हम बॉट के ज्यामितीय निर्देशांक के अनुसार मूल्य का चयन करते हैं। हम कह सकते हैं कि पहले 8 चालों में यह एक रणनीति थी, और फिर रणनीति शुरू होती है। वास्तव में, कोई भी हमें एक रणनीति चुनने में प्रतिबंधित नहीं करता है, और हम बाद में इससे निपटेंगे, लेकिन अभी के लिए, हर्ष और हेजल के बारे में मजाक से उल्लू की तरह नहीं बनने के लिए, हम रणनीति पर आगे बढ़ेंगे।

सामान्य योजना

और इसलिए, हमने एल्गोरिथ्म पर फैसला किया। प्रत्येक चरण में, हम अनुकूलन समस्या को हल करते हैं, चरण के लिए इष्टतम कार्रवाई खोजें, इसे पूरा करें, जिसके बाद खेल अगले चरण पर आगे बढ़ता है।

हर कदम पर एक नई समस्या को हल करना आवश्यक है, क्योंकि खेल के प्रत्येक पाठ्यक्रम के साथ कार्य थोड़ा बदल जाता है, नया सोना दिखाई देता है, कोई व्यक्ति किसी को खाता है, खिलाड़ी चलते हैं ...
लेकिन यह मत सोचो कि हमारा सरल एल्गोरिथ्म सब कुछ प्रदान कर सकता है। अनुकूलन समस्या को हल करने के बाद, आपको निश्चित रूप से एक हैंडलर जोड़ना होगा जो अप्रिय स्थितियों की जांच करेगा:

• लंबे समय तक बॉट खड़े रहना
• लगातार बाएं-दाएं चलना
• आय का अभाव बहुत लंबा है

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



आपके प्रतिद्वंद्वी प्रतिष्ठित सोने के लिए अपनी छोटी सड़क को फ्रीज और बंद कर सकते हैं - हम बाद में इस सब से निपटेंगे।

शिथिलता के खिलाफ लड़ाई

साधारण मामले पर विचार करें जब एक सोना बॉट के दाईं ओर स्थित है और 8 के त्रिज्या में अधिक सोने की कोशिकाएं नहीं हैं। हमारे सूत्र द्वारा निर्देशित बॉट क्या कदम उठाएगा? वास्तव में - बिल्कुल किसी भी। उदाहरण के लिए, ये सभी समाधान तीन चालों के लिए भी समान परिणाम देते हैं:

• स्टेप लेफ्ट - स्टेप राइट - स्टेप राइट
• दाईं ओर कदम - निष्क्रियता - निष्क्रियता
• निष्क्रियता - निष्क्रियता - सही कदम

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

$$

$$F(x^0) = \max_{a \in A} F(x^1_a)*E + P(x^0, x^1_a)$$

हमने "मुद्रास्फीति गुणांक" ई द्वारा अगले चरण में भविष्य के लाभ को गुणा किया है, जिसे 1. से कम चुना जाना चाहिए। हम सुरक्षित रूप से 0.95 या 0.9 के मान के साथ प्रयोग कर सकते हैं। लेकिन इसे बहुत छोटा न चुनें, उदाहरण के लिए, E = 0.5 के मान के साथ, 8 वीं चाल पर खाया गया सोना केवल 339 अंक लाएगा।

और इसलिए, हमने "कल तक मत डालो जो आज तुम खा सकते हो" के सिद्धांत को फिर से खोज लिया।

सुरक्षा

सोना इकट्ठा करना निश्चित रूप से अच्छा है, लेकिन आपको अभी भी सुरक्षा के बारे में सोचने की जरूरत है। हमारे पास दो कार्य हैं:

• यदि राक्षस उपयुक्त स्थिति में है तो छेद खोदने के लिए बॉट को सिखाएं
• राक्षसों से दूर भागने के लिए बॉट सिखाओ

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

यदि वे हमसे संपर्क करना शुरू करते हैं, तो बॉट खुद उनसे दूर भागना शुरू कर देगा, क्योंकि यह उनके बहुत करीब होने (आत्म-अलगाव की तरह) के लिए जुर्माना होगा। और इसलिए, हम दो नियम पेश करते हैं:

• यदि हम d और d <= 3 की दूरी पर राक्षस के पास आते हैं, तो हम पर 100,500 * (4-d) / 4 का जुर्माना लगाया जाता है
• यदि राक्षस काफी करीब आ गया, हमारे साथ एक ही पंक्ति पर है और हमारे बीच एक छेद है, तो हमें कुछ लाभ मिलता है पी

"द डिस्टेंस एट द मॉन्स्टर एट ए डिस्टेंस डी" हम थोड़ी देर बाद खुलेंगे, लेकिन अभी के लिए, रणनीति पर आगे बढ़ते हैं।

हम रेखांकन के आसपास जाते हैं

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



पहले चरण में, हम उन सभी कोशिकाओं का चयन करते हैं जिनसे हम एक चाल में सोने में उतर सकते हैं और उन्हें १ को असाइन कर सकते हैं। दूसरे चरण में, हम उन सभी कक्षों का चयन करते हैं, जहाँ से हम एक चरण में आते हैं और उन्हें २ को असाइन करते हैं। चित्र ३ चरणों के लिए मामले को दर्शाता है। अब आइए इसे सभी को औपचारिक रूप से लिखने की कोशिश करें, प्रोग्रामिंग के लिए उपयुक्त रूप में।

हमें आवश्यकता होगी:

• दो-आयामी संख्यात्मक सरणी दूरी [x, y], जिसमें हम परिणाम को संग्रहीत करेंगे। प्रारंभ में, सोने के निर्देशांक के लिए, इसमें 0 होते हैं, शेष अंक -1 के लिए।
• OldBorder सरणी, जिसमें हम उन बिंदुओं को संग्रहीत करेंगे, जिनसे हम आगे बढ़ेंगे, शुरू में इसमें सोने के निर्देशांक के साथ एक बिंदु होगा
• नयाबॉर्डर को व्यवस्थित करें, जिसमें हम वर्तमान चरण में पाए गए बिंदुओं को संग्रहीत करेंगे

1. पुराने बिंदु से प्रत्येक बिंदु p के लिए हमें सभी बिंदु p_a मिलते हैं जिनसे हम एक चरण में p तक पहुँच सकते हैं (अधिक सटीक रूप से, हम बस विपरीत दिशा में p से सभी संभव कदम उठाते हैं, उदाहरण के लिए, समर्थन के अभाव में ऊपर की ओर उड़ना) और दूरी [p_a] = - 1
2. हम सरणी newBorder में प्रत्येक ऐसे बिंदु p_a को रखते हैं, दूरी पर [p_a] हम पुनरावृति संख्या लिखते हैं
3. सभी बिंदुओं के पूरा होने के बाद:
4. OldBorder और newBorder के सरणियों को स्वैप करें, जिसके बाद हम newBorder को साफ़ करते हैं
5. यदि पुराना बॉर्डर खाली है, तो एल्गोरिथ्म को समाप्त करें, अन्यथा चरण 1 पर जाएं।

छद्म कोड में एक ही बात:

iter=1;
newBorder.clear();
distance.fill(-1);
distance[gold]=0;
oldBorder.push(gold);

while(oldBorder.isNotEmpty()) {
  for (p: oldBorder){
    for (p_a: backMove(p)) {
      if (distance[p_a]==-1) {
         newBorder.push(p_a);
         distance[p_a]=iter;
      }
    }
  }
  Swap(newBorder, oldBorder);
  newBorder.clear();
  iter++;
}

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

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

मैंने संख्याओं के साथ चित्र को पूरक किया, जिसमें एक छेद खोदना और इसमें कूदना शामिल है: यह



हमें क्या याद दिलाता है?



सोने की गंध! और हमारे बॉट इस गंध के लिए जाएंगे, जैसे कि रॉकी फॉर पनीर (लेकिन साथ ही यह अपने दिमाग को नहीं खोता है और राक्षसों को चकमा देता है, और यहां तक ​​कि उनके लिए छेद भी खोदता है)। चलो उसे एक सरल लालची रणनीति बनाते हैं:

1. प्रत्येक स्वर्ण के लिए, हम एक दूरी के नक्शे का निर्माण करते हैं और खिलाड़ी से दूरी पाते हैं।
2. खिलाड़ी के लिए निकटतम सोने का चयन करें और रणनीति की गणना करने के लिए उसका कार्ड लें
3. मानचित्र के प्रत्येक सेल के लिए, सोने के लिए इसकी दूरी, फिर सामरिक मूल्य से निरूपित करें
   

   $$

   $$S(x) = \begin{cases} 0 & \text{ $d < 0$,}\\ G_s E_s^d & \text{ $d \geq0$ } \end{cases}$$

कहाँ पे $$$G_s$यह सोने का कुछ काल्पनिक मूल्य है, यह वांछनीय है कि इसे वर्तमान की तुलना में कई गुना कम मूल्य दिया जाए, और $$$E_s$यह एक मुद्रास्फीति गुणांक <1 है, क्योंकि काल्पनिक सोना जितना अधिक है, उतना ही सस्ता है। गुणांक E और के अनुपात$$$E_s$सहस्राब्दी की एक अनसुलझी समस्या का गठन और रचनात्मकता के लिए कमरा छोड़ देता है।

ऐसा मत सोचो कि हमारा बॉट हमेशा निकटतम सोने तक चलेगा। मान लें कि हमारे पास 5 कोशिकाओं की दूरी पर बाईं ओर एक सोना है और फिर शून्य है, और 6 और 7 की दूरी पर दाहिने दो सोने पर चूँकि असली सोना कल्पना से अधिक मूल्यवान है, बॉट दाईं ओर जाएगा।

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

जटिल रणनीतियाँ

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

हालांकि, एक नया समाधान नई समस्याएं पैदा करता है - एक नए मूल्य मैट्रिक्स में स्थानीय मैक्सिमा हो सकती है, जिसके पास कोई सोना नहीं है। क्योंकि हमारा बॉट उनमें घुस सकता है और बाहर नहीं जाना चाहता है, इसका मतलब है कि हमें एक हैंडलर जोड़ने की जरूरत है जो यह जांच करे कि बॉट रणनीति के स्थानीय अधिकतम स्तर पर है और इस कदम के परिणामों के अनुसार बना हुआ है। और अब हमारे पास फ्रीज़ से निपटने के लिए एक उपकरण है - एन चालों द्वारा इस रणनीति को रद्द करें और अस्थायी रूप से निकटतम सोने की रणनीति पर वापस लौटें।

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

रणनीति रणनीति से असहमत है

यहां हमारा बॉट फर्श के नीचे सोने के लिए आता है:



यह पहले से ही अनुकूलन एल्गोरिथ्म में आता है, यह दाईं ओर 3 कदम उठाने के लिए रहता है, दाईं ओर एक छेद काटकर इसमें कूद जाता है, और फिर गुरुत्वाकर्षण खुद से सब कुछ करेगा। कुछ इस तरह:



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

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

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

$$

$$p_{new}(x^0,x^1_a) = p(x^0,x^1_a) + (S(x^1_a) – S(x^0)).$$

उत्तरार्द्ध पर उद्देश्य समारोह का मूल्य आम तौर पर शून्य हो जाता है: $$$F(x^9) =0$। चूँकि प्रत्येक गुणांक को गुणांक से गुणा करके लाभ को ह्रास किया जाता है, इससे हमारे बॉट को तेजी से रणनीतिक लाभ मिलेगा और देखी गई समस्या को समाप्त किया जा सकता है।

अनकही रणनीति

मैंने अभ्यास में इस रणनीति का परीक्षण नहीं किया है, लेकिन यह आशाजनक लग रहा है।

1. चूँकि हम सोने के बिंदुओं और सोने और खिलाड़ी के बीच की दूरियों के बीच की सभी दूरियों को जानते हैं, इसलिए हम सबसे कम लंबाई वाली सोने की कोशिकाओं (जहाँ N छोटा है, उदाहरण के लिए 5 या 6) के खिलाड़ी-एन श्रृंखला पा सकते हैं। यहां तक ​​कि समय की सबसे सरल खोज काफी है।
2. इस श्रृंखला में पहले सोने का चयन करें और एक रणनीति मैट्रिक्स के रूप में इसके मूल्य क्षेत्र का उपयोग करें।

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

अंतिम सुधार

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

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

कार्यान्वयन सुविधाएँ

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

स्रोत कोड और गेम सर्वर

स्रोत कोड यहाँ github पर पाया जा सकता है । सख्ती से न्याय न करें, बहुत जल्दबाजी में किया गया है। कोडेनजॉय गेम सर्वर बॉट लॉन्च करने और गेम की निगरानी के लिए बुनियादी ढांचा प्रदान करेगा । निर्माण के समय, संशोधन प्रासंगिक था, संशोधन 1.0.26 का उपयोग किया गया था।

आप निम्न लाइन के साथ सर्वर शुरू कर सकते हैं:

call mvn -DMAVEN_OPTS=-Xmx1024m -Dmaven.test.skip=true clean jetty:run-war -Dcontext=another-context -Ploderunner

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

निष्कर्ष

यदि आपने प्रारंभिक तैयारी के बिना अंत तक यह सब पढ़ा है और सब कुछ समझा है, तो आप एक दुर्लभ साथी हैं।