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

खेल के नियम

आइए सहमत हैं कि अब से मैं "शोगी" लिखूंगा, लेकिन 5 से 5 फ़ील्ड पर खेल का एक सरलीकृत संस्करण।

आंकड़े

एक नया खेल सीखने के दौरान समझने वाली पहली चीज चालें हैं। शोगी के 10 अलग-अलग आकार हैं। आंकड़ों के पदनाम, उनके नाम और संभावित कदम नीचे तालिका में प्रस्तुत किए गए हैं:

तख्तापलट

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

निर्वहन

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

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

सच है, रीसेट करते समय कई सीमाएँ हैं, लेकिन वे काफी सरल हैं:

• सभी आंकड़े अनियंत्रित रीसेट किए जाते हैं;
• यदि आप तख्तापलट क्षेत्र में एक टुकड़ा छोड़ते हैं, तो यह एक चाल चलने के बाद ही लुढ़क सकता है;
• आप एक मोहरे को एक ऊर्ध्वाधर में नहीं मोड़ सकते हैं जहाँ आपका मोहरा पहले से मौजूद है (टोकन को मोहरा नहीं माना जाता है);
• आप पिछले क्षैतिज को एक मोहरा नहीं छोड़ सकते हैं;
• आप एक चेकमेट के साथ एक मोहरा मोड़ नहीं सकते।

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

चाल और प्रारंभिक प्लेसमेंट की अनुक्रम

खेल 5 कोशिकाओं के साथ एक वर्ग क्षेत्र पर होता है। खेल की शुरुआत में, क्षेत्र इस प्रकार दिखता है:

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

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

खेल प्रोग्रामिंग

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

पेड़ खोजो

खेल के पेड़ों की पूरी खोज

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

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

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

पुनरावृत्ति की एक सीमित गहराई के साथ खेल के पेड़ों की गणना

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

समारोह SearchBestMove ( गहराई : बाइट ; रंग : TColor ) : असली ;
वर
आर , टीएमपीआर : वास्तविक ;
मैं , एन : शब्द ;
चाल : तमोव्स ;
शुरू करना
अगर गहराई = 0 तो
r : = एस्टीमेटोस
अन्यथा
शुरू करना
वास्तविक : = - 100000 ;
N : = GenerateAllMoves ( मूव्स ) ;
मैं के लिए : = 1 से एन करते हैं
शुरू करना
हम मूव करते हैं मूव्स [ i ] ;
tmpr : = - SearchBestMove ( गहराई - 1 , opcolor ( रंग ) ) ;
चाल को रद्द करें मूव्स [ i ] ;
अगर tmpr> r तब
r : = tmpr ;
अंत ;
अंत ;
SearchBestMove : = r ;
अंत ;

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

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

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

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

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

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

छंटनी की चाल

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

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

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

समारोह AB ( POS : TRPosition ; रंग : TColor ; गहराई : बाइट ; ए , बी : वास्तविक ) : वास्तविक ;
वर
चाल : तमोव्स ;
मैं , मूवेस्काउंट : बाइट ;
OLDPos : TRPosition ;
शुरू करना
MovesCount : = 0 ;
अगर ( गहराई = 0 ) या मेट ( पीओएस । हैंडसेंट , पीओएस हैंडगोट , रंग ) तब
ए : = एस्टीमेटोस
अन्यथा
शुरू करना
अगर रंग = भेजा तो
MovesCount : = GenerateMoves ( पीओएस बोर्ड , रंग , पीओएस । हैंडसेंट , मूव्स )
अन्यथा
MovesCount : = GenerateMoves ( POS । बोर्ड , रंग , POS । हैंडगोट , मूव्स ) ;

i : = 1 से MovesCount करते हैं
शुरू करना
अगर A> = B तब
तोड़;
OLDPOS : = POS ;
मेकमोव ( पीओएस , कलर , मूव्स [ i ] ) ;
चलती है [ i ] । r : = - AB ( POS , opcolor ( color ) , गहराई - 1 , - B , - A ) ;
POS : = OLDPos ;
अगर मूव्स [ i ] । r > ए तो
ए : = चालें [ i ] । आर ;
अंत ;
अंत ;
एबी : = ए ;
अंत ;

अंतिम कार्यान्वयन

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