खेल स्क्रैबल के लिए चाल पीढ़ी एल्गोरिथ्म

शुभ दिन, हेब्र!

इस लेख में, मैं बात करूंगा कि मैंने स्क्रैबल के खेल के लिए कृत्रिम बुद्धि कैसे बनाई। कट के तहत विवरण।

अंडमुख

स्क्रैबल - विश्व प्रसिद्ध खेल स्क्रैबल का एक घरेलू एनालॉग - एक बोर्ड गेम जिसे 2 से 4 लोगों द्वारा खेला जा सकता है, खेल के मैदान में अपने पत्रों से शब्दों को बाहर करना। खेल के मैदान में 15 x 15 होते हैं, यह 225 कोशिकाएं होती हैं, जिस पर खेल में भाग लेने वाले शब्द बनाते हैं। प्रत्येक रचित शब्द क्षेत्र में अक्षरों और कोशिकाओं के मूल्य के आधार पर अंक अर्जित करता है।

स्क्रैबल गेम फ़ील्ड इस तरह दिखता है:


चित्र 1. खेल के लिए मैदान

बुनियादी नियम

आमतौर पर खेल शुरू होने से पहले खिलाड़ियों द्वारा नियमों पर बातचीत की जाती है, लेकिन खेल के कुछ सामान्य रूप से स्वीकृत नियम हैं:

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

पहला कदम

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

हम दो परिभाषाएँ प्रस्तुत करते हैं:
किसी शब्द का उपसर्ग किसी शब्द के अक्षरों का लगातार सेट होता है जो किसी शब्द के पहले अक्षर से शुरू होता है लेकिन अंतिम में शामिल नहीं होता है।

एक शब्द प्रत्यय किसी शब्द के अंतिम अक्षर के साथ समाप्त होने वाले शब्द के अक्षरों का लगातार सेट होता है, लेकिन पहले सहित नहीं।

लंगर अंक

चित्रा 2. प्रश्न में पंक्ति

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


चित्रा 3. लंगर अंक

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


चित्रा 4. उपसर्ग पत्रों की संभावित संख्या

एक पंक्ति में शब्द खोजने के लिए एल्गोरिथ्म

प्रत्येक कोशिका जो लंगर बिंदु है, उसके लिए हम सभी संभावित शब्दों की तलाश करते हैं:

1. किसी दिए गए एंकर बिंदु से जुड़े सभी संभावित उपसर्गों को ढूंढें जो एंकर बिंदु के लिए निर्दिष्ट संभावित उपसर्ग लंबाई को संतुष्ट करते हैं।
2. ऊपर दिए गए पैराग्राफ में पाए जाने वाले प्रत्येक उपसर्ग के लिए, सभी उपयुक्त प्रत्ययों को खोजें, जो कि उपसर्ग के साथ मिलकर शब्दकोश से एक शब्द बनाएंगे। मैदान पर खिलाड़ी के अक्षरों या अक्षरों का उपयोग करके प्रत्ययों का निर्माण किया जाता है।

उपसर्ग शब्द में या तो खिलाड़ी के हाथ की कोशिकाएँ होंगी या बोर्ड पर पहले से रखी गई कोशिकाएँ होंगी, लेकिन एक ही समय में नहीं।

अब, मैदान पर सभी शब्दों को खोजने का एक तरीका होने से, आप सीधे इस कदम को उत्पन्न करने के लिए एल्गोरिदम के वर्णन पर जा सकते हैं।

स्ट्रोक जेनरेशन एल्गोरिदम

मैंने तीन चाल पीढ़ी के एल्गोरिदम को चुना: अधिकतम मूल्य चयन एल्गोरिथ्म, संपूर्ण खोज विधि और अल्फा-बीटा क्लिपिंग विधि।

अधिकतम मूल्य चयन एल्गोरिथ्म

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

इस एल्गोरिथ्म की मुख्य समस्या यह है कि शब्दों का परिणामी सेट आवश्यक रूप से इस स्थिति में सबसे अच्छा कदम नहीं होगा कि वह कितने अंक लाएगा।

पूर्ण पाशविक बल विधि

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

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

अल्फा बीटा कतरन विधि

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

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

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

परिणाम

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

औसत पीढ़ी का समय नीचे दिए गए चित्र में दिखाया गया है:

चित्रा 5. जनरेशन टाइम चार्ट

शोध के नमूने में खिलाड़ियों को दिखने वाले अक्षरों के 100 अलग-अलग क्रम शामिल थे (स्टैक सिद्धांत के अनुसार)। परिणामस्वरूप, हाथ और पदों पर पत्रों के लगभग 1,500 विभिन्न संयोजनों की जांच की गई।

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

यह करें

दुर्भाग्य से, निम्नलिखित बिंदुओं को विचार से बाहर रखा गया था:

• दुर्लभ पत्र संयोजन विश्लेषण
• चाल के बाद शेष रहे अक्षरों का विश्लेषण
• आगे की दुश्मन क्रियाओं का विश्लेषण
• एक स्ट्रोक को छोड़ते समय बदलने के लिए पत्र

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

साहित्य

• स्क्रैबल पर पीटर नॉरविग द्वारा व्याख्यान । इस स्रोत से सबसे बड़ी संख्या में विचार उधार लिए गए हैं।
• खेल के नियम
• पूर्ण विकि गणना
• द ग्रेट थॉमस कॉर्मेन: एल्गोरिथम। निर्माण और विश्लेषण।
• अल्फा बीटा कतरन

आपका ध्यान के लिए धन्यवाद!