एक टॉवर रोबोट कैसे इकट्ठे हुए की कथा

मुझे तुरंत कहना होगा कि पोस्ट के शीर्षक में "टावरों" के तहत पहेली खेल " सरोवर टावर्स" है, जो साइट bashni.org पर स्थित है, जिसका अस्तित्व मैंने हैबरपोस्ट से सीखा है कि एक टॉवर कैसे बनाया जाए ।

यदि आप इस गेम और इस साइट से परिचित हैं, तो कोई और स्पष्टीकरण की आवश्यकता नहीं है, यदि नहीं, तो आप दोनों लिंक पर जाकर समझ सकते हैं कि यह किस बारे में है।

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

प्रविष्टि

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

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

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

एक अतिरिक्त प्रोत्साहन तथ्य यह था कि खेल के निर्माता, पापाबाबाडिओप हब पर प्रसिद्ध थे दावा किया कि उसने पहले से ही मिनटों के एक मामले में अधिकांश टावरों को हल करने में सक्षम एक बॉट लिखा था।

सामान्य तौर पर, इस मामले में देरी किए बिना, मैंने कोड लिखना शुरू कर दिया।

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

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

यदि इस जगह के पाठक ने अभी तक कम से कम धाराप्रवाह खेल के नियमों को नहीं पढ़ा है, तो आपको इसे इस अद्भुत पृष्ठ पर करना चाहिए, जहां सब कुछ बहुत सुलभ चित्रित है, और यहां तक ​​कि एक स्पष्ट एनीमेशन उदाहरण भी है। सौभाग्य से, ये नियम बहुत सरल और संक्षिप्त हैं।
क्या आप परिचित हैं? महान, आगे बढ़ें।

पहला पैनकेक गांठदार है

कार्यक्रम का पहला संस्करण बहुत ही आदिम था, और बस बाएं से दाएं (स्तंभों के क्रम में) सभी संभावित समाधानों की जांच की। प्रारंभिक लेआउट लिया गया था, पहले कॉलम की खोज की गई थी, जिसने नियमों द्वारा अनुमति दी गई चाल को बनाने की अनुमति दी थी, यह कदम (वस्तुतः) बनाया गया था, फिर एल्गोरिथ्म के पहले बिंदु पर एक पुनरावर्ती वापसी हुई थी, केवल अब टॉवर की प्रारंभिक स्थिति से आधार नहीं लिया गया था, लेकिन किए गए कदम के बाद क्या हुआ।

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

बुनियादी अनुकूलन में से एक चाल की शाखाओं की काट था जिसकी लंबाई पहले से ही पाए गए समाधानों से अधिक थी, जो काफी स्पष्ट है, क्योंकि ऐसी शाखाओं से कोई फायदा नहीं।

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

स्क्रिप्ट ने "अफ्रीकी" टावरों (कठिनाई के न्यूनतम स्तर) पर काफी अच्छी तरह से काम किया, 1-2 मिनट में एक समाधान ढूंढा, और कभी-कभी कम। हालांकि, "हनोई" पर उन्हें पहले ही 15-30 मिनट की देरी हो गई थी, और "सरोवर" के लिए मैं भी लेने से डर रहा था।

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

हालांकि, यदि आप इस अनुकूलन को पूरी तरह से अक्षम कर देते हैं, तो पहेली को सुलझाने का समय छत के माध्यम से चला गया, और यहां तक ​​कि अफ्रीकी टावरों के लिए यह 15 मिनट से अधिक हो गया।

कुछ बदलना जरूरी था।

हैंडलिंग में त्रुटि

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

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

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

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

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

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

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

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

रोबोटों की जय! सभी लोगों को मार डालो!

अंतिम परिणाम मेरी सभी अपेक्षाओं को पार कर गया। स्क्रिप्ट ने सेकंडों (औसतन 1-3) के मामले में अधिकांश अफ्रीकी टावरों को हल किया, हनोई - 10 सेकंड के भीतर, रूसी (सरोव) - ज्यादातर मामलों में 30 सेकंड से 10 मिनट तक, और सबसे कठिन लेआउट के लिए 20-30 मिनट कि मैं "जटिल" लेआउट के पहले सौ सहित मिले।

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

खैर, निश्चित रूप से, समाधान खोजने की गति के मामले में, लोहे का दिमाग मानव दिमाग से बहुत आगे है।

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

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

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

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

आप केवल प्रतियोगिता की अवधारणा या उनके परिणामों के संबंध पर पुनर्विचार कर सकते हैं।

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

PPS I लगभग भूल गया :) pastebin.com/AJyR2E71 - यहाँ कोड है