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

त्याग

लेख अलेक्सी डिचकोवस्की (कमांडो) और व्लादिमीर किस्लेव (वल्देमार) के सहयोग से लिखा गया था।

उन लोगों के लिए जो सिर्फ विजेताओं के फैसलों के बारे में पढ़ना चाहते हैं, मैं आपको सलाह देता हूं कि आप आइटम "सिमुलेशन" से तुरंत शुरुआत करें।

समस्या का बयान

इस बार, दुनिया के मैकेनिक ड्राइव अहेड मोबाइल गेम को बहुत पसंद कर रहे थे: खिलाड़ियों को उस पर स्थित बटन के साथ एक कार दी गई थी; कार्य दुश्मन के बटन को तेजी से दबाने के लिए है जो वह करता है। यदि कोई 600 गेम टिक में नहीं जीतता है, तो कार्ड कचरे के ढेर में डूबने लगता है, जो एक बटन भी दबा सकता है। दूसरे शब्दों में, आपको अपने बटन को दुश्मनों से, अपने आस-पास की दुनिया और कचरे के ढेर (vitally, हाँ) से बचाने की जरूरत है। प्रत्येक खिलाड़ी को 5 जीवन दिए गए, खेल 5 से 9 राउंड तक चला, जबकि किसी ने अपने जीवन को समाप्त नहीं किया। प्रत्येक राउंड एक यादृच्छिक मानचित्र और कारों पर आयोजित किया गया था, दोनों प्रतिभागियों के लिए समान। कुल में 6 अलग-अलग कार्ड और 3 प्रकार की कारें थीं - कुल 18 अलग-अलग संयोजन।

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

अधिक पूर्ण नियम यहां देखे जा सकते हैं । और फाइनल गेम्स यहां देखें ।

सामान्य समाधान विवरण

अधिकांश बॉट लेखन प्रतियोगिताएं बहुत समान हैं: इसमें टिकों की एक परिमित संख्या होती है (एक दौर के लिए लगभग 1,500 अधिकतम), संभावित कार्यों की एक सीमित संख्या होती है, आपको अपने विरोधियों से बेहतर होने के लिए कार्यों का क्रम चुनने की आवश्यकता होती है। थोड़ी देर बाद हम बेहतर होने के लिए क्या करेंगे, इस पर वापस लौट आएंगे, लेकिन अब हम यह पता लगाएंगे कि मुख्य समस्या से कैसे निपटें - बड़ी संख्या में विकल्प: शुरुआत में हमारे पास एक प्रारंभिक अवस्था होती है, फिर प्रत्येक मशीन तीन अलग-अलग तरीकों से आगे बढ़ सकती है, जो दो कारों के लिए हमें 9 अलग-अलग संयोजन देता है, 1500 वीं चाल से यह 9 ^ 1500 अलग-अलग संयोजन होगा ... जो हम यूनिवर्स के अस्तित्व के दौरान उन्हें छांटने के लिए प्रबंधित करने की योजना की तुलना में थोड़ा अधिक है।

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

एल्गोरिथ्म चुनते समय, आपको विचार करना चाहिए:

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

इस प्रतियोगिता में, 1 टिक ने लगभग 10-13ms (पूरे खेल के लिए 2 मिनट) दिए। इस समय के दौरान, बॉट को डेटा पढ़ना, निर्णय करना और स्थानांतरित करने के लिए एक कमांड भेजना था। यह लगभग 500-1000 चालों को प्रोत्साहित करने के लिए पर्याप्त था। सभी राज्यों में Iterate। सबसे सरल खोज एल्गोरिदम तीन आंदोलन विकल्पों की तुलना की तरह लग सकता है: "50 टिक बाएं जाएं", "50 टिक सही जाएं", "50 टिक क्लिक स्टॉप"। और कोई फर्क नहीं पड़ता कि यह कितना सरल लगता है, यह विजेता के निर्णय से बहुत दूर नहीं है।

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

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

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

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

प्रश्न: क्या सिमुलेशन के बिना ऐसा करना संभव है?
एक: हाँ, आप समाधान पर निर्णय का उपयोग कर सकते हैं (निर्णय पेड़ों, ifs का एक गुच्छा, आदि)। हेयिस्टिक्स पर एआई आर्किटेक्चर के साथ एक अच्छा लेख है ।

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

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

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

सिमुलेशन

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

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

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

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

खोज और एक विरोधी की भविष्यवाणी के लिए एल्गोरिदम

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

व्लादिमीर किसेलेव (वल्देमार) 4 वाँ स्थान

समाधान स्थान की खोज के लिए एक यादृच्छिक खोज (मोंटे कार्लो) का उपयोग किया गया था। एल्गोरिथ्म इस प्रकार है:

1. हम 60 टिक्स - यादृच्छिक डेटा के लिए जीनोम - क्रियाओं का एक क्रम (बाएं, दाएं, स्टॉप) शुरू करते हैं।
2. सबसे अच्छा जीनोम मिला
3. किसी एक क्रिया को बेतरतीब ढंग से बदलना
4. मूल्यांकन फ़ंक्शन का उपयोग करके हमें एक संख्या मिलती है - एक संकेतक जो कि नया जीनोम कितना अच्छा है
5. यदि आपको एक बेहतर समाधान मिलता है, तो सबसे अच्छा समाधान अपडेट करें।
6. चरण 2 से फिर से दोहराएं

मेरे सिम्युलेटर ने 1 सेकंड में दुनिया के ~ 100k सिमुलेशन का उत्पादन किया, यह देखते हुए कि प्रति टिक की औसत ~ 12ms है, हमें प्रति टिक 1200 कार्रवाई मिलती है। यही है, 1 टिक में हम लगभग 20 बार पूर्ण चक्र के माध्यम से जाने का प्रबंधन करते हैं।

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

यह उन तकनीकों पर ध्यान दिया जाना चाहिए जिन्होंने एल्गोरिथ्म की गुणवत्ता में काफी सुधार किया है:

• हम केवल पहली टिक पर यादृच्छिक आरंभ करते हैं, बाकी समय हम 1 चाल की शिफ्ट के साथ पाए जाने वाले सर्वोत्तम समाधान का पुन: उपयोग करते हैं (2 टिक पर कार्रवाई 1 पर स्थानांतरित की जाती है, आदि, एक यादृच्छिक कार्रवाई अंत में जोड़ दी जाती है)। यह खोज की गुणवत्ता में बहुत सुधार करता है, क्योंकि अन्यथा एल्गोरिथ्म "भूल जाता है" कि यह आखिरी टिक में क्या करने जा रहा था और विभिन्न दिशाओं में संवेदनहीन झटके देता है।
• पाठ्यक्रम की शुरुआत में, हम अधिक से अधिक तीव्र परिवर्तन करते हैं (हम एक के बजाय जीनोम 2 या 3 बार बदलते हैं) स्थानीय अधिकतम (तापमान अनुरूपण की विधि में तापमान की समानता) को तोड़ने की उम्मीद में।
  तीव्रता को मैन्युअल रूप से चुना गया था: पहले 30 पुनरावृत्तियों में 3 परिवर्तन होते हैं, अगले 10 को 2, फिर 1 से।
• बहुत महत्वपूर्ण दुश्मन की कार्रवाई की भविष्यवाणी है। अपने स्वयं के समाधान की खोज करने के लिए समय की कमी के लिए, हम प्रतिद्वंद्वी की ओर से एक यादृच्छिक खोज शुरू करते हैं, 20 पुनरावृत्तियों पर, फिर अपने लिए 50, प्रतिद्वंद्वी के इष्टतम चाल के बारे में जानकारी का उपयोग करते हुए।
  विरोधी के सर्वश्रेष्ठ निर्णय का ऑफसेट के साथ अगले कदम का भी पुन: उपयोग किया जाता है। उसी समय, दुश्मन के समाधान की खोज करते समय, अंतिम चाल से जीनोम का उपयोग मेरे इच्छित कार्यों के रूप में किया जाता है।

प्रतियोगिता के दौरान, उन्होंने स्थानीय विकास के लिए सक्रिय रूप से टूल का इस्तेमाल किया, जिससे बग्स को जल्दी से ढूंढना और रणनीति के कमजोर बिंदुओं पर ध्यान केंद्रित करना संभव हो गया:

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

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

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

अलेक्जेंडर किसेलेव (मोर्टिडो) तीसरा स्थान

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

हम 40 नंबरों की एक सरणी के साथ समाधान को एन्कोड करते हैं, जहां -1, 0, और 1 , और मूवमेंट्स के अनुरूप हैं।

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

Valdemar:
दिलचस्प है, इस चिप ने मेरे लिए खेल खराब कर दिया। यह पता चला कि पहले के मुकाबले 20-30ms खर्च करना हमेशा बेहतर होता है, और अंत में 60

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

समाधान की खोज स्वयं और प्रतिद्वंद्वी दोनों के लिए समान थी:

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

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

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

अंतिम संस्करण में, खंडों में यादृच्छिक निर्णय उत्पन्न किए गए, जिन्होंने एक ही स्थान पर "मरोड़ते" समाधानों को बाहर रखा:

1. रैंडम टीम चुनी गई
2. समाधान की पूरी लंबाई के लिए (40 चाल)
   
   1. हम सेल में वर्तमान कमांड लिखते हैं
   2. 10% की संभावना के साथ हम वर्तमान टीम को यादृच्छिक में बदलते हैं

एक समान तकनीक के अनुसार, एक उत्परिवर्तन भी हुआ - समाधान के एक यादृच्छिक खंड को एक यादृच्छिक कमांड के साथ बदल दिया गया। क्रॉसिंग उस बिंदु को चुनकर किया गया था जिसमें निर्णय 1 माता-पिता से लिया गया था, और 2 से बाद में।

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

Valdemar:
1 , , .

Commandos:
— - .
— , . , … , . " ”. -.

(Commandos) 1

( ), n m . 3^2=9 . m + n 40 .

:

 |----------- n  -----------|---------- m  --------| |   ...   |   ...   | 

: , , . ( ).

n m , . , .

:

1. , ( , ):
   
   • , , , .
   • , , . . . , , , .
   • . ; ( ).
2. n m . , .1, , . - ( ) , — , ;
3. . , — . , ( ).

Valdemar:
, 2 . . , .

mortido:
! , . . , 2 , 40-60 . , 3 .
n + m == const ?

. n + m != const , . , . - .

(Valdemar) 4

, . , ( , , ..) [0..1].
. : , .
, , : , .

, :

• — 70 180 ( : ).
  , .
• 0..500
• — [2pi, pi/4] [0, 1]
• — , ( ), ( , , )
• — , , , .
  , , .
• — . .
• Y — .

, 2 , .

.

:

• “” ,
• “ ” , , .

mortido:
, .. , .

Commandos:
, . -

(mortido) 3

, chipmunk. . , , , , . .

3 .

, ( , , ):

• . , , ( , );
• , — , ; , 1 ;
• ;
• ( , );
• ( “+”, “-”);
  - ( “+”, “-”); , , , ;
  30 , , ( );
• , .

, , (, , )

Valdemar:
. , “ , , ” , ( ..) .

, , . .

Commandos:
, , “”… ? , “” .

(Commandos) 1

SquaredWheelsBuggy , .. , . Buggy , , ( /).
:

1. ;
2. ; — , , 1 0; .. ;
3. . ; 10 ( );
4. ( , );
5. (, );
6. — - , ;
7. / ; , — ; .

1-5 , . 2 “ ”.

Valdemar:
, . , .

mortido:
, 10 .

IF'

(Valdemar) 4

, if'. 3 , , . , , -.
: , “” — , - , ( , ) — .

:

• . , .
• — , .
• . “ ” .
  , , .
  , , .

, : . , , if' .

mortido:
, . .

Commandos:
if'. , , … , , .

(mortido) 3

- .

3 . . . “”, . , , .

, “” . . , , , - . . , , .. .

, , , , , . … . - — , ( , ).

Valdemar:
, . . “” , if'. , — .

, + . , .

Commandos:
… , - — , , . , , .

(Commandos) 1

. (, , ). ( ) /.

pill carcass map , , ( ). island map, , .

island hole buggy. / , , ( ). — . , , . SquaredWheelBuggy . , , , . , … , , .

(Pill map, Bus) , ( / 100% ).

pill hubble map. , ( ), . .

— , ...

, . , . ( ).

Valdemar:
, — . , .

mortido:
, “” .

Valdemar:
. , . ( ) .
. “”, , , , :)
, mailru , .

mortido:
: , … , , ( ). , 3 , , … .

Commandos:
- , . , , , . … . — , .
— ++. . , . 1 -.

, . , . , , .

Mail.Ru Group .

Valdemar
mortido