जब मैंने बॉक्सवर्ल्ड (सोकोबैन जैसा खेल) खेलना शुरू किया, तो पहले 20-30 स्तर दिलचस्प थे, लेकिन फिर जटिलता और एकरूपता सामने आने लगी और मैंने बॉट लिखने का फैसला किया। मैं समाधान के लिए एक कठिन एल्गोरिथ्म के साथ नहीं आ सका, इसलिए मैंने bruteforce लिखा। C # में लिखा है।
पहले संस्करण में, मैंने लोडर (रोबोट) के आंदोलनों को हल किया। लूपिंग से सुरक्षा के लिए पुन: गहराई से छंटनी की गई, सभी पारित विकल्पों को एक सरणी में रखा गया। उन्होंने यह संकेत देते हुए एक स्ट्रिंग के रूप में निर्णय जारी किया कि किस खेल में बटन दबाना है। मैंने इस क्रम को MacroExpress प्रोग्राम में डाउनलोड किया, और इसने पहले ही गेम विंडो पर क्लिक भेज दिए। क्लिक भेजने के बीच के ठहराव को समायोजित करके, आप एक सुविधाजनक गति से स्तरों के पारित होने को देख सकते हैं।
बॉट ने पहले कुछ स्तरों का फैसला किया और अगले कुछ दिनों के लिए अटक गया। यह स्तर पिछले एक से 2 गुना अधिक था, लेकिन समाधान खोजने का समय तेजी से बढ़ गया। इसलिए एक उत्तर की प्रतीक्षा किए बिना, मैंने दूसरा संस्करण लिखना शुरू किया। रोबोट के आंदोलनों को बक्से के आंदोलनों से बदल दिया गया था, अर्थात। अब एक बॉक्स से दूसरे बॉक्स में रोबोट पथ की चालों को संग्रहीत करने की आवश्यकता नहीं है। प्रत्येक मोड़ पर, मैंने यह निर्धारित किया कि अब कौन से बक्से को बॉक्स मिल सकता है और धक्का देने का कौन सा तरीका है।
फिर बॉट ने अगले कुछ स्तरों का फैसला किया और फिर से अटक गया। तब कुछ और संस्करण थे:
- पुनरावृत्ति की गहराई पर प्रतिबंध जोड़ा, यह मानते हुए कि बक्से के 100 से कम आंदोलनों में अधिकांश स्तरों को हल किया जा सकता है;
- मानचित्र पर स्थिर मृत-अंत स्थानों को चिह्नित किया जाता है, उदाहरण के लिए, एक कोने या पहली दीवार के साथ पहली पंक्ति, क्योंकि फिर वहां से बॉक्स को बाहर निकालना असंभव होगा;
- पाठ्यक्रम का एक सरल विश्लेषण जोड़ा और स्पष्ट गतिशील गतिरोध को त्याग दिया जैसे कि 4 बक्से के एक वर्ग को स्थानांतरित करना;
- सभी पिछले चालों के निर्देशांक के भंडारण को उनके हैश के भंडारण से बदल दिया गया था, ताकि यह मेमोरी में फिट हो जाए और खोज के लिए तेज़ हो;
इस सबने कई और स्तरों को आगे बढ़ाना संभव बना दिया, लेकिन यह स्पष्ट हो गया कि प्रत्येक स्तर के साथ समाधानों की जटिलता बहुत बढ़ गई है। फिर मैंने सबसे बड़े स्तर को चुना - 86. खैर, अगर बॉट इसे हल करता है, तो बाकी को आसानी से संभाला जाएगा।
तो, स्तर 86।
इसमें 46 बॉक्स और 156 फील्ड सेल शामिल हैं। एक ही समय में, 40 कोशिकाएं स्टैटिक डेड एंड हैं, कुल 116 सेल हैं, जिस पर आप बॉक्स को स्थानांतरित कर सकते हैं। इसलिए, विभिन्न विकल्पों की संख्या 116 ^ 46 = 92271483792519010208299118408158326223759549834325815837590806767395615673894137078445244416 से अधिक नहीं होगी। हाँ, यह 95 अंकों की संख्या है। यह ~ = 9.2e + 94 है। इस मामले में, अधिकतम चालों का कोई मतलब नहीं है, क्योंकि यह अनुमान और भी बड़ा हो गया है: मान लें कि अधिकतम चाल = 100 है, और औसतन प्रत्येक बॉक्स को चार में से कम से कम एक दिशा में धकेला जा सकता है, फिर विकल्पों की संख्या अधिक नहीं होगी (46 * 1) ^ 100 ~ = 1.9e + 166 ।
यकृत जोड़:
- स्टैटिक डेड एंड
यह स्पष्ट है कि यदि आप बॉक्स को लाल मार्कर से चिह्नित किसी भी स्थान पर धकेलते हैं, तो इसे दीवार से दूर फाड़कर गंतव्य तक पहुंचाना असंभव होगा। मैं मानचित्र पर ऐसी जगहों को पहले से चिह्नित करता हूं और बॉट छांटने की प्रक्रिया में ऐसी हरकत नहीं करता।
- गतिशील मृत
यह स्पष्ट है कि यदि आप 4 दराज वर्ग (दराज और दीवारों के साथ विभिन्न संयोजनों में) को स्थानांतरित करते हैं, तो उन्हें एक-दूसरे से अलग करना असंभव होगा। बॉट प्रत्येक चाल का विश्लेषण करता है और इस तरह के वर्ग के लिए अग्रणी चाल नहीं बनाता है।
अधिक जटिल अभी तक सामने नहीं आया है।
बेशक, गतिशील डेड एंड्स के कटने के कारण वास्तविक विकल्प पहले अनुमान की तुलना में बहुत छोटे होंगे, संभवतः परिमाण के कई आदेशों द्वारा। लेकिन अगर आप इस संख्या (92271483792519010208299118408158326223223759549834) के आधे ऑर्डर लेते हैं और प्रत्येक चाल की स्थिति को केवल एक बाइट में संग्रहीत करते हैं, तो आपको 83920425634022658603 टेराबाइट्स की आवश्यकता होगी।
यह तब था जब मुझे एहसास हुआ कि "अभी भी प्रतीक्षा करें और बॉट सभी चालों के माध्यम से छाँटेगा" जैसा कि पहले स्तरों पर यह काम नहीं करेगा। एल्गोरिथ्म में मौलिक रूप से कुछ बदलना, प्रत्येक मोड़ पर एक अधिक जटिल और लंबा विश्लेषण करना आवश्यक है, लेकिन विकल्पों के बड़े उपशीर्षक को काट दें। लेकिन मुझे नहीं पता कि यह कैसे करना है ... शायद आप मुझे सलाह दे सकते हैं? रेखांकन, चींटी एल्गोरिदम, तंत्रिका नेटवर्क के क्षेत्र से कुछ तकनीकों का उपयोग करें?