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

समुदाय

पहले हफ्तों को आयोजकों के साथ समस्याओं द्वारा चिह्नित किया गया था: यह सर्वर का प्रदर्शन है, और "गंदे" गेम के मामले, शुरुआती सेट और उपयोगकर्ताओं के काम के माहौल के बीच विभिन्न संघर्ष, 12 वीं -13 वीं को कोड भेजने के साथ समस्याएं। लेकिन, उनके क्रेडिट के लिए, सब कुछ जल्दी से पर्याप्त रूप से तय किया गया था। खैर, या लगभग सब कुछ ... अब तक, प्रत्येक बॉट औसतन एक घंटे में एक बार खेलता है, जिसका अर्थ है कि यह समझने के लिए कि कोड में परिवर्तन ने रेटिंग को कैसे प्रभावित किया है, आपको एक या दो दिन इंतजार करना होगा (अगले सप्ताह यह संभवतः एक और सर्वर जोड़ देगा)। इस समस्या का एक हिस्सा एक अनौपचारिक टीसीपी सर्वर द्वारा हल किया जाता है जिससे आप अपने कंप्यूटर से सीधे बॉट को कनेक्ट कर सकते हैं। खेलों की आवृत्ति काफी बढ़ जाती है और, प्लस के रूप में, डिबगिंग डेटा को सहेजना संभव हो जाता है। मुख्य दोष यह है कि सर्वर में अधिकांश शीर्ष बॉट नहीं हैं, इसलिए परिणाम केवल परीक्षण या कोड प्रसंस्करण के समय के लिए समझ में आता है। और नवीनतम समाचार: इस समय के दौरान , लंबे समय से प्रतीक्षित लिस्प, हास्केल, ओकेमेल और कॉफीस्क्रिप्ट, साथ ही साथ अल्पज्ञात विदेशी: पीएचपी, पर्ल, जावास्क्रिप्ट और रूबी (या यह दूसरा तरीका था?) क्या समर्थित सी ++, सी #, जावा और पायथन की सूची में जोड़ा गया था?



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

• JBotManager - टीसीपी सर्वर के लिए एक क्लाइंट रिकॉर्डिंग और गेम देखना, आपको कमांड लाइन से निपटने की अनुमति नहीं देता है और बहुत शुरुआत में उपयोगी होगा
• जीयूआई फ्रंटेंड कार्ड जेनरेटर
• वे विज़ुअलाइज़र जिन्हें अब गिना नहीं जा सकता है:
  • PlanetWars pastebin आपको PlayGame.jar का आउटपुट डाउनलोड करने और इसे ऑनलाइन देखने की अनुमति देता है
  • विज़ुअलाइज़र के साथ इंजन , सी ++ में फिर से लिखा गया - यह सिर्फ तेजी से काम करता है
  • Qt पर बनाया गया एक और ग्रह संख्या और उनकी वृद्धि प्रदर्शित करता है
  • और HTML5 पर आधारित अंतिम - इंजन के आउटपुट को आधिकारिक जावास्क्रिप्ट प्लेयर के प्रारूप में कनवर्ट करता है, कमांड लाइन से काम करता है
• डिबगिंग के लिए सुविधाजनक बैसाखी - खेल के दौरान प्राप्त बॉट को डेटा के एक सेट में इंजन के उत्पादन में परिवर्तित करता है। इस डेटा को बॉट इनपुट में सबमिट करके, आप इसे डीबग मोड में इंजन के बिना शुरू कर सकते हैं। यह काम करता है, ज़ाहिर है, केवल अस्पष्ट व्यवहार वाले बॉट के लिए
• बॉट्स के परीक्षण के लिए बहु-पिरोया पायथन लिपि

बॉट विकास के बारे में

अगला, मैं अपनी भागीदारी के दौरान प्राप्त अनुभव को साझा करना चाहता हूं। वह पूर्ण सत्य की भूमिका का ढोंग नहीं करता, बल्कि यह विचार का भोजन है। तो एक बॉट क्या करने में सक्षम होना चाहिए?

सिमुलेशन

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

सार्वजनिक शून्य अनुकरण () {

// सूची <बेड़े> बेड़े - लक्ष्य ग्रह के लिए उड़ान भरने वाले बेड़े

अगर ( बेड़े ) । आकार () == 0 )

वापसी;

SortFleets ( ) ;



// वर्तमान गणना की गई अवस्था के साथ चर

int owner = लक्ष्य। मालिक ;

int shipCount = लक्ष्य। शिपकाउंट ;

// परिणाम संचित करने के लिए वर्तमान संसाधित चाल को संग्रहीत करता है

int lastGrowth = 0 ;



for ( int i = 0 ; मैं < fleets। size ( ) ; i ++ ) {

// यदि इस कदम के परिणामों की गणना की जाती है, तो राज्य को बचाएं

अगर ( lastGrowth < fleets। get । ( i ) । मोड़ना ) {

अगर ( i > 0 )

राज्यों। जोड़ें ( नया प्लैनेटस्टेट ( शिपकाउंट, मालिक, लास्ट ग्रोथ ) ) ;

// केवल खिलाड़ी ग्रहों पर विकास

यदि ( लक्ष्य स्वामी > 0 )

shipCount + = लक्ष्य। विकास करें *

( fleets। get ( i ) । मुड़ना -पड़ना - lastGrowth ) ;

// इस कदम की आगे गणना की जाएगी

lastGrowth = बेड़ा। मिल ( i ) । बदल रहा है ;

}

अगर ( स्वामी ! = बेड़े ) । ( i ) । स्वामी

जहाजखाना - = बेड़ा। मिल ( i ) । अंक ;

अन्यथा

shipCount + = fleets। मिल ( i ) । अंक ;

// स्वामित्व का परिवर्तन

अगर ( शिपकाउंट < 0 ) {

shipCount * = - 1 ;

मालिक = बेड़ा। मिल ( i ) । मालिक ;

}

अगर ( i == बेड़े ) । आकार ( ) - 1 )

राज्यों। जोड़ें ( नया प्लैनेटस्टेट ( शिपकाउंट, मालिक, लास्ट ग्रोथ ) ) ;

}

}

वैसे, सिरिलिक टिप्पणियों वाला कोड सर्वर पर संकलित नहीं होता है, इसलिए सबमिट करने से पहले सावधान रहें। राज्य परिवर्तनों की गणना के बाद, किसी भी चाल के लिए पूर्वानुमान प्राप्त करना काफी सरल है:

सार्वजनिक PlanetState getInfoForTurn ( int बारी ) {

int growth = लक्ष्य। वृद्धि ;

// ऐसे मामले जब कोई आवक बेड़े नहीं थे और

// जब अनुरोध पहले बेड़े के आगमन से पहले स्थानांतरित करने के लिए जाता है

if ( स्टेट्स। size ( ) == 0 || स्टेट्स। get ( 0 ) । turn > टर्न ) {

// तटस्थ ग्रहों पर कोई लाभ नहीं है

यदि ( लक्ष्य। स्वामी == 0 )

वृद्धि = 0 ;

नया PlanetState लौटाएं ( लक्ष्य। shipCount + turn * growth,

लक्ष्य। मालिक , बारी ) ;

}

int last = स्टेट्स आकार ( ) - 1 ;

// अंतिम बेड़े के आने के बाद आगे बढ़ें

अगर ( टर्न > = स्टेट्स। get ( last ) । टर्न ) {

यदि ( राज्य मिलता है ) ( अंतिम ) । स्वामी == 0 )

वृद्धि = 0 ;

नए PlanetState को लौटाएं ( राज्य मिलता है। अंतिम ) । shipCount +

( टर्न - स्टेट्स। get ( last ) । टर्न ) * growth,

राज्यों। ( अंतिम ) । मालिक , बारी ) ;

}

// पहले और अंतिम बेड़े के आगमन के बीच

for ( int i = 1 ; i < = last ; i ++ )

अगर ( अवस्थाएँ। get ( i ) । टर्न > टर्न ) {

अगर ( राज्य मिलता है। ( i - 1 ) । मालिक == 0 )

वृद्धि = 0 ;

नए PlanetState को लौटाएं ( राज्यों को मिलता है ( i - 1 ) । shipCount +

( टर्न - स्टेट्स। get । ( i - 1 ) । turn ) * ग्रोथ,

राज्यों। get ( i - 1 ) । मालिक , बारी ) ;

}

वापसी शून्य ;

}

लॉगिंग

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

खेल शैली स्विचिंग

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

अगर ( myPlanets। आकार ( ) < 4 )

मोड = बॉटमोड। bmStart ;

और अगर ( myPower > दुश्मनपावर * 3 && बारी > 50 )

मोड = बॉटमोड। bmFinishHim ;

और अगर ( टर्न > 180 || myPower * 5 < दुश्मनपावर * 4 )

मोड = बॉटमोड। bmRegenerate ;

अन्यथा

मोड = बॉटमोड। bmNormal ;

मूल्यांकन कार्य

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

मानक चाल

स्पष्ट रूप से, हमलों के अलावा, ऐसी मानक तकनीकों को लागू करना उचित है:

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

स्टार्टर किट संशोधन

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

आगे क्या?

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

1. कहानी। पिछले चालों के परिणामों के लिए लेखांकन आपको प्रवाह की निगरानी करने, सिद्धांत के अनुसार यातायात एकाग्रता और वास्तविक विकास के स्थानों की पहचान करने की अनुमति देता है
   
   realGrowth = growthRate + (fleetsInMy - fleetsInEnemy - fleetsOut) / historySize
2. नक्शा विश्लेषण। सबसे सरल मामले में, यह समस्या एक मूल्यांकन फ़ंक्शन की शुरुआत करके हल की जाती है जो औसत और न्यूनतम दूरी को अपने स्वयं के और विदेशी ग्रहों, विकास और उन पर जहाजों की संख्या को ध्यान में रखती है। अधिक जटिल मामले में, ग्राफ़ में इष्टतम पथ और अधिकतम प्रवाह खोजने में समस्याएं उत्पन्न होती हैं।
3. संभावित चालों का विश्लेषण। लक्ष्यों का चयन करने के बाद, उनमें से प्रत्येक के लिए आप सबसे सफल ग्रहों के कई सेट उत्पन्न कर सकते हैं जिनसे आप एक हमले का संचालन कर सकते हैं। इसी समय, प्रत्येक सेट के लिए प्रभावशीलता का आकलन और उन जहाजों की संख्या होगी जिन्हें कब्जा या संरक्षण के लिए भेजा जाना है (और इस संख्या को ग्रहों के बीच पुनर्वितरित किया जा सकता है)। इस तरह के एक सेट को चुनने की समस्या है कि उपलब्ध जहाजों को भेजने पर अधिकतम लाभ होगा। यह थोड़ा संशोधित पैकेजिंग कार्य है।
4. Temporizing। बॉट्स हैं जो प्रत्येक मोड़ को प्रत्येक ग्रह से सबसे प्राथमिकता वाले क्षेत्रों में सभी विकास भेजते हैं। एक भावना है कि वे सभी "काम" करते हैं, लेकिन क्या ऐसा है? भेजे गए बेड़े प्रतिद्वंद्वी के लिए गणना करने के लिए बहुत आसान हैं: उनके पास पहले से ही एक लक्ष्य है, प्रतीक्षा करने वाले लोगों के विपरीत। इसी समय, ऐसे लक्ष्य के लिए इंतजार करना संभव हो जाता है कि आप निश्चित रूप से (अच्छी तरह से, या लगभग निश्चित रूप से) कब्जा कर सकते हैं या, इसके विपरीत, रक्षात्मक पर रहते हैं। इसलिए, यह समझना महत्वपूर्ण है कि छोटे हिस्से में एक हमले की संभावना अधिक बुराई है, क्योंकि आप तब तक परिणाम प्राप्त नहीं करेंगे जब तक कि कुल द्रव्यमान एक निश्चित निशान से अधिक न हो। तो क्यों न उस क्षण तक इंतजार किया जाए जब यह द्रव्यमान आपमें जमा हो। और एक और तथ्य: भेजे गए बेड़े खेल से बाहर है जब तक कि लक्ष्य पूरा नहीं हो जाता है, इसलिए दूरियों पर विचार करना महत्वपूर्ण है ताकि जब आप मिटा दिए जाएं तब तक श्रेष्ठ बलों द्वारा हमला करने पर कोई स्थिति न हो।
5. चाल के बीच गणना। नियमों के अनुसार, इस कदम का समय 1000 ms है और बॉट थ्रेड का उपयोग नहीं कर सकता है। लेकिन यह उन क्षणों पर विचार किया जा सकता है जब पाठ्यक्रम पूरा होने के बाद, इंजन उन्हें संसाधित करता है। इन क्षणों में, आप इतिहास, गणना और कैश मानों के साथ काम कर सकते हैं जो शायद ही कभी बदलते हैं (उदाहरण के लिए, ग्रहों के बीच की दूरी, प्रवाह, तटस्थ ग्रहों की प्राथमिकताएं, आदि)

निष्कर्ष

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