Game tree
संयोजन खेल सिद्धांत के संदर्भ में, जो आम तौर पर सटीक जानकारी के साथ अनुक्रमिक खेलों का अध्ययन करता है, एक गेम ट्री एक ग्राफ है जो इस तरह के खेल के भीतर सभी संभावित खेल स्थितियों का प्रतिनिधित्व करता है। इस तरह के खेलों में शतरंज, चेकर्स, गो और टिक-टैक-टो जैसे प्रसिद्ध खेल शामिल हैं। इसका उपयोग खेल की जटिलता को मापने के लिए किया जा सकता है, क्योंकि यह उन सभी संभावित तरीकों का प्रतिनिधित्व करता है जिनसे खेल पूरा हो सकता है। शतरंज जैसे जटिल खेलों के बड़े खेल वृक्षों के कारण, इस वर्ग के खेलों को खेलने के लिए डिज़ाइन किए गए एल्गोरिदम आंशिक खेल वृक्षों का उपयोग करेंगे, जो आधुनिक कंप्यूटरों पर गणना को संभव बनाता है। खेल वृक्षों को हल करने के लिए विभिन्न तरीके मौजूद हैं। यदि एक पूर्ण गेम ट्री उत्पन्न किया जा सकता है, तो एक नियतात्मक एल्गोरिथ्म, जैसे कि बैकवर्ड इंडक्शन या रेट्रोग्रेड एनालिसिस का उपयोग किया जा सकता है। यादृच्छिक एल्गोरिदम और एम. सी. टी. एस. जैसे मिनमैक्स एल्गोरिदम का उपयोग उन मामलों में किया जा सकता है जहां एक पूर्ण गेम ट्री संभव नहीं है। गेम ट्री को बेहतर ढंग से समझने के लिए, इसे प्रतिकूल खेलों के विश्लेषण के लिए एक तकनीक के रूप में सोचा जा सकता है, जो खेल जीतने के लिए खिलाड़ी द्वारा किए जाने वाले कार्यों को निर्धारित करता है। खेल सिद्धांत में, एक गेम ट्री एक निर्देशित ग्राफ है जिसके नोड्स एक खेल में स्थिति हैं (उदाहरण के लिए, एक बोर्ड गेम में टुकड़ों की व्यवस्था) और जिनके किनारे चाल हैं (उदाहरण के लिए, एक बोर्ड पर एक स्थिति से दूसरी स्थिति में टुकड़ों को स्थानांतरित करने के लिए)। एक खेल के लिए पूरा खेल वृक्ष खेल वृक्ष है जो प्रारंभिक स्थिति से शुरू होता है और जिसमें प्रत्येक स्थिति से सभी संभावित चालें होती हैं; पूरा वृक्ष वही वृक्ष है जो व्यापक रूप से खेल प्रतिनिधित्व से प्राप्त होता है। अधिक विशिष्ट होने के लिए, पूरा खेल खेल सिद्धांत में खेल के लिए एक मानक है। जो कई महत्वपूर्ण पहलुओं को स्पष्ट रूप से व्यक्त कर सकता है। उदाहरण के लिए, हितधारकों द्वारा की जाने वाली कार्रवाइयों का क्रम, प्रत्येक निर्णय बिंदु पर उनकी पसंद, प्रत्येक हितधारक द्वारा निर्णय लेने पर अन्य हितधारकों द्वारा की गई कार्रवाइयों के बारे में जानकारी और सभी संभावित खेल परिणामों के लाभ। आरेख टिक-टेक-पैर के लिए गेम ट्री में पहले दो स्तरों को दिखाता है। स्थिति के घूर्णन और प्रतिबिंब बराबर होते हैं, इसलिए पहले खिलाड़ी के पास चाल के तीन विकल्प होते हैंः केंद्र में, किनारे पर या कोने में। यदि पहला खिलाड़ी केंद्र में खेलता है तो दूसरे खिलाड़ी के पास जवाब के लिए दो विकल्प होते हैं, अन्यथा पाँच विकल्प होते हैं। और इसी तरह। पूर्ण गेम ट्री में लीफ नोड्स की संख्या खेल को खेले जाने वाले संभावित विभिन्न तरीकों की संख्या है। उदाहरण के लिए, टिक-टैक-पैर के लिए गेम ट्री में 255,168 लीफ नोड्स हैं। कृत्रिम बुद्धिमत्ता में खेल के पेड़ महत्वपूर्ण हैं क्योंकि एक खेल में सबसे अच्छी चाल चुनने का एक तरीका है कि पेड़ की कटाई के लिए मिनीमैक्स जैसे नियमों के साथ कई पेड़ खोज एल्गोरिदम में से किसी का उपयोग करके खेल के पेड़ की खोज की जाए। टिक-टैक-पैर के लिए गेम ट्री आसानी से खोजा जा सकता है, लेकिन शतरंज जैसे बड़े खेलों के लिए पूरा गेम ट्री खोजने के लिए बहुत बड़ा है। इसके बजाय, एक शतरंज खेलने वाला कार्यक्रम एक आंशिक गेम ट्री की खोज करता हैः आम तौर पर वर्तमान स्थिति से उतने ही लोग जिन्हें यह उपलब्ध समय में खोज सकता है। "पैथोलॉजिकल" गेम ट्री के मामले को छोड़कर (जो व्यवहार में काफी दुर्लभ प्रतीत होते हैं), खोज की गहराई को बढ़ाना (यानी, खोजे गए प्लियों की संख्या) आम तौर पर सबसे अच्छी चाल चुनने की संभावना में सुधार करता है। दो-व्यक्ति खेलों को और-या-पेड़ के रूप में भी दर्शाया जा सकता है। खेल जीतने वाले पहले खिलाड़ी के लिए, दूसरे खिलाड़ी की सभी चालों के लिए एक विजयी चाल होनी चाहिए। इसे पहले खिलाड़ी की वैकल्पिक चालों का प्रतिनिधित्व करने के लिए विच्छेदन का उपयोग करके और दूसरे खिलाड़ी की सभी चालों का प्रतिनिधित्व करने के लिए संयोजन का उपयोग करके और-या वृक्ष में दर्शाया जाता है। गेम ट्री को हल करना एक पूर्ण गेम ट्री के साथ, गेम को "हल" करना संभव है-अर्थात, उन चालों का एक क्रम खोजें जिनका पहला या दूसरा खिलाड़ी पालन कर सकता है जो उस खिलाड़ी के लिए सर्वोत्तम संभव परिणाम (आमतौर पर एक जीत या एक टाई) की गारंटी देगा। नियतात्मक एल्गोरिदम (जिसे आम तौर पर बैकवर्ड इंडक्शन या रेट्रोग्रेड एनालिसिस कहा जाता है) को पुनरावर्ती रूप से निम्नानुसार वर्णित किया जा सकता है। गेम ट्री के अंतिम प्लाई को रंग दें ताकि खिलाड़ी 1 के लिए सभी जीत एक तरह से रंगीन हों (आरेख में नीला), खिलाड़ी 2 के लिए सभी जीत दूसरे तरीके से रंगीन हों (आरेख में लाल), और सभी संबंध तीसरे तरीके से रंगीन हों (आरेख में ग्रे)। अगले प्लाई अप को देखें। यदि वर्तमान खिलाड़ी के विपरीत रंग का कोई नोड मौजूद है, तो उस खिलाड़ी के लिए भी इस नोड को रंग दें। यदि सभी तुरंत निचले नोड्स एक ही खिलाड़ी के लिए रंगीन हैं, तो उसी खिलाड़ी के लिए भी इस नोड को रंग दें। अन्यथा, इस नोड को एक टाई में रंग दें। प्रत्येक प्लाई के लिए दोहराएं, ऊपर की ओर बढ़ते हुए, जब तक कि सभी नोड्स रंगीन न हो जाएं। रूट नोड का रंग खेल की प्रकृति को निर्धारित करेगा। आरेख एक मनमाने खेल के लिए एक गेम ट्री दिखाता है, जो उपरोक्त एल्गोरिथ्म का उपयोग करके रंगीन है। आमतौर पर गेम ट्री के केवल एक उपसमुच्चय का उपयोग करके एक खेल ("हल" के इस तकनीकी अर्थ में) को हल करना संभव है, क्योंकि कई खेलों में एक चाल का विश्लेषण करने की आवश्यकता नहीं होती है यदि एक ही खिलाड़ी के लिए एक और चाल बेहतर है (उदाहरण के लिए अल्फा-बीटा छंटाई का उपयोग कई निर्धारक खेलों में किया जा सकता है)। खेल को हल करने के लिए उपयोग किए जाने वाले किसी भी उप-वृक्ष को निर्णय वृक्ष के रूप में जाना जाता है, और विभिन्न आकारों के निर्णय वृक्षों के आकार का उपयोग खेल जटिलता के माप के रूप में किया जाता है। यादृच्छिक एल्गोरिदम संस्करण यादृच्छिक एल्गोरिदम का उपयोग गेम ट्री को हल करने में किया जा सकता है। इस प्रकार के कार्यान्वयन में दो मुख्य लाभ हैंः गति और व्यावहारिकता। जबकि गेम ट्री को हल करने का एक नियतात्मक संस्करण किया जा सकता है, निम्नलिखित यादृच्छिक एल्गोरिथ्म में एक अपेक्षित रन टाइम होता है यदि गेम ट्री में प्रत्येक नोड में डिग्री 2 होती है। इसके अलावा, यह व्यावहारिक है क्योंकि यादृच्छिक एल्गोरिदम "एक दुश्मन को विफल करने" में सक्षम हैं, जिसका अर्थ है कि एक प्रतिद्वंद्वी गेम ट्री को हल करने के लिए उपयोग किए जाने वाले एल्गोरिदम को जानकर गेम ट्री की प्रणाली को हरा नहीं सकता है क्योंकि हल करने का क्रम यादृच्छिक है। निम्नलिखित यादृच्छिक गेम ट्री समाधान एल्गोरिदम का एक कार्यान्वयन हैः डेफ जीटी _ इवेल _ रैंड (यू)-> बूलः "यदि यह नोड एक जीत का मूल्यांकन करता है तो सही लौटता है, अन्यथा गलत" "यदि u.leaf: रिटर्न u.win अन्यथाः यादृच्छिक _ बच्चे = (जीटी _ इवेल _ रैंड (चाइल्ड) यादृच्छिक _ क्रम (u.children) में बच्चे के लिए) यदि यू. ओ. पी. = =" ओ. आर ".: किसी भी (यादृच्छिक _ बच्चों) को वापस करें यदि यू. ओ. पी. = =" ए. एन. डी ".: सभी (यादृच्छिक _ बच्चों को वापस करें) एल्गोरिदम" शॉर्ट-सर्किटिंग "के विचार का उपयोग करता हैः यदि रूट नोड को" ऑपरेटर "माना जाता है, तो एक बार अल्फा-बीटा प्रूनिंग एक्सटेंसिव फॉर्म गेम शैनन नंबर गेम कॉम्प्लेक्सिटी भी देखें संदर्भ आगे पढ़ने के लिए जूडिया पर्ल, ह्यूरिस्टिक्स, एडिसन-वेस्ली, 1984 कॉम्बिनेटरियल गेम थ्योरी ट्रीज़ (ग्राफ थ्योरी)