एआई चैलेंज: चींटियों एआई चैलेंज: चींटियों को एनिमेट करना

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

1. एआई चैलेंज में भाग लेने का कुछ अनुभव

एआई चैलेंज के बारे में अन्य विषयों पर टिप्पणियों को देखते हुए, कई लोगों के पास "स्थानीय" रेटिंग प्रणाली के बारे में सवाल हैं। वास्तव में टिप्पणियाँ।

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

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

प्रति कदम एल्गोरिथ्म के निष्पादन समय को सीमित करना: 500 एमएस, और टर्नटाइम पैरामीटर के साथ भिन्न हो सकते हैं। हालांकि, इस थ्रेशोल्ड से कम से कम 50 एमएस द्वारा एल्गोरिथ्म के निष्पादन को तेजी से पूरा करना बेहद वांछनीय है, अन्यथा I / O बफरिंग (सभी गेम डेटा पाइप के माध्यम से प्रेषित होता है), और कभी-कभी मजाकिया बातें बाहर आने के कारण बहुत समय लगने की संभावना है:



मेमोरी सीमा 2GB (एक 32 बिट प्लेटफॉर्म की सीमा) है, यह 1.5GB मेमोरी के बारे में गारंटी दी जाती है ("वादा" के रूप में पढ़ने की अधिक संभावना है), जो स्वैप फ़ाइल द्वारा फैल नहीं होगी। यह एक काफी बड़ी संख्या है (200 से 200 कोशिकाओं के कार्ड के लिए - वह), जो आपको सीधे मध्यवर्ती परिणामों को कैश करने के लिए प्रोत्साहित करती है, जो हम वस्तुओं को पथ खोजने के लिए एक अच्छा एल्गोरिदम प्राप्त करने के लिए करेंगे।

2. पथ खोजने के लिए एल्गोरिथ्म

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

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

यदि मानचित्र में "जल" (गहरे नीले रंग की कोशिकाएं) के अभेद्य खंड नहीं थे, तो कार्य तुच्छ होगा; "चींटी" और "पानी" को जोड़ने वाली लाल रेखा पर विचार करें। क्योंकि चूंकि एक चींटी चार दिशाओं में केवल एक पिंजरे में चल सकती है, वस्तु की दूरी (बाधाओं को छोड़कर) मैनहट्टन दूरी के साथ मेल खाती है। यदि हम सही दिशा में वेतन वृद्धि का उपयोग करते हैं, तो ऑब्जेक्ट का पथ हमेशा समान संख्या में कोशिकाओं पर कब्जा करेगा। लक्ष्य के निर्देशांक (X1, y1) से निर्देशांक (x0, y0) के निर्देशांक से घटाएं और X में वृद्धि के साथ चरणों की संख्या (- X1-x0 |) प्राप्त करें: साइन इन करें (X1-x0) और संख्या (Y- y1-y0।) Y में: संकेत (y1-y0) लक्ष्य के लिए अग्रणी।

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

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

यह बहुत है या थोड़ा है? हमारे मामले में, | cols |; पंक्तियों | <= 200, आप सभी को 1000 चींटियों के लिए दिशा-निर्देश प्राप्त करने की आवश्यकता है (वास्तविक गेम में कभी अधिक नहीं हैं), और प्रत्येक में सैकड़ों संभावित लक्ष्य हो सकते हैं। कुल मिलाकर 200 ^ 2 * 1000 * 100, यह 4 बिलियन पुनरावृत्तियों है, जिनमें से अधिकांश मेमोरी में लिखे गए हैं। सामान्य ज्ञान हमें बताता है कि 500ms पर यह फिट नहीं है।

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

हम क्या याद करेंगे? प्रत्येक लक्ष्य सेल के लिए तरंग एल्गोरिदम के पूरे मैट्रिक्स:

char * WaveMaps[MAX_X][MAX_Y]; //
WaveMaps[x][y] = new char [MAX_X*MAX_Y]; //

मुझे आपको याद दिलाना है कि WaveMaps [x] [y] को निर्देशांक (x, y) के साथ लक्ष्य वस्तु के लिए माना जाता है; वास्तव में, ये सभी इस वस्तु के लिए संभव मार्ग हैं। इस प्रकार, यह स्पष्ट है कि पानी वाली कोशिकाएं लक्ष्य नहीं होंगी (उनमें कोई समझदारी नहीं है, और आप बस नहीं जा सकते हैं), और अधिकांश कोशिकाएं जो किसी भी चीज (भोजन, चींटियों, एंथिल्स) से भरी नहीं हैं, हमारे लिए दिलचस्प नहीं हैं - उन्हें आरंभीकृत नहीं किया जाएगा।

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

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

सबसे पहले, पता करें कि "पानी" का पता कैसे लगाया जाए। ऐसा करने के लिए, यह क्षेत्र की स्थिति की एक स्थानीय प्रतिलिपि को संग्रहीत करने के लिए पर्याप्त है, और प्रत्येक नए कदम पर यह जांचने के लिए कि क्या प्राप्त गेम राज्य और सहेजे गए के बीच अंतर है या नहीं। ठीक है, हमने पानी को स्थिति में पाया (X1, y1)। फिर आपको उन सभी कार्डों को फिर से लिखने की जरूरत है जिसमें स्थिति (X1, y1) का मान चरण संख्या (और डिफ़ॉल्ट मान नहीं) से भरा है।

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

इस प्रकार, एक उचित विचार वस्तुओं की पुनरावृत्ति का एक पदानुक्रमित नक्शा रखना होगा। मेरे कार्यान्वयन के मामले में, केवल दो स्तर पर्याप्त थे (सबसे उचित मामले में सभी चींटियों के लिए सभी मार्गों की योजना के लिए 100ms)।

फिर उपरोक्त एल्गोरिथ्म को निम्नानुसार संशोधित किया गया है:
1. तरंग एल्गोरिथ्म के प्रत्येक कार्ड को भरते समय, हम जांचते हैं कि प्रारंभिक बिंदु से प्रारंभिक बिंदु की दूरी MAP_RANGE से अधिक है (यदि अधिक, हम बाहर निकलते हैं);
2. कम-रिज़ॉल्यूशन फ़ील्ड (MAX_X / SCALE, MAX_Y / SCALE) के लिए एक पूर्ण तरंग मानचित्र बनाएँ। ऐसा नक्शा MAP_RANGE से अधिक दूरी के साथ बिंदुओं के बीच का रास्ता खोजने में मदद करेगा।


पर्याप्त रूप से दूर के बिंदुओं (X1, y1) और (x0, y0) के लिए एक मार्ग का अनुरोध करते समय, हम पहले एक कम-रिज़ॉल्यूशन मानचित्र को देखते हैं, एक मध्यवर्ती बिंदु (x2, y2) प्राप्त करते हैं और पथ (X1, y1) -> (x2, y2) और ( x2, y2) -> (x0, y0), पुनरावृत्ति, हाँ।

दर्ज किया गया MAP_RANGE पैरामीटर, एक तरफ, यह निर्धारित करता है कि तरंग एल्गोरिथ्म मानचित्र कितनी बार पूरी तरह से फिर से बनाया जाएगा, और दूसरे पर, बहुत लंबे रास्तों की अंतिम सटीकता। MAP_RANGE> 2 * viewRadius के साथ, व्यावहारिक रूप से कोई त्रुटि नहीं है, और समय (सभी चींटियों के लिए मार्ग) मुश्किल से 100ms से अधिक है।

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

स्मृति के लिए: सबसे खराब स्थिति में, भरना होगा: 200 ^ 2 * (200/2) ^ 2 (पूर्ण कार्ड) + (200 / SCALE) ^ 4 (कम रिज़ॉल्यूशन) बाइट्स, जो SCALE के उचित मूल्य के साथ 500 एमबी की सीमा से अधिक नहीं होगा (5 से अधिक)।

3. उद्देश्य

जीतने का एक अच्छा तरीका है कि व्यर्थ की चाल न चलें, न कि सार्थक अवसरों को छोड़ना। आइए विश्लेषण करने का प्रयास करें कि वास्तव में इसका क्या मतलब है।

लक्ष्यों में शामिल हो सकते हैं:
1. दुश्मन एंथिल
2. खाना (केवल अगर आपके पास अपनी खुद की एंथिल है)
3. खुद की सुरक्षा (सुरक्षा के लिए)
4. आपकी चींटियों (हमले को बचाने या सुधारने के लिए) - समर्थन
5. दुश्मन चींटियों
6. अस्पष्टीकृत कोशिकाएं

खेल में क्रमशः कोई और वस्तु नहीं है, और कोई अन्य लक्ष्य नहीं हैं।

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

लक्ष्य वस्तुओं को खोजने के लिए, प्राप्त किए गए संपूर्ण क्षेत्र के चारों ओर जाना आवश्यक है, यह जाँच कर कि क्या वे लक्ष्य के मानदंडों को पूरा करते हैं:

foreach int program in |ProgramList|
foreach Location loc in map
if (MatchingProgram(loc, program))
ProgramList[program].push_back(loc);

जहाँ मैचिंगप्रोग्राम यह निर्धारित करता है कि क्या दिया गया सेल प्रोग्राम फिट बैठता है:
1. अगर प्रोग्राम == दुश्मन एंथिल्स, तो सेल में दुश्मन एंथिल होना चाहिए;
2. भोजन, कोशिका में भोजन होता है;
3. इसकी एंथिल्स, सेल में इसकी एंथिल होती है और इसके लिए एक अप्रत्यक्ष खतरा होता है (दुश्मन चींटी की उपस्थिति हमारी तुलना में करीब है);
4. इसकी चींटियां, कोशिका में इसकी चींटी होती है और इसके लिए एक अप्रत्यक्ष खतरा होता है (व्यूअरियस में दुश्मन चींटियों की उपस्थिति);
5. एक दुश्मन चींटी की उपस्थिति, और उसके दुश्मन "सहयोगी" की तुलना में अधिक समान हैं;
6. अस्पष्टीकृत कोशिकाएँ (ऐसी कोशिकाएँ जिनमें हम नहीं हुए हैं, नीचे इस पर और अधिक)।

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

4. ताले

जैसा कि आप जानते हैं, दो या दो से अधिक चींटियां जो एक ही कोशिका पर गिरती हैं, मर जाती हैं। हम "रचना" के संवेदनहीन नुकसान को रोकना चाहते हैं।

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

इसलिए, आपको उन चींटियों को अलग करना चाहिए जो पाठ्यक्रम के दौरान पहले से ही चले गए हैं, और जो अभी तक स्थानांतरित नहीं हुए हैं। जब आप पहले से ही कब्जे वाले सेल पर जाने की कोशिश करते हैं, तो दो विकल्प सामने आते हैं:
1. वर्तमान चींटी के लिए एक अलग दिशा चुनें;
2. जो दूसरे सेल में हस्तक्षेप करता है ( अवरोधक ) को स्थानांतरित करें।

programAnt(MyAnt *ant):
if (ant->alreadyMoved) return ;
repeat:
direction = getDirectionByProgramList(program)
if (moveResult(ant, direction) == mrBlockerNotMoved)
{
programAnt(blocker);
program++;
goto repeat;
}

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

एक चींटी की बेकार मौत का एक और कारण विरोधियों की अधिकता वाले क्षेत्र में भटकने का प्रयास है। ऐसी स्थितियों का पता लगाने के लिए, आपको कड़ी मेहनत करनी होगी और युद्ध को लिखना होगा।

यह एक समस्या नहीं है, हालांकि, यदि आप C ++ स्टार्टर पैकेज का उपयोग करते हैं, तो आपको राज्य का उपयोग करना होगा। ग्रिड, शत्रु नहीं, क्योंकि सूची में वे प्रकार से भिन्न नहीं हैं (यदि यह पहले से ही सही नहीं है, तो निश्चित रूप से)। वैसे भी ...

5. स्टार्टर पैकेज इतना अच्छा क्यों नहीं है

1. MyAnts में प्राप्त चींटी वस्तुएं अपने मापदंडों को संग्रहीत नहीं करती हैं। मैंने पहले ही उल्लेख किया है कि प्रत्येक चींटी के लिए अपना अंतिम कार्यक्रम और पथ रखना बुरा नहीं है, लेकिन आप State.h के साथ ऐसा नहीं कर सकते - वेक्टर myAnts प्रत्येक मोड़ पर बनाया गया है। इसलिए, चींटियों के मापदंडों को संग्रहीत करने का सही तरीका यह होगा कि आप फॉर्म MyAnt * antMap [MAX_X] [MAX_Y] का एक नक्शा बनाएं, जिसे आप मैन्युअल रूप से अपडेट करेंगे (यह एक विशिष्ट चींटी के लिए मेकवॉव फ़ंक्शन में करना इतना मुश्किल नहीं है)।

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

3. std :: वेक्टर <std :: वेक्टर> ग्रिड। यहां हम गति खो देते हैं, और कुछ मामलों में हम स्क्वायर ग्रिड [MAX_X] [MAX_Y] के खिलाफ भी मेमोरी का उपयोग बढ़ाते हैं। गति का नुकसान मज़ाक नहीं है, क्योंकि ऑब्जेक्ट को बहुत खराब तरीके से कैश किया जाता है, अलग-अलग मेमोरी एड्रेस पर बिखरे हुए हैं।

6. प्रदेशों का अनुसंधान और नियंत्रण

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

अनुसंधान में उन स्थानों पर स्थैतिक वस्तुओं की खोज शामिल है जहां हम (एंथिल, पानी) नहीं रहे हैं।

नियंत्रण - यह जांचना कि क्या कुछ उपयोगी (भोजन) या हानिकारक (दुश्मन चींटियों) प्रकट हुआ है।

दोनों और एक और, एक सार एक ही चीज - कोशिकाएं जिसमें हम लंबे समय तक नहीं रहे हैं। और यह अवधारणा काफी आसानी से औपचारिक हो जाती है।

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

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

7. प्रतिबिंबित करने का कारण

अब हमारी चींटियां काफी व्यवहार्य हैं और जानते हैं कि क्या करना है, हालांकि, उपरोक्त एल्गोरिथ्म जीत की गारंटी नहीं देता है।

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

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

मुझे उम्मीद है कि उपरोक्त किसी को कुछ मुद्दों को हल करने में मदद करेगा, या कम से कम यह दिखाएगा कि सामान्य तौर पर प्रतियोगिता का विषय इतना मुश्किल नहीं है। सौभाग्य है