लागू होने पर न्यूनतम रूप से मिनीमैक्स एल्गोरिदम को लागू करने के लिए प्रत्येक बोर्ड की स्थिति के लिए सर्वोत्तम खेल (एक मिनीमैक्स अर्थ में) की गणना करना पड़ता है भविष्य में भागो। अल्फा बीटा-प्रुनिंग अनावश्यक गणनाओं पर वापस कटौती करने में मदद करता है क्योंकि यदि आप जानते हैं कि आप कभी भी एक निश्चित कदम नहीं खेलेंगे तो आपको उस कदम को चलाने के मूल्य की गणना करने की आवश्यकता नहीं है।
कुछ खेलों के साथ किसी दिए गए बोर्ड पर सबसे अच्छा खेल समय पर उस समय बोर्ड की स्थिति द्वारा निर्धारित किया जा सकता है। शतरंज इस तरह है, इसलिए जाना है और कुछ अन्य खेल भी हैं। मुख्य अहसास यह है कि एक बार जब आप उस राज्य में पहुंचने के बाद किसी विशेष गेम स्थिति में पहुंचे तो वास्तव में कोई फर्क नहीं पड़ता (एक न्यूनतम दृष्टिकोण से)।
विशेष रूप से शब्द के शतरंज की भावना में एक पारदर्शिता तब होती है जब आप प्रारंभिक स्थिति से अंत स्थिति तक पहुंचने के लिए 2 अलग-अलग पथ लेते हैं।
ट्रांसपोजिशन टेबल आपको सबसे अच्छी स्थिति की गणना करने के लिए अनुकूलित करने देता है जब आप उन परिस्थितियों का सामना करते हैं जहां बोर्ड में अलग-अलग नाटकों का परिणाम होता है। अनिवार्य रूप से एक बार जब आप एक विशिष्ट बोर्ड स्थिति प्राप्त करते हैं तो आप बस उस स्थिति में अपनी न्यूनतम सीमा गणना के परिणाम को ट्रांसपोजिशन तालिका में संग्रहीत करते हैं। इसका मतलब यह है कि बाद में यदि चाल की कुछ अन्य अलग-अलग सूची उसी बोर्ड पर आती है तो अचानक आपको उस बोर्ड पर मिनीमैक्स को पूरी तरह से पुन: गणना करने की आवश्यकता नहीं होती है क्योंकि आप पहले ही ऐसा कर चुके हैं और आप इसे देख सकते हैं पारदर्शिता तालिका।
तो यदि खिलाड़ियों को एक ही बोर्ड की स्थिति में आने वाले कई तरीके हैं तो खेल के पेड़ की उस शाखा को नीचे डुप्लिकेट करने की आवश्यकता नहीं है यदि आप उस गणना के परिणामों को सहेजने में सक्षम हैं किसी न किसी तरह। इसे कुशलता से करने के लिए आपको बोर्ड की स्थिति का कुशलतापूर्वक प्रतिनिधित्व करने में सक्षम होना चाहिए, फिर कुछ डेटा संरचनाएं हैं जो आपको पारदर्शिता तालिका में उस बोर्ड की स्थिति को तुरंत देखने की अनुमति देती हैं। सही प्रतिनिधित्व ढूँढना आप जिस गेम का विश्लेषण कर रहे हैं उस पर भारी निर्भर करेगा।
तो connect6 is this game शायद एक उदाहरण अच्छा होगा:
बोर्ड इस (स्थिति ए) की तरह शुरू होता है कहते हैं:
X 0
0 X
वहाँ चाल है कि आप (स्थिति बी करने के लिए मिल के एक से अधिक सेट है):
X 0 0 0
0 X X X
0 X
वहाँ है, स्थिति बी को स्थिति एक से जा रहा है, तो आप इस के बारे में चला गया भोलेपन से आप पदों पर सबसे अच्छा कदम को खोजने के लिए परीक्षण करने के लिए हो सकता है की एन तरीके कहो एन बी तक एन बार (पेड़ अल्फा-बीटा prunes बंद की शाखाओं के आधार पर)। लेकिन वास्तव में यह बहुत अच्छा होगा अगर हमें बी बोर्ड की स्थिति के लिए सटीक उसी गणना को कई बार नहीं करना पड़ेगा, तो उम्मीद है कि एक बार पर्याप्त होगा!
इस विचार का लाभ उठाने के लिए आपको क्या करना है, कनेक्ट 6 बोर्ड की स्थिति का प्रतिनिधित्व करने का एक तरीका ढूंढना है। बोर्ड का प्रतिनिधित्व करने का एक तरीका यह है कि N by N
सरणी है जहां N
बोर्ड आयाम है और प्रत्येक सेल के लिए एक एनम मान स्टोर करें जो कि यह खाली है, उसके पास X
है या इसमें 0
है। हालांकि इस बेवकूफ दृष्टिकोण में पदों की तलाश करने के लिए बहुत अच्छी संपत्ति नहीं है क्योंकि हम हमेशा इन बुरा N by N
सरणी के आसपास गुजर रहे होंगे। उल्लेख नहीं है कि इन N by N
सरणी में से बहुत से स्टोर करना हमेशा बहुत मेमोरी लेगा।
तो यदि हम एक हैश फ़ंक्शन को परिभाषित कर सकते हैं जो N by N
बोर्ड लेता है और इसे प्रोसेसिंग ओवरहेड के टन के बिना लगभग अनूठा पूर्णांक में मैप करता है तो हम इस प्रक्रिया को व्यवस्थित कर सकते हैं। बोर्ड को हश करना और यह देखना कि टेबल में है, तो उम्मीद है कि इस तरह से तेज हो।
इसलिए यही कारण है कि लोग उस विशिष्ट गेम के लिए हैशिंग फ़ंक्शन बनाने का प्रयास करते हैं जिसका वे विश्लेषण कर रहे हैं। कनेक्ट 6 के लिए मुझे नहीं पता कि सबसे अच्छा हैशिंग फ़ंक्शन क्या है, यह कुछ ऐसा है जो आपको काम करना होगा।
इस तरह से कुछ का सबसे अच्छा प्रदर्शन प्राप्त करने से टिंकरिंग का पूरा समूह लगता है लेकिन उम्मीद है कि इस पोस्ट ने आपको कुछ विचार दिए हैं। अगर आप मुझे कुछ भी विस्तार करना चाहते हैं तो कृपया टिप्पणी करें।
बहुत बढ़िया, बहुत बहुत धन्यवाद! :) – dfg