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

मुझे विश्वास नहीं हो रहा है कि मैं जीता हूं।
और इससे भी अधिक, मैं विश्वास नहीं कर सकता कि मैं निर्णायक रूप से जीता हूं।

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

यहाँ मेरे एक गेम का एक उदाहरण है: aichallenge.org/visualizer.php?game=346288&user=4513 ( यह वह गेम नहीं है जिसे लेखक ने अपने लेख में उद्धृत किया है। मैं इसे लिंक नहीं दे सकता क्योंकि यह सीधे लेखक के सर्वर पर संग्रहीत है। - लगभग अनुवाद। ) । इस लेख में, मैं यह बताना चाहता हूं कि मेरा कोड क्या करता है और वास्तव में इसे करने में कैसे सफल होता है। कई तकनीकी बिंदु हैं, और सामान्य तौर पर लेख स्वयं रणनीति के बारे में नहीं है, लेकिन मैं और अधिक सरल रूप से समझाने की कोशिश करूंगा।

कोड के बारे में

मैंने जावा स्टार्टर पैक को डाउनलोड करके , फ़ाइलों का नाम बदलकर, उन सभी को हटाकर, जो अतिश्योक्तिपूर्ण था, एक नई Strategy वर्ग को जोड़ना शुरू किया और जल्द ही महसूस किया कि मुझे एक चींटी का प्रतिनिधित्व करने वाले वर्ग की भी आवश्यकता होगी। मैंने अपने सभी कोड Strategy क्लास में लिखे, जिसके परिणामस्वरूप लगभग 1800 लाइनें कोड की थीं। ब्याज की भी Ant.java और Tile.java , दोनों ही फ़ील्ड की एक गुच्छा के साथ मूल्य ऑब्जेक्ट हैं।

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

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

यदि आप स्रोत कोड को स्वयं देखना चाहते हैं, तो आपको पता होना चाहिए: यह गोवनोकोडा से भरा है, और मुझे इस पर विशेष रूप से गर्व नहीं है। हालाँकि, आप शायद इसे किसी भी तरह से देखना चाहते हैं, इसलिए आप इसे यहाँ डाउनलोड कर सकते हैं ।

रणनीति कार्यान्वयन

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

तो क्या वास्तव में हर मोड़ होता है? सभी प्रारंभिकताओं और पूर्व-गणनाओं के बाद, मैं इस क्रम में निम्नलिखित तरीके कहता हूं:

• initMissions ();
• शत्रुहिल ();
• भोजन ();
• initExplore ();
• createAreas ();
• लड़ाई ();
• रक्षा ();
• दृष्टिकोण दुश्मन ();
• attackDetachedEnemy ();
• भागने के दुश्मन ();
• वितरित (सच्चा);
• अन्वेषण ();
• doMissions ();
• createMissions ();
• वितरित (झूठा);
• cleanAreas ();

नीचे मैं यह समझाने की कोशिश करूंगा कि ये सभी तरीके क्या हैं, लेकिन संक्षेप में, वे बस चींटियों को स्थानांतरित करते हैं जो कुछ मानदंडों को फिट करते हैं। यदि किसी भी चींटी को स्थानांतरित किया जाता है, तो इसके बारे में जानकारी तुरंत सर्वर को भेजी जाती है, और कार्रवाई को पूर्ववत करना संभव नहीं है।

विस्तृत खोज

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

 LinkedList<Tile> openList = new LinkedList<Tile>(); LinkedList<Tile> changedTiles = new LinkedList<Tile>(); openList.add(foodTile); foodTile.dist = 0; foodTile.isReached = true; changedTiles.add(foodTile); while (!openList.isEmpty()) { Tile tile = openList.removeFirst(); if (tile.dist >= 10) break; for (Tile n : tile.neighbors) { if (n.isReached) continue; if (n.type == Type.MY_ANT) { // found one of my ants at the tile n } n.isReached = true; n.dist = tile.dist + 1; changedTiles.add(n); openList.add(n); } } for (Tile tile : changedTiles) tile.isReached = false; 

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

पाठ्यक्रम का प्रारंभ

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

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

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

अनुसंधान और मिशन

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

अध्ययन

एक्सप्लोरवैल्यू मानचित्र पर प्रत्येक सेल के लिए संग्रहीत किया जाता है, जो 1 प्रत्येक मोड़ से बढ़ता है, अगर यह सेल 10 में बीएफएस के साथ उपलब्ध नहीं है, तो कम से कम मेरी चींटी में से एक के साथ बदल जाता है। यदि सेल पहुंच योग्य है, तो काउंटर शून्य पर रीसेट हो जाता है। इस प्रकार, एक्स्प्लव्यू एक उपाय है कि मुझे कब तक पता नहीं था कि सेल में क्या चल रहा है।

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

मिशन

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

भूमि और सीमा

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

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

 target = area.border.get(turnRandom.nextInt(area.border.size())); 

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

अधिक विविध

आप एक टिप्पणी कर सकते हैं कि सेल 10 चालों में पहुंच योग्य है - सेल की दूरी 77 से अधिक नहीं के समान है, लेकिन वे बहुत करीब हैं, और मुझे इसके साथ कोई समस्या नहीं थी।

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

भोजन

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

मैक्लिओपोल्ड ने एक अच्छी पोस्ट लिखी जिसमें उन्होंने इस बारे में बात की कि उनके साथ यह कैसे हुआ।

दुश्मन एंथिल्स

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

लड़ाई

खैर, मज़ा शुरू हुआ! निस्संदेह, लड़ाई का तर्क सबसे अधिक चर्चा का मुद्दा था।

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

उदाहरण

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

 % % % % % % % % A % % % % % . B % % % % . . C % % X . . . % % % Y . . % % % % % % % 

मैं यह दिखाने के लिए बहुत छोटा नहीं था कि यह क्या हो रहा है:
N / E / S / W का अर्थ है क्रमशः उत्तर / पूर्व / दक्षिण / पश्चिम की ओर बढ़ना, और "-" का अर्थ है जगह में रहना।

वृक्ष DFS का उपयोग करके मक्खी पर उत्पन्न होता है। हम चींटी ए के लिए संभावित गति पर विचार करके शुरू करते हैं, इस गति का अनुकरण करते हैं और चींटी बी के लिए जारी रखते हैं। अंतिम दुश्मन चींटी चले जाने के बाद, हम एक साधारण सूत्र का उपयोग करके स्थिति का मूल्यांकन करते हैं: (मृत दुश्मन चींटियों की संख्या) माइनस (मृत चींटियों की संख्या मेरी)। शत्रु नोड्स (न्यूनतम) हमेशा उन चालों को चुनते हैं जो सबसे छोटे परिणाम की ओर ले जाते हैं, जबकि हमारे नोड्स (अधिकतम) उन मानों को चुनते हैं जिनके लिए इस सूत्र का मान अधिकतम है। यदि हम A, B और C को दक्षिण की ओर (बाएँ सबट्री) स्थानांतरित करते हैं, तो दोनों शत्रु किसी भी स्थान पर नहीं मरेंगे जहाँ वे चलते हैं, इसलिए मान +2 है लेकिन अगर हम ए को जगह में छोड़ देते हैं और केवल बी और सी को स्थानांतरित करते हैं, तो दोनों दुश्मन पूर्व में जा सकते हैं, जिसके परिणामस्वरूप हर कोई मर जाएगा, और अंतिम मूल्य 2 - 2 = 0. होगा यह महान है, क्योंकि हम कुछ विकल्पों में कटौती कर सकते हैं और भूरे रंग के फ्रेम में किसी और चीज को न देखें, क्योंकि यह पहले से ही पता है कि एक संयोजन है जो 2 का परिणाम हो सकता है, लेकिन चूंकि दुश्मन हमेशा उन आंदोलनों का चयन करता है जो हमारे लिए कम से कम फायदेमंद होते हैं, इस मान से शून्य से अधिक नहीं होने वाला मान इस भूरे रंग के फ्रेम में चुना जाएगा ।

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

छद्म कोड में कार्यान्वयन कुछ इस तरह दिखता है:

 List myAnts List enemyAnts bestValue = -Infinity void max(antIndex) { if antIndex < myAnts.size myAnt = myAnts[antIndex] for each possible move of myAnt simulate move max(antIndex+1) undo move else value = min(0) if value > bestValue bestValue = value save the current simulated moves of all my ants } int min(antIndex) { if antIndex < enemyAnts.size minValue = +Infinity enemyAnt = enemyAnts[antIndex] for each possible move of enemyAnt simulate move value = min(antIndex+1) undo move if value < bestValue return -Infinity // cut! if value < minValue minValue = value return minValue else return evaluate() } 

चींटियों की सूचियों को भरना आवश्यक है, और फिर अधिकतम आंदोलनों की सूची प्राप्त करने के परिणामस्वरूप, अधिकतम (0) को कॉल करें।

अनुकूलन

दो पड़ोसी चींटियां जो एक चाल नहीं बनाती हैं वे समान हैं जैसे कि वे स्थानों को स्विच करते हैं, इसलिए दूसरे विकल्प को अनदेखा किया जा सकता है। इसे प्राप्त करने के लिए, मैं लड़ाई से पहले प्रत्येक चींटी की स्थिति बनाए रखता हूं।

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

चेक किए गए आंदोलनों की सूची

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

 . . . . . . . . A . . . . . . B . . . . . . C . . . . . . . . XY . . . . . . . . . 

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

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

  0 1 2 3 4 5 0 . . . . . . 1 . . , A . . 2 . . . , B . 3 . . . . , . 4 . X . . . . 5 . . . . . . 

यदि कोई चींटी (1/2) है, तो चींटी X को जांचना चाहिए (3/1)। यदि (2/3) पर है, तो जांच (3/1) और (4/2)। के लिए (3/4), चेक (4/2)। यह टेबल जैसा दिखता है:

 (1/2) => [ (3/1) ] (2/3) => [ (3/1), (4/2) ] (3/1) => [ (4/2) ] 

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

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

मूल्यांकन

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

 if (beAgressive) return enemyDeadCount * 300 - myDeadCount * 180 - distValue; else return enemyDeadCount * 512 - myDeadCount * (512+256) - distValue; 

यदि बीग्रेसिव ध्वज को सेट किया जाता है, तो मृत दुश्मन की कीमत 300 अंक होती है, और मृतक अपने 180 दंड का जुर्माना करता है। गैर-आक्रामक मोड में, बॉट समान आदान-प्रदान नहीं करता है, लेकिन तीन के लिए दो देने के लिए काफी तैयार है। distValue - मेरे प्रत्येक चींटी से निकटतम शत्रु से दूरी का योग, हम इस राशि को घटाते हैं, क्योंकि शत्रु के करीब होना बेहतर है।

तो जब प्रगतिशील होना सच है? इसका कुल चींटियों या स्थितिगत लाभ से कोई लेना-देना नहीं है, यह केवल उन चींटियों की संख्या पर निर्भर करता है जो लड़ाई के करीब हैं। अधिक सटीक रूप से, ध्वज सेट किया जाता है यदि मेरी चींटी के बगल में लड़ाई में चींटियों की संख्या (लड़ाई में, और समूह में नहीं) की अधिकतम संख्या 14. से अधिक या बराबर है। क्यों? ज्यादातर क्योंकि 42 को 14 से विभाजित किया जाता है!

शत्रुओं का सामना करना

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

वहाँ भी है हमलावरडाइट दुश्मन विधि, बीटा संस्करण के शेष, जिसने हमें पहले पृथक दुश्मनों से संपर्क करने के लिए मजबूर किया।

सुरक्षा

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

शत्रुओं से बचाव

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

 int addValue = (ESCAPE_CHECK_DIST+1-tile.dist); if (tile.type == Type.MY_ANT) addValue *= 3; else if (tile.type.isEnemy()) addValue *= -3; 

वितरण

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

खैर, यह बात है!

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

अनुवादक से

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

मुझे आशा है कि आप रुचि रखते थे।