मिनी एआई कप 4 में दूसरा स्थान इतिहास: पेपर आईओ

मेरा नाम इगोर वोल्कोव है। मैं एक जावा डेवलपर, वास्तुकार, टीम लीडर, तकनीकी प्रबंधक के रूप में एक परामर्श कंपनी में काम करता हूं। परियोजना की वर्तमान जरूरतों के आधार पर विभिन्न भूमिकाएँ। उन्होंने एक लंबे समय के लिए mail.ru से प्रतियोगिताओं पर ध्यान आकर्षित किया, लेकिन यह केवल पेपर IO पर सक्रिय रूप से भाग लेने के लिए निकला।

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

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

रणनीति एल्गोरिदम

रणनीति के उच्च-स्तरीय एल्गोरिथ्म को निम्नलिखित 6 बिंदुओं द्वारा दर्शाया जा सकता है:

1. दुनिया की स्थिति पढ़ें
2. संदेश ऑब्जेक्ट को कार्य ऑब्जेक्ट में कनवर्ट करें
3. आयताकार मार्गों का एक सेट तैयार करें
4. उत्पन्न मार्गों में से प्रत्येक की दर
5. सबसे अच्छा मार्ग चुनें
6. टीम भेजें

प्रतियोगिता के दौरान यह एल्गोरिथ्म नहीं बदला है। केवल बॉट मार्ग बनाने की विधि और उनके मूल्यांकन को संशोधित किया गया था।

SimpleStrategy वर्ग में रणनीति का प्रारंभिक संस्करण है, और BestStrategy वर्ग एक उन्नत संस्करण है, जिसने प्रतियोगिता में दूसरा स्थान प्राप्त किया।

दुनिया की स्थिति पढ़ना

दुनिया की स्थिति को STDIN के माध्यम से JSON ऑब्जेक्ट के रूप में प्रसारित किया जाता है। मैंने pom.xml में देखा कि आप Gson लाइब्रेरी का उपयोग कर सकते हैं और दुनिया की स्थिति को पढ़ने का कार्य बहुत सरल हो गया है। Gson लाइब्रेरी का उपयोग करते हुए, संदेश वर्ग की एक आवृत्ति में मानक इनपुट स्ट्रीम से पढ़े गए JSON स्ट्रिंग को deserialized किया। कोड Main.java (लाइनें 44-49) में है ।

काम की वस्तुएँ बनाएँ

मुख्य कार्यक्रम कोड में परिवहन वस्तुओं का उपयोग करना आमतौर पर बहुत सुविधाजनक और वास्तुशिल्प रूप से गलत नहीं है। उदाहरण के लिए, आयोजक, एक कारण या किसी अन्य के लिए, संदेशों के प्रारूप को बदल सकते हैं। इसलिए, परिवहन वस्तुओं को श्रमिकों में बदलना आवश्यक है, जिसका उपयोग मुख्य कार्यक्रम कोड में किया जाएगा। प्लेयर और PlayerState कक्षाएं बॉट की स्थिति को संरक्षित करती हैं, और उपयोगिता वर्ग MessagePlayer2PlayerConverter परिवहन संदेश से डेटा के आधार पर इन वर्गों को बनाने में मदद करता है। बोनस वर्ग में खेल के क्षेत्र में एक सेल के बोनस के बारे में जानकारी होती है। कार्य ऑब्जेक्ट बनाने के लिए कोड Main.java (लाइनें 61-74) में स्थित है।

मार्ग निर्माण

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

बॉट के प्रक्षेपवक्रों का ऐसा गठन बाद के मूल्यांकन के प्रदर्शन के मामले में बहुत प्रभावी नहीं था, क्योंकि कई बार एक ही प्रक्षेपवक्र की गणना करना आवश्यक था, लेकिन यह खेल के यांत्रिकी को समझने के लिए बहुत उपयोगी था।

रणनीति के बाद के संस्करणों में, BestStrategy ने रूट ट्री का उपयोग करना शुरू किया। MoveNode वर्ग इस पेड़ के नोड को दर्शाता है। पेड़ पूरी तरह से रणनीति की शुरुआत में बनता है। MoveNode वर्ग की init पद्धति पर ध्यान दें । यह SimpleStrategy क्लास से रूट जेनरेट करने के समान है। मौलिक रूप से, प्रश्न में मार्ग पहले संस्करण से बहुत अलग नहीं है।

मुझे लगता है कि मार्गों का गठन, एक और मोड़ जोड़कर थोड़ा और बेहतर किया जा सकता था। लेकिन अनुकूलन के लिए पर्याप्त समय नहीं था।

रूट रेटिंग

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

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

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

अजीब है, लेकिन रणनीति के पहले संस्करणों की प्रधानता के बावजूद, इसने खुद को काफी अच्छी तरह से दिखाया: सैंडबॉक्स में 10 वां स्थान। सच है, प्रीफिनल राउंड में वह जल्दी से नीचे जाने लगा: अन्य प्रतिभागियों ने अपनी रणनीतियों में सुधार किया।

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

खेल मैदान की कोशिकाओं की गिनती

1. टिक जिस पर प्रतिद्वंद्वी के बॉट पिंजरे (पूंछ पर टिक) पर कब्जा कर सकते हैं
2. टिक जिस पर प्रतिद्वंद्वी के बॉट सेल में प्रवेश कर सकते हैं
3. पिंजरे में प्रवेश करते समय पूंछ की लंबाई
4. टिक जिस पर प्रतिद्वंद्वी के बॉट पिंजरे से बाहर निकल सकते हैं
5. पिंजरे से बाहर निकलते समय पूंछ की लंबाई
6. टिक जिस पर एक सेल को प्रतिद्वंद्वी के बॉट द्वारा कब्जा किया जा सकता है
7. टिक जिस पर सेल क्षेत्र पर कब्जा करने का लक्ष्य हो सकता है
8. टिक जिस पर सेल को आरी से मारा जा सकता है

एनालिटिक्स की गहराई 10 चालों तक सीमित है। मुझे लगता है कि व्यक्तिगत प्रतिद्वंद्वियों की गणना करने या अस्थायी गहराई का परिचय देने से इनकार करके अधिक गहराई हासिल करना संभव था, लेकिन अनुकूलन के लिए पर्याप्त समय नहीं था। AnalyticsBuilder के अलावा , उन्होंने SimpleTickMatrixBuilder का उपयोग करना शुरू किया , अगर AnalyticsBuilder के लिए रेंडरिंग डेप्थ की कमी थी। Analytics परिणाम BestStrategy द्वारा उपयोग किए जाते हैं ।

रेटिंग फ़ंक्शन में भी थोड़ा सुधार हुआ है:

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

रणनीति डिबगिंग

रणनीति के पहले संस्करणों में बड़ी संख्या में टाइपोस और त्रुटियां थीं: जाहिर है, रात के प्रोग्रामिंग का परिणाम। उदाहरण के लिए, सेल वर्ग में, इंडेक्स को गलत तरीके से माना जाता था: इसके बजाय this.index = x * Game.sizeY + y , this.index = x * Game.width + y । पहले तो मैंने केवल परीक्षणों पर भरोसा करने की कोशिश की, लेकिन मेरे अंतर्ज्ञान ने सुझाव दिया कि बिना विज़ुअलाइज़ेशन और पहले खेले गए मैचों को खेले बिना, कोड में त्रुटियों को ढूंढना और गलत निर्णय लेने के कारणों का विश्लेषण करना मुश्किल होगा। नतीजतन, डिबगविंडो विज़ुअलाइज़र दिखाई दिया , जिसमें आप पहले से खेले गए गेम को चरण दर चरण देख सकते हैं, साथ ही वांछित टिक पर डिबगिंग शुरू कर सकते हैं। कोड बहुत सुंदर नहीं है, जल्दबाजी में लिखा गया है, लेकिन डिबगिंग के समय इसने मेरी बहुत मदद की। उदाहरण के लिए, सेल इंडेक्स की गलत गणना के साथ त्रुटि का तुरंत पता लगाया गया था। कई प्रतियोगियों ने कंसोल में डिबगिंग जानकारी प्रदर्शित की, लेकिन यह मुझे पर्याप्त नहीं लगा।

अनुकूलन

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

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

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

असत्य विचार

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

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

खाली कोशिकाओं के लिए लेखांकन जो एक मूल्यांकन समारोह के रूप में निकट भविष्य में कब्जा कर लिया जाएगा।

सिफारिशें और धन्यवाद

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

आयोजकों को बहुत धन्यवाद। कुछ तकनीकी समस्याओं के बावजूद, प्रतियोगिता दिलचस्प बन गई। मैं अगले करने के लिए तत्पर हैं!