अल्फा–बीटा प्रूनिंग

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

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

इतिहास

जॉन मैकार्थी ने 1956 में डार्टमाउथ कार्यशाला के दौरान आईबीएम के एलेक्स बर्नस्टीन से मुलाकात की, जो एक शतरंज प्रोग्राम लिख रहे थे। मैकार्थी ने अल्फा–बीटा सर्च का आविष्कार किया और इसे बर्नस्टीन को सुझाया, लेकिन बर्नस्टीन "आश्वस्त नहीं" थे। एलन न्यूएल और हर्बर्ट ए. साइमन, जिन्होंने 1958 में मैकार्थी द्वारा "अनुमान" कहे जाने वाले तरीके का उपयोग किया, ने लिखा कि अल्फा–बीटा "कई बार पुनः आविष्कार किया गया प्रतीत होता है।" आर्थर सैमुएल के पास चेकर्स सिमुलेशन के लिए एक प्रारंभिक संस्करण था। रिचर्ड्स, टिमोथी हार्ट, माइकल लेविन और/या डैनियल एडवर्ड्स ने भी संयुक्त राज्य अमेरिका में स्वतंत्र रूप से अल्फा–बीटा का आविष्कार किया। मैकार्थी ने डार्टमाउथ कार्यशाला के दौरान समान विचार प्रस्तावित किए और उन्हें अपने छात्रों के एक समूह को सुझाया, जिसमें 1961 में एमआईटी में एलन कोटोक शामिल थे। अलेक्जेंडर ब्रुडनो ने स्वतंत्र रूप से अल्फा–बीटा एल्गोरिदम की कल्पना की, अपने परिणाम 1963 में प्रकाशित किए। डोनाल्ड क्नुथ और रोनाल्ड डब्ल्यू. मूर ने 1975 में एल्गोरिदम को परिष्कृत किया। जूडिया पर्ल ने दो पेपरों में यादृच्छिक रूप से असाइन किए गए लीफ मानों वाले पेड़ों के लिए अपेक्षित चलने के समय के संदर्भ में इसकी इष्टतमता साबित की। अल्फा–बीटा के यादृच्छिक संस्करण की इष्टतमता 1986 में माइकल सैक्स और अवी विगडरसन द्वारा दिखाई गई।

मुख्य विचार

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

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

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

नाइव मिनिमैक्स पर सुधार

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

शाखा कारक b के (औसत या स्थिर) और सर्च गहराई d प्लाई के साथ, मूल्यांकित लीफ नोड स्थितियों की अधिकतम संख्या (जब चाल ऑर्डरिंग पेसिमल है) O(b^d) है - सरल मिनिमैक्स सर्च के समान। यदि सर्च के लिए चाल ऑर्डरिंग इष्टतम है (जिसका अर्थ है कि सबसे अच्छी चालें हमेशा पहले खोजी जाती हैं), तो मूल्यांकित लीफ नोड स्थितियों की संख्या विषम गहराई के लिए लगभग O(b 1 b 1 ... b) और सम गहराई के लिए O(b 1 b 1 ... 1), या O(b^(d/2)) = O(sqrt(b^d)) है। बाद के मामले में, जहां सर्च की प्लाई सम है, प्रभावी शाखा कारक इसके वर्गमूल तक कम हो जाता है, या समकक्ष रूप से, सर्च समान मात्रा में गणना के साथ दोगुनी गहराई तक जा सकती है। b1b1... का स्पष्टीकरण यह है कि सबसे अच्छी चाल खोजने के लिए पहले खिलाड़ी की सभी चालों का अध्ययन किया जाना चाहिए, लेकिन प्रत्येक के लिए, केवल दूसरे खिलाड़ी की सबसे अच्छी चाल की आवश्यकता होती है ताकि पहली (और सबसे अच्छी) पहले खिलाड़ी की चाल को छोड़कर सभी को खारिज किया जा सके - अल्फा–बीटा सुनिश्चित करता है कि किसी अन्य दूसरे खिलाड़ी की चाल पर विचार करने की आवश्यकता नहीं है।

जब नोड्स को यादृच्छिक क्रम में माना जाता है (यानी, एल्गोरिदम यादृच्छिक करता है), स्पर्शोन्मुख रूप से, बाइनरी लीफ-मानों वाले समान पेड़ों में मूल्यांकित नोड्स की अपेक्षित संख्या Theta(((b-1+sqrt(b^2+14b+1))/4)^d) है। समान पेड़ों के लिए, जब मान लीफ मानों को एक दूसरे से स्वतंत्र रूप से असाइन किए जाते हैं और कहते हैं कि शून्य और एक दोनों समान रूप से संभावित हैं, तो मूल्यांकित नोड्स की अपेक्षित संख्या Theta((b/2)^d) है।

कार्यान्वयन विचार

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

विरासत और प्रभाव

अल्फा–बीटा प्रूनिंग का Artificial intelligence और गेम थ्योरी पर स्थायी प्रभाव पड़ा है। यह प्रारंभिक शतरंज प्रोग्रामों में एक प्रमुख घटक था और आधुनिक गेम इंजनों में प्रासंगिक बना हुआ है, विशेष रूप से बड़े शाखा कारकों वाले खेलों के लिए। एल्गोरिदम की दक्षता सुधारों का व्यापक अध्ययन किया गया है, और इसके सिद्धांतों ने सर्च और अनुकूलन के अन्य क्षेत्रों को प्रभावित किया है। हालांकि Machine learning और Deep learning जैसी नई तकनीकों ने गेम एआई को बदल दिया है, अल्फा–बीटा प्रूनिंग अभी भी प्रतिकूल सर्च में एक मौलिक उपकरण के रूप में कार्य करती है, और इसका ऐतिहासिक विकास एआई अनुसंधान की सहयोगात्मक और पुनरावृत्त प्रकृति को उजागर करता है।