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

आप सीखेंगे कि गेम AI प्रोग्रामिंग प्रतियोगिताओं में सफलतापूर्वक प्रतिस्पर्धा कैसे करें।

CodinGame क्या है?

codingame.com सभी उम्र और प्रशिक्षण के स्तरों के डेवलपर्स के लिए एक शैक्षिक मंच है। आप 26 भाषाओं में लिख सकते हैं : सी # और पायथन से बैश और हास्केल तक। सबसे अच्छी बात यह है कि वहाँ कार्य उबाऊ और समझ से बाहर नहीं हैं, लेकिन एक अच्छे GUI के साथ असली खेल:

एक प्रतियोगिता 10-दिवसीय प्रतियोगिता होती है जो हर महीने में एक बार आयोजित की जाती है। कोई भी भाग ले सकता है, एसीएम ICPC का फाइनलिस्ट होना आवश्यक नहीं है। बेशक, बहुत ऊपर जाने के लिए, आपको कम से कम गेमिंग कृत्रिम बुद्धिमत्ता के एल्गोरिदम को समझने की आवश्यकता है।

लेकिन ब्याज के साथ कुछ शाम बिताने के लिए, सबसे बुनियादी ज्ञान पर्याप्त है। प्रत्येक प्रतियोगिता में इनपुट डेटा को पढ़ने के लिए एक तैयार कोड होता है। यह केवल नियमों को पढ़ने के लिए बनी हुई है, और अगर-और - लड़ाई में, सरल लिखें!

कुटलु का कोड

"Cthulhu Code" अंतिम प्रतियोगिता है, जो 15 से 25 जून तक हुई थी। प्लॉट और उद्देश्य का पता लगाने के लिए, एक विवरण पर्याप्त है:

PH'NGLUI MGLW'NAFH CTHULHU R’LYEH WGAH'NAGL RHT
जो हमेशा के लिए झूठ हो सकता है वह बिल्कुल भी मृत नहीं है। और एक रहस्यमय चींटे में मौत मर जाती है।

आप और आपके शोधकर्ताओं की टीम ने Cthulhu की कब्र की खोज की है। यह आपके जीवन का सबसे बुरा निर्णय है, क्योंकि वह जागने के लिए तैयार नहीं था और अब आपकी मृत्यु का भूखा है। लेकिन क्रिप्ट एक वास्तविक भूलभुलैया है, और आपको याद नहीं है कि बाहर निकलना कहाँ था ... अगर यह अभी भी है!
ओह ... और ऐसा लगता है कि Cthulhu अकेला नहीं था, और अब वह दीपों को आपके लिए भेज रहा है।

सबसे लंबे समय तक जीवित रहने की कोशिश करें, लेकिन याद रखें कि आप अकेले लंबे समय तक नहीं रहेंगे ...

नियम

मैं अभी यह कहना चाहूंगा कि नियमों का पाठ विवरण पढ़ने के बजाय, आप नियमों के विश्लेषण का वीडियो देख सकते हैं और टिनसेन से मूल रणनीति देख सकते हैं :

अन्यथा, पर पढ़ें।

नक्शा

खेल में, चार खिलाड़ी उत्पन्न नक्शे पर चलते हैं - अधिक सटीक रूप से, एक दूसरे से जुड़ी कोशिकाओं का ग्राफ। मानचित्र पर अधिक दुश्मन के शत्रु दौड़ रहे हैं, जिनका लक्ष्य खिलाड़ियों को पकड़ना और डराना है।

वर्ण

• शोधकर्ता खिलाड़ियों में से एक है। एक सेल पर किसी भी दिशा में जाता है। इसके पास सुपरपावर हैं, लेकिन बाद में उनके बारे में और अधिक।
• वांडरर एक हरे रंग का राक्षस है। पहले से ज्ञात बिंदुओं से हर 5 मोड़ पर नक्शे पर दिखाई देता है। यह 3 से 6 चालों में घूमता है, निकटतम खिलाड़ी को खोजता है और पीछा शुरू करता है। प्रति मोड़ केवल एक वर्ग जाता है। यदि उसने किसी को भी एन चरणों में नहीं पकड़ा है, तो वह नक्शे से गायब हो जाता है।
• स्लेशर - एक स्किथे के साथ मौत के समान। ऐसे खिलाड़ी के स्थान पर दिखाई दें जिसका स्वास्थ्य 200 अंकों से नीचे गिर गया है, और खेल के अंत तक मानचित्र पर बने रहें। "सीज़" एक खिलाड़ी है अगर उनके बीच कोई दीवारें नहीं हैं। यदि 2 चालों में लक्ष्य खो नहीं जाता है, तो अगला कदम उस स्थान पर कूदता है जहां खिलाड़ी अंतिम बार देखा गया था।

उत्तरजीविता

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

शोधकर्ताओं ने महाशक्तियों

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

खेल का अंत

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

प्रतियोगिता डेवलपर्स खिलाड़ियों को नियम देते हैं, लेकिन सफल खिलाड़ी जीथब में जाते हैं और रेफरी कोड पढ़ते हैं।

युक्ति

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

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

येकातेरिनबर्ग में हब के नेताओं में से एक वान्या डैशकेविच ( स्पेसकोर ) है। वह एक वर्ष से अधिक समय तक कोडिनगैम पर बैठे रहे, सात प्रतियोगिताओं में भाग लिया, और पांच में दुनिया के शीर्ष 100 में शामिल हुए:

मुझे निर्णय के विवरण से पता चला, जिसने उन्हें विश्व लीडरबोर्ड में 64 वें स्थान के साथ प्रदान किया, और उनके फैसले की तुलना खदान से की।

[१] आस पास आओ: वहाँ आप स्टार्टर किट के लिंक पा सकते हैं, नियमों पर चर्चा कर सकते हैं, रणनीति के साथ आ सकते हैं और दिलचस्प लोगों से मिल सकते हैं।

प्रतियोगिता की शुरुआत में, कि अंत में, अगला कदम चुनने के लिए एल्गोरिथ्म समान दिखता है:

• बॉट के लिए उपलब्ध सभी कार्यों को उत्पन्न करें;
• उन्हें वर्तमान स्थिति पर लागू करें;
• इन चालों के परिणामों का मूल्यांकन करें;
• सबसे अच्छा एक चुनें।

उपलब्ध कार्य उत्पन्न करें

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

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

[२] फंतासी को शामिल करने से डरो मत: शुरुआत के लिए, सरल उत्तराधिकार और सशर्त ऑपरेटरों के एक जोड़े पर्याप्त हैं।

स्ट्रोक आवेदन

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

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

spaceorc : मेरा सामान्य दृष्टिकोण हाल ही में दो चरणों में रहा है:

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

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

[३] शीर्ष पर जाना चाहते हैं? आपको नियमों का पता लगाना होगा और एक सिमुलेशन लिखना होगा।

विरोधियों का अनुकरण

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

परिणामस्वरूप, एक त्वरित अनुकरण अधूरा हो गया:

• मेरे से 8 कोशिकाओं से आगे भटकने वालों पर विचार करना बंद कर दिया;
• घूमने वालों को रोकना बंद कर दिया, क्योंकि वे पहले से ही 5 चालों में घूमते हैं, और यह मेरी खोज गहराई है।

इसके कारण, खोज की गहराई बढ़ गई है। मैंने अपने विरोधियों से केवल चाल (येल, लाइट, प्लेन के बिना) का अनुकरण करने की कोशिश की, लेकिन यह खराब निकला।

मूल्यांकन समारोह

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

ओलीस्टेका : मेरे मूल्यांकन में कौन से पैरामीटर शामिल किए गए थे:

• मेरे शोधकर्ता का स्वास्थ्य;
• पथिक:
  
  • अगर वह अगले कदम के लिए यहां आने की संभावना है, तो यह एक बुरा कदम है;
  • अगर मैं उसके साथ एक ही पंक्ति पर हूं, तो उससे दूर, बेहतर;
  • अगर वह मुझ पर भी हावी है, तो दूरी और भी महत्वपूर्ण है।
• चारों ओर मुक्त कोशिकाओं, ताकि एक मृत अंत में चलाने के लिए नहीं;
• अन्य शोधकर्ताओं, जो करीब रहने के लिए बेहतर हैं;
• वर्तमान योजना: यदि मेरा स्वास्थ्य 230 से नीचे चला जाता है, तो उपचार एक अच्छा विचार है।

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

नतीजतन, मेरा मूल्यांकन छोटा हो सकता है, लेकिन जैसा कि वे कहते हैं, यह काम करता है - स्पर्श न करें।

spaceorc : मैंने मूल्यांकन कार्यों के साथ खेलने की कोशिश की, लेकिन यह बहुत अच्छी तरह से काम नहीं कर पाया ... सामान्य तौर पर, उनमें से कुछ जो लीडरबोर्ड में मुझसे काफी अधिक निकले, वे बिल्कुल भी नहीं गुजरे, लेकिन मूल्यांकन के लिए अच्छे फीचर्स के साथ आए। मैंने इससे सामना नहीं किया। मेरे अंतिम मूल्यांकन समारोह में शामिल हैं:

• अंकों की संख्या (दौरे जिस पर मृत्यु हो गई + स्वास्थ्य);
• कौआ ;
• विदेशी शोधकर्ताओं के लिए दूरी।

[४] प्रयोग: मूल्यांकन समारोह के मापदंडों के गुणांक को बदलें, नए पैरामीटर जोड़ें और पुराने को हटा दें।

सबसे अच्छा कदम चुनना

हम चाल को अवरोही क्रम में क्रमबद्ध करते हैं, पहले एक को लेते हैं, इसका उपयोग करते हैं।

अनुकूलन

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

ओलिस्टेका : मैंने इस तथ्य का लाभ उठाया कि मानचित्र को एक ग्राफ के रूप में दर्शाया जा सकता है - मैंने पहले से सेल तक के सभी रास्तों की लंबाई की गणना की और हर बार इस पर समय नहीं बिताया।

spaceorc : CodinGame पर, सिमुलेशन ने तेज़ी से काम किया, 50 ms में इसने कई दसियों हजार चालें बनाईं। जिसके कारण:

• बिट मास्क और असुरक्षित कोड।
• एक्सप्लोरर - इंट, वांडरर - इंट, स्लेशर - इंट।
• सभी परिवर्तनशील स्थिति 128 बाइट्स में फिट होती है, इसलिए इसके साथ सब कुछ बहुत जल्दी काम करता है।
• समन्वय बाइट है, क्योंकि सबसे बड़े मानचित्र में 222 मुक्त कोशिकाएं थीं।
• कतार होनी चाहिए - var कतार = stackalloc बाइट [255]।
• रास्तों, दूरियों और अन्य चीजों की पूर्व-गणना।

मैं इसे हर समय कर रहा हूँ, यह बहुत अच्छा है। वैसे, मैं हमेशा इस तरह के सिमुलेशन के लिए बहुत सारे परीक्षण लिखता हूं, जिसके बिना इसे बस डिबग नहीं किया जा सकता है।

[५] शीर्ष १०० में एक स्थान के लिए प्रतिस्पर्धा करना चाहते हैं - अक्षम कोड से छुटकारा पाएं।

इसके कारण क्या हुआ

ऑलिस्टेका : प्रतियोगिता के दौरान, मेरे बॉट लगातार शीर्ष 300 में रहे। किसी समय, मैं विश्व लीडरबोर्ड में 84 वें स्थान पर था, लेकिन फिर मैंने एक नया संस्करण बनाया और वापस नहीं लौटा t \ (ツ) / 290 290 वें स्थान पर समाप्त होने के बाद, मैं तीन कारणों से बहुत खुश हूं:

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

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

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

निष्कर्ष में

CodinGame की जाँच करें और अपने हाथ की कोशिश करो! जुलाई में वे एक नई प्रतियोगिता का वादा करते हैं - हब में आते हैं, हम बॉट्स को एक साथ कोड करेंगे।

उपयोगी लिंक:

• कोडिनगैम खाते: मेरा और वाणी डैशकेविच ;
• अगली प्रतियोगिता लेजेंड्स ऑफ़ कोड एंड मैजिक (लेखन के समय, 1392 पहले ही पंजीकृत हो चुकी है);
• कंटूर के ब्लॉग और टेलीग्राम में चैनल - उनमें नए हब की घोषणाओं की प्रतीक्षा करें।

युपीडी। टिप्पणी के लिए धन्यवाद dbf : कोड ऑफ कुटुलु को मल्टीप्लेयर पर अपलोड किया गया है। तो आप लेख में प्राप्त ज्ञान को व्यवहार में ला सकते हैं! :)