गोमोकू की जीत की रणनीति - 35 चाल

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

पूर्ण समाधान का प्रदर्शन - यहां - आप खेल सकते हैं और सबसे लंबे विकल्प ढूंढ सकते हैं। कार्यक्रम हमेशा जीतता है और इस पर खर्च करता है 35 से अधिक नहीं। आवेदन के स्रोत कोड, समाधान और लेख के अंत में पार्टियों के उदाहरण।

मैं खेल के नियमों और रणनीति पर ध्यान नहीं दूंगा। इस विषय पर यहां और यहां तक कि निर्णय एल्गोरिदम के बारे में विस्तार से चर्चा की गई।

छोटा विषयांतर

स्मार्टफोन के युग से पहले, टिक-टैक-टो "एक पंक्ति में पांच" (गोमोकू, रेन्जू) स्कूली पाठ के समय के सबसे लोकप्रिय हत्यारों में से एक था। विचार करने के लिए संयोजन उत्तरी अफ्रीका की राष्ट्रीय अर्थव्यवस्था के विकास या तिपतिया घास के फूलों के वर्गीकरण से अधिक दिलचस्प था।

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

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

लेख में दिए गए समाधानों और उदाहरणों में विरोधियों की "सही चाल" के साथ पुस्तक, जो एक जीतने की रणनीति का हिस्सा है, उपयोग किए गए एल्गोरिदम की कमजोरी को प्रदर्शित करता है।

उदाहरण के लिए, आंकड़ा में, मानक गोमोकू नियमों के लिए कार्यक्रम समाधान। अगर व्हाइट के 10 वें मूव g9 के जवाब में ब्लैक j10 के साथ प्रतिक्रिया करता है और फिर j8, तो गेम 45 के बजाय 29 चालों में समाप्त होता है। तब 16 बार और 26 के बाद 17 चालों में ब्लैक के "खतरों के अनुक्रम" के संयोजन से दो बार "नोटिस नहीं" किया गया। सफेद चाल। और अंत में, अगर व्हाइट j12 के बजाय 36 वीं चाल f12 बनाता है, तो वह कम से कम 49 वीं चाल तक पकड़ बनाए रखेगा। निष्पक्षता में, यह कहा जाना चाहिए कि इस उदाहरण में, सभी ब्लैक की चालें व्हाइट को अपने पक्ष में खेल को समाप्त करने का कोई मौका नहीं छोड़ती हैं।

इंटरनेट पर, मुझे एक जीत की रणनीति की खोज के समान काम के लिए कई संदर्भ मिले। पाए गए समाधानों की इष्टतमता का प्रश्न अनसुलझा है। ब्लैक को जीतने के लिए चालों की न्यूनतम संख्या क्या है?

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

बोर्ड पर स्थिति का डिजिटलीकरण करें

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

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

एक स्थिति का मूल्यांकन करने का कार्य प्रत्येक पंक्ति के लिए सभी महत्वपूर्ण आंकड़े निर्धारित करना है। सरलता के लिए, हम 2 बिट्स के साथ लाइन के प्रत्येक सेल का वर्णन करते हैं। पहला बिट भरा हुआ है जब एक सफेद पत्थर स्थापित किया गया है, दूसरा बिट एक काला पत्थर है। प्रत्येक पंक्ति में 15 से अधिक सेल नहीं हैं और 32-बिट पूर्णांक में एन्कोडेड है। इस प्रकार, एक रेखा पर आकृतियों की खोज आकृति के बिट पैटर्न के साथ एक स्लाइडिंग विंडो के माध्यम से लाइन के संख्यात्मक मूल्य की तुलना करने के लिए कम हो जाती है।



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

समरूपता का उपयोग माना जाने वाले पदों की संख्या को काफी कम कर देता है। उदाहरण के लिए, दूसरे कदम के लिए विकल्पों की संख्या 224 से घटाकर 35 कर दी गई है।

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

विकास प्रक्रिया के दौरान, कई कोडिंग एल्गोरिदम पर विचार किया गया था, लेकिन ऊपर वर्णित एक ने स्थिति के आकलन की उच्चतम दर को दिखाया।

स्थिति का मूल्यांकन करें

किसी स्थिति का मूल्यांकन करने के लिए एक महत्वपूर्ण कारक यह है कि विरोधियों ने महत्वपूर्ण टुकड़ों का निर्माण कैसे किया।

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



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



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





एक खुली ट्रिपल - 6 या 7 कोशिकाओं की लंबाई, सबसे बाहरी कोशिकाएं आवश्यक रूप से स्वतंत्र हैं। 6 कोशिकाओं के लिए, चार मध्य में से तीन एक ही रंग के पत्थरों द्वारा कब्जा कर लिया जाता है, एक मुक्त। 7 कोशिकाओं के लिए - एक ही रंग के पत्थरों द्वारा तीन मध्यम लोगों का कब्जा है। अपनी बारी में एक टुकड़ा एक खुला चार बन जाता है अगर प्रतिद्वंद्वी के पास चार या एक खुला तीन नहीं होता है। किसी और के कदम पर, यह एक खतरा पैदा करता है और प्रतिद्वंद्वी को तीनों को बंद करने या प्रतिक्रिया में अपने चार लगाने के लिए मजबूर करता है। 6 वें सेल ट्रिपल में 1 उठाने की चाल और 3 समापन चाल है। 7 वें सेल ट्रिपल में 2 उठाने चालें और केवल 2 समापन चाल हैं। स्थिति रेटिंग में 2 से 4 अंक तक देता है।







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







एक खुला (परिप्रेक्ष्य) ड्यूस - 6 से 7 कोशिकाओं तक लंबा। हमला करते समय, इसे एक खुले तीन में बदल दिया जाता है। स्थिति रेटिंग में 1 या 2 अंक देता है।







एक ही समय में एक प्लग दो या दो से अधिक खतरों पर होता है जिन्हें एक बार में बंद नहीं किया जा सकता है। 3x3 कांटे (दो खुले ट्राइएबल्स), 3x4 (ओपन थ्रीज़ और फोर) और 4x4 फ़ॉर्क (दो ओपन फोर) हैं। फ़ॉर्क्स एक जीत देता है अगर प्रतिद्वंद्वी को अधिक खतरा नहीं है - 3x3 कांटा के लिए चार या एक खुला तीन, या प्रतिद्वंद्वी क्रमिक रूप से कांटा बंद नहीं कर सकता है। बड़े खतरे पैदा करना - 3x3 कांटा के लिए चौकों का एक क्रम।









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

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

रक्षात्मक संयोजन, इसके विपरीत, सफल होता है जब प्रतिद्वंद्वी खतरे पैदा करना बंद कर देता है, या गणना के लिए चाल की सीमा पार हो जाती है। एक रक्षात्मक संयोजन में रक्षात्मक चालें होती हैं या प्रतिद्वंद्वी को अधिक खतरा पैदा करता है।

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

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

हम इसका हल ढूंढ रहे हैं

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

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

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

हम रणनीति की गणना करते हैं

सभी घटक तैयार हैं, हम पहले काले पत्थर को मैदान के केंद्र में रखते हैं, एक समाधान की खोज शुरू करते हैं और ... इस पर, कुछ घंटों के बाद, मेरे लैपटॉप के संसाधन बाहर निकल जाते हैं और मुझे "युद्ध में नहीं, बल्कि युद्ध में" हार को स्वीकार करना पड़ता है।

सच में, मैं अपनी उंगलियों पर कंप्यूटिंग शक्ति डेढ़ सौ कोर Xeon और मुफ्त रैम की टेराबाइट के साथ था। लेकिन, याद रखें कि नब्बे के दशक के मध्य में, एलिस ने 128 एमबी रैम में से प्रत्येक पर केवल 10 SUN SPARCstation 2 का इस्तेमाल किया था, इसने असंगत व्यवहार के लिए पछतावा महसूस किया और जावा मशीन पर रैम की मात्रा को 1 जीबी तक सीमित करने का निर्णय लिया और कार्य के लिए केवल 1 धागा आवंटित किया। प्रोसेसर। यह किसी भी तरह अपने मेगाहर्ट्ज की तुलना में मेरे GHz के लिए क्षतिपूर्ति कर सकता है। साथ ही उन्होंने एल्गोरिदम को ब्राउज़र के लिए जावास्क्रिप्ट में स्थानांतरित करने के लिए काम के अंत में खुद से वादा किया।

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

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





चित्रा 3 में 3 ऊर्ध्वाधर शुरुआत के साथ कोई समस्या नहीं थी। परिणाम समाधान का एक पूरा सेट था। परिणामस्वरूप 4 चाल i8 और j10 के बाद सबसे कठिन स्थिति 31 चालों में हल की गई थी। तब प्रति गेम 35 चालों की लक्ष्य सीमा निर्धारित की गई थी।





निर्णय के लिए विकर्ण से, उन्होंने पारंपरिक रूप से 7 वीं शुरुआत को चुना। चौथी चाल g9 के बाद सबसे कठिन स्थिति उत्पन्न होती है। 6 चाल जी 8 और जी 7 के लिए अनुमेय लंबाई समाधान पाए गए थे।



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

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

7 वें विकर्ण की शुरुआत के बाद दिए गए 35 चालों में निर्णय लिया गया था, कोई भी जीत का जश्न मना सकता है - केंद्र के लिए लड़ाई जीत ली गई थी। आगे अभी भी नियमित कम्प्यूटेशनल काम की एक बड़ी मात्रा थी, रणनीति को पूरा करने के लिए "गैर-इष्टतम" सफेद चाल की गणना। इष्टतम रणनीति की कुल मात्रा में से, इस तरह के परिणाम का जवाब 80% था। सौभाग्य से, वे स्वचालित रूप से 2 वीं चाल के बाद प्रारंभिक गणना पर पूरी तरह से हल हो गए थे, और यह सब कुछ दिनों में इष्टतम रणनीति में जोड़ा गया था।

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

खुद को जाँच रहा है

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

जाँच पूरी होने तक कई बार की गई। एकल-थ्रेडेड मोड में अंतिम त्रुटि मुक्त रन 14 घंटे लग गए। जाँच के दौरान, त्रुटियों को पाया गया और सही किया गया कि संयोजनों की खोज की गहराई में अंतर के कारण उत्पन्न हुई, लंघन चालों के लिए धारणाएं, सममित पदों का दोहराव।

सवाल का जवाब - 35 चालों में निर्णय वास्तव में सबसे इष्टतम है। मेरे शोध के अनुसार, ऊर्ध्वाधर शुरुआत की सबसे लंबी शाखाओं के लिए, 33 चालों की लंबाई के साथ अधिक इष्टतम समाधान खोजना संभव है। लेकिन j9 पर 6 वीं चाल के बाद विकर्ण के लिए, 33 चालों में एक समाधान की खोज में बहुत समय बिताया गया था, ब्लैक के लिए भिन्नता प्रत्येक चरण में 50 चालों तक विस्तारित हुई और कोई फायदा नहीं हुआ। 33 चालों में समाधान की कमी को कठोरता से साबित करना संभव नहीं है, परियोजना के लिए आवंटित समय समाप्त हो गया है और 35 चालों की लक्ष्य सीमा पर रोक लगाने का निर्णय लिया गया।

जावा से जावास्क्रिप्ट में परिवर्तित करें

किसी समस्या के समाधान के प्रकाशन के लिए स्पष्टता की आवश्यकता होती है। ब्राउज़र में सीधे समाधान का उपयोग करने के लिए, यह आवश्यक था:

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

आवेदन वर्गों की सूची:

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

JSON प्रारूप में पूरा समाधान gomoku.json फ़ाइल से डाउनलोड किया जा सकता है । GitHub

पर भंडार में स्रोत । स्पष्टता के लिए, मैं नेक्स्ट पर क्लिक करके प्रदर्शन में प्राप्त सबसे लंबे गेम्स के उदाहरण नीचे दूंगा। विकर्ण पहली फिल्म: खड़ी पहली फिल्म: