प्रतिकूल खोज और खेल खेलना

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

Definition

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

Scope

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

Core questions

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

Key concepts

• खेल वृक्ष
• मिनिमैक्स मान
• अल्फा-बीटा प्रूनिंग
• मूल्यांकन (अनुमानी) फ़ंक्शन
• गहराई-सीमित खोज और क्षितिज प्रभाव
• शून्य-योग पूर्ण-सूचना खेल
• मोंटे कार्लो ट्री खोज
• चाल क्रम

Key theories

मिनिमैक्स निर्णय नियम

दो-खिलाड़ी शून्य-योग खेल में, प्रत्येक खिलाड़ी वह चाल चुनता है जो उनके अपने न्यूनतम गारंटीकृत परिणाम को अधिकतम करती है; इन अधिकतम/न्यूनतम मानों को खेल वृक्ष में ऊपर की ओर प्रचारित करने से मूल में इष्टतम चाल प्राप्त होती है।

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

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

मोंटे कार्लो ट्री खोज

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

Clinical relevance

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

History

शैनन के 1950 के पेपर ने कंप्यूटर शतरंज को एक मूल्यांकन फ़ंक्शन के साथ मिनिमैक्स खोज के रूप में तैयार किया, और वॉन न्यूमैन के मिनिमैक्स प्रमेय ने खेल-सैद्धांतिक नींव प्रदान की। अल्फा-बीटा प्रूनिंग को 1950-60 के दशक में विकसित किया गया था और नुथ और मूर (1975) द्वारा कठोरता से विश्लेषण किया गया था। 2000 के दशक में औपचारिक रूप से मोंटे कार्लो ट्री खोज ने खेल-खेलने की शक्ति में अगली छलांग लगाई, विशेष रूप से गो में।

Key figures

• Claude E. Shannon
• John von Neumann
• Arthur Samuel
• Donald E. Knuth
• Ronald W. Moore

Seminal works

• shannon1950
• knuth1975
• browne2012

Frequently asked questions

क्या अल्फा-बीटा प्रूनिंग उस चाल को बदलता है जिसे मिनिमैक्स चुनेगा?

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

गो जैसे खेलों में मिनिमैक्स के बजाय मोंटे कार्लो ट्री खोज का उपयोग क्यों करें?

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