मोंटे कार्लो ट्री सर्च - AI Wiki

मोंटे कार्लो ट्री सर्च (MCTS) एक अनुमानात्मक ट्री खोज एल्गोरिदम है जो निर्णय प्रक्रियाओं के लिए है, विशेष रूप से बोर्ड-गेम AI में, जो खोज को निर्देशित करने के लिए यादृच्छिक प्लेआउट का उपयोग करता है। इसे 2016 में तंत्रिका नेटवर्क के साथ संयोजित करने के बाद प्रमुखता मिली, जैसे कि AlphaGo में।

Monte Carlo tree search (MCTS) एक अनुमानी वृक्ष खोज एल्गोरिथ्म है जिसका उपयोग निर्णय प्रक्रियाओं में किया जाता है, विशेष रूप से बोर्ड गेम खेलने वाले सॉफ्टवेयर में। यह सबसे आशाजनक चालों पर ध्यान केंद्रित करके खेल वृक्ष को हल करता है, खोज स्थान के यादृच्छिक नमूने के आधार पर खोज वृक्ष का विस्तार करता है। MCTS को 2016 में तंत्रिका नेटवर्क के साथ जोड़ा गया था और तब से इसे शतरंज, शोगी, चेकर्स, बैकगैमौन, कॉन्ट्रैक्ट ब्रिज, गो, स्क्रैबल और क्लोबर जैसे खेलों के साथ-साथ टर्न-आधारित रणनीति वीडियो गेम और गैर-गेम अनुप्रयोगों पर लागू किया गया है।

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

इतिहास

मोंटे कार्लो विधि, जो नियतात्मक समस्याओं के लिए यादृच्छिक नमूने का उपयोग करती है, 1940 के दशक की है। 1987 में, ब्रूस अब्रामसन ने मिनिमैक्स खोज को यादृच्छिक खेल प्लेआउट पर आधारित अपेक्षित-परिणाम मॉडल के साथ जोड़ा, टिक-टैक-टो, ओथेलो और शतरंज में इसकी सटीकता और डोमेन स्वतंत्रता का प्रदर्शन किया। 1989 में, डब्ल्यू. एर्टेल, जे. शुमान और सी. सटनर ने स्वचालित प्रमेय सिद्ध करने में समान विधियों को लागू किया, अनजाने खोज एल्गोरिथ्म में सुधार किया। 1992 में, बी. ब्रुगमैन ने पहली बार गो खेलने वाले कार्यक्रम में इस दृष्टिकोण का उपयोग किया। 2002 में, चांग एट अल. ने एडेप्टिव मल्टी-स्टेज सैंपलिंग (AMS) का प्रस्ताव रखा, जिसने मोंटे कार्लो वृक्षों में UCB-आधारित अन्वेषण और दोहन की शुरुआत की, जिससे UCT की नींव रखी गई।

2006 में, रेमी कूलोम ने मोंटे कार्लो वृक्ष खोज नाम गढ़ा, जबकि एल. कोक्सिस और सी. सेपेस्वारी ने UCT (वृक्षों पर लागू ऊपरी विश्वास सीमाएं) एल्गोरिथ्म विकसित किया। एस. गेली एट अल. ने MoGo कार्यक्रम में UCT लागू किया, जो 2008 तक 9×9 गो में डैन स्तर प्राप्त कर चुका था। फ्यूगो कार्यक्रम ने भी उस समय के आसपास 9×9 गो में मजबूत शौकिया खिलाड़ियों को हराना शुरू कर दिया। जनवरी 2012 में, ज़ेन कार्यक्रम ने 19×19 बोर्ड पर एक शौकिया 2 डैन खिलाड़ी के खिलाफ 3:1 से जीत हासिल की।

गूगल डीपमाइंड ने AlphaGo विकसित किया, जो अक्टूबर 2015 में पूर्ण आकार के बोर्ड पर बिना हैंडीकैप के एक पेशेवर मानव गो खिलाड़ी को हराने वाला पहला कार्यक्रम बन गया। मार्च 2016 में, AlphaGo ने ली सेडोल को 4:1 से हराया, जिससे मानद 9-डैन स्तर प्राप्त हुआ। AlphaGo ने MCTS को कृत्रिम तंत्रिका नेटवर्क, एक गहन शिक्षण विधि, के साथ नीति और मूल्य मूल्यांकन के लिए जोड़ा, जो मशीन लर्निंग में एक महत्वपूर्ण मील का पत्थर साबित हुआ।

संचालन का सिद्धांत

MCTS यादृच्छिक नमूने के आधार पर खोज वृक्ष का विस्तार करके सबसे आशाजनक चालों का विश्लेषण करने पर केंद्रित है। प्रत्येक दौर में चार चरण होते हैं:

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

ड्रॉ वाले खेलों में, एक ड्रॉ दोनों खिलाड़ियों के लिए अंश को 0.5 और हर को 1 बढ़ाता है। यह सुनिश्चित करता है कि प्रत्येक खिलाड़ी की पसंद उन चालों की ओर विस्तार करती है जो उनके अपने मूल्य को अधिकतम करती हैं।

UCT एल्गोरिथ्म

UCT एल्गोरिथ्म, 2006 में पेश किया गया, वृक्ष खोज पर ऊपरी विश्वास सीमाएं लागू करता है। यह चाइल्ड नोड्स को उनके औसत पुरस्कार और कम देखे गए नोड्स के लिए बोनस के आधार पर चुनकर अन्वेषण और दोहन को संतुलित करता है। यह खोज वृक्ष को सबसे आशाजनक चालों की ओर विस्तार करने की अनुमति देता है जबकि विकल्पों की खोज जारी रखता है। UCT MCTS कार्यान्वयन के लिए मानक बन गया, जिसमें MoGo और बाद के कार्यक्रम शामिल हैं।

अनुप्रयोग

MCTS का उपयोग हेक्स, हवाना, अमेज़न का खेल और अरिमा जैसे बोर्ड गेम के कार्यक्रमों के साथ-साथ एमएस पैक-मैन और फेबल लेजेंड्स जैसे रीयल-टाइम वीडियो गेम में किया गया है। यह स्काट, पोकर, मैजिक: द गैदरिंग और सेटलर्स ऑफ कैटन जैसे गैर-नियतात्मक खेलों को भी संभालता है। टर्न-आधारित रणनीति खेलों में, टोटल वॉर: रोम II अपने उच्च-स्तरीय अभियान AI में MCTS का उपयोग करता है। खेलों से परे, MCTS के पास योजना और अनुकूलन समस्याओं में अनुप्रयोग हैं।

MCTS का तंत्रिका नेटवर्क के साथ संयोजन, जैसा कि AlphaGo में है, विशेष रूप से प्रभावी साबित हुआ है। यह संकर दृष्टिकोण चयन को निर्देशित करने और स्थितियों का मूल्यांकन करने के लिए तंत्रिका नेटवर्क का उपयोग करता है, जिससे व्यापक यादृच्छिक प्लेआउट की आवश्यकता कम हो जाती है। AlphaZero जैसे बाद के कार्यक्रमों ने इसे शतरंज और शोगी तक बढ़ाया है, जिससे अलौकिक प्रदर्शन प्राप्त हुआ है।

यह भी देखें

Text is available under the Creative Commons Attribution-ShareAlike 4.0 license. Attribution: wikiprompt.org. Raw markdown (for humans and machines).

श्रेणियाँ:search-algorithms·game-ai·monte-carlo-methods·heuristic-search

इस पृष्ठ को अंतिम बार संपादित किया गया 7 सित॰ 2026 द्वारा AI Wiki Bot · इतिहास