खेल Balda में शब्द खोजने के लिए एल्गोरिथ्म और रणनीति

एक बार जब हबेरा में मुझे बलदा गेम में शब्द खोज एल्गोरिथ्म के बारे में एक लेख मिला: habrahabr.ru/post/207734 मैं खुद रोबोट बलदा 2 सॉल्वर का लेखक हूं, जिसने वर्षों से बलदा खेल में कई ऑनलाइन खिलाड़ियों के बीच लोकप्रियता हासिल की है। और मैं अपने अनुभव को साझा करना चाहूंगा और बुलडोजर के खेल में एक अद्वितीय एल्गोरिथ्म के बारे में बताऊंगा, जिसका उपयोग अभी तक किसी ने नहीं किया है।

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

अधिक जटिल उपसर्ग वृक्ष ("टर्बो मोड") को शामिल करना भी संभव है, प्रतीक "डमी" के साथ। इस स्थिति में, टर्मिनल नोड में सभी अक्षर होते हैं जिन्हें डमी में डाला जा सकता है। उदाहरण के लिए, हमने K * T की यात्रा की, और एक टर्मिनल नोड से मुलाकात की। इसमें दो अक्षर "O" और "And" होंगे। सेल "O" में KOT शब्द का लिंक होगा, और KIT शब्द के "I" में। नतीजतन, डमी आपको खाली कोशिकाओं पर प्रत्येक पुनरावृत्ति में 32 अक्षरों की थकावट से छुटकारा पाने की अनुमति देता है। लेकिन यह उपसर्ग शब्दकोश के आकार को लगभग 5 गुना बढ़ा देता है। अपने शुद्ध रूप में, यह 4 गुना का त्वरण देता है (यदि यह मेमोरी नहीं बदलता है), लेकिन शब्दों की खोज के अलावा, मैं विश्लेषण पर भी समय बिताता हूं, इसलिए कुल त्वरण केवल 1.5 गुना है।

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

कई पूछ सकते हैं कि और भी तेज क्यों है। यदि सबसे सरल और धीमी एल्गोरिदम भी मिलीसेकंड में शब्दों के लिए देखें। ये सवाल केवल उन प्रोग्रामर के लिए ही पैदा हो सकते हैं, जिन्होंने "चैंपियन" के खिलाफ खेलने की कोशिश नहीं की है। उनके कार्यक्रम कुछ कदम आगे सोचने में सक्षम हैं। इसका मतलब यह है कि कार्यक्रमों को केवल शब्दों की खोज नहीं करनी चाहिए, बल्कि रणनीति भी लागू करनी चाहिए। और सभी तार्किक खेलों के लिए सबसे सार्वभौमिक रणनीति न्यूनतम है। यह क्या है: अच्छी तरह से यहाँ या यहाँ वर्णित है । और मिनिमैक्स के उपयोग का मतलब है कि आपको बहुत सारे वर्चुअल मूव करने की आवश्यकता है। उदाहरण के लिए, यदि प्रत्येक खिलाड़ी को प्रत्येक मोड़ पर औसतन 100 शब्द मिलते हैं, तो 100 ^ (4-1) = 1,000,000 खोजों के लिए खेल को विकसित करने के लिए सभी विकल्पों को देखने की आवश्यकता होगी 4 आगे। यदि आपका प्रोग्राम 1ms में सभी शब्दों को खोज सकता है, तो यह गेम को 16 मिनट में 4 चालों की जाँच करेगा! और एक नियम के रूप में, चाल पर प्रतिबिंब के लिए 2 मिनट दिए जाते हैं। अब आप समझ गए हैं कि आपको एक त्वरित खोज की आवश्यकता क्यों है। मेरा कार्यक्रम कुछ सेकंड में 8-10 चालों के लिए खेल का विश्लेषण कर सकता है।

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

अल्फा बीटा क्लिपिंग द्वारा एक दूसरा महत्वपूर्ण त्वरण दिया गया है।

इससे पहले, मैंने मानक एल्गोरिदम का उल्लेख किया था जिसे आप हमेशा अपने साथ पा सकते हैं और परिचित कर सकते हैं। और अब मैं अपना "आविष्कार" लिखूंगा। यह आभासी चालों के वृक्ष के निर्माण की प्रक्रिया में शब्द खोज के अनुकूलन की चिंता करता है। यहाँ देखो। हमेशा की तरह, हम बुलडोजर में एक खोज ट्री बनाते हैं:
1. सभी शब्दों का पता लगाएं।
2. हम सभी शब्दों को खेल मैदान पर बारी-बारी से डालते हैं।
3. हम 1 बिंदु पर पुनरावर्ती पास करते हैं। यदि हम बहुत गहराई से चढ़ते हैं तो हम पुनरावृत्ति से लौटते हैं।

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

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

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

अंत में, मैं कहना चाहता हूं कि मिनिमैक्स विश्लेषण दृढ़ता से शब्दकोश की सटीकता पर निर्भर करता है। इसलिए, यह उस शब्दकोश का आकार नहीं है जो मायने रखता है, लेकिन खेल पोर्टल के शब्दकोश के लिए इसका पत्राचार।