मोंटे कार्लो ट्री सर्च: जटिल मल्टीप्लेयर गेम्स में कमियों, लाभों और सीमाओं की समीक्षा
João Luis Almeida Santos, Andrei Camilotto, Djonatan Bonelli, Eduardo Fiorentin, Felipe Grando
सार
MCTS को गो, शतरंज और शोगी में सफलताओं के बाद प्रमुखता मिली, लेकिन अधिकांश अध्ययन पूर्ण सूचना वाले दो-खिलाड़ी खेलों पर केंद्रित हैं। यह पेपर मल्टीप्लेयर डिजिटल और बोर्ड गेम्स में MCTS का विश्लेषण करता है, जो अक्सर अपूर्ण सूचना द्वारा विशेषता होते हैं। IEEE Xplore, HAL Science Ouverte और Google Scholar (2013–2025) से प्राप्त 22 में से चुने गए 18 पेपरों के आधार पर, यह अध्ययन तीन आवर्ती संरचनात्मक सीमाओं की पहचान करता है: कम्प्यूटेशनल पठार, सामरिक तर्क में अंधे धब्बे और प्रतिद्वंद्वी मॉडलिंग में समझौते।
1. परिचय
मोंटे कार्लो ट्री सर्च (MCTS) सर्च एल्गोरिदम का एक परिवार है जो चार चरणों में एक निर्णय वृक्ष का निर्माण करता है: चयन, विस्तार, सिमुलेशन और बैकप्रोपेगेशन। प्रत्येक अवस्था के लिए एक पूर्ण मूल्यांकन फलन की आवश्यकता के बजाय, यह विधि अनेक सिमुलेशनों से क्रियाओं की गुणवत्ता का अनुमान लगाती है, तथा कम बार देखे गए विकल्पों की खोज और ज्ञात क्रियाओं के उपयोग के बीच संतुलन बनाती है। इस विशेषता ने गो, शतरंज और शोगी जैसे खेलों में, विशेष रूप से पूर्ण सूचना वाले दो-खिलाड़ी वातावरणों में, उल्लेखनीय परिणाम देने में योगदान दिया (BROWNE et al., 2012)।
हालाँकि, समकालीन डिजिटल और टेबलटॉप गेम्स अधिक जटिल परिस्थितियाँ प्रस्तुत करते हैं: कई प्रतिद्वंद्वी, छिपी हुई जानकारी, यादृच्छिकता, बड़े एक्शन स्पेस और रीयल-टाइम निर्णय। इन स्थितियों में, एक अतिरिक्त सिमुलेशन हमेशा बेहतर निर्णय उत्पन्न नहीं करता। खिलाड़ियों की अधिक संख्या सर्च ट्री को बड़ा कर देती है और प्रतिद्वंद्वियों की प्रतिक्रियाओं को मॉडल करना कठिन बना देती है। अपूर्ण जानकारी तब स्ट्रैटेजी फ्यूज़न का कारण बन सकती है जब छिपी हुई अवस्थाओं को अपर्याप्त रूप से संभाला जाता है, जबकि समय का दबाव उपलब्ध कम्प्यूटेशनल बजट को कम कर देता है। इन परिदृश्यों में MCTS के बढ़ते अनुप्रयोग के बावजूद, साहित्य खंडित बना हुआ है और क्लासिक गेम्स पर केंद्रित है।
2. उद्देश्य
इस कार्य का सामान्य उद्देश्य मल्टीप्लेयर डिजिटल और टेबलटॉप गेम्स में MCTS की आवर्ती सीमाओं की पहचान करना और उन्हें व्यवस्थित करना था, विशेष रूप से अपूर्ण सूचना, स्टोकेस्टिसिटी और समय की कमी वाले वातावरणों में।
विशिष्ट उद्देश्यों के रूप में, इस कार्य ने उन रणनीतियों को एकत्र करने का प्रयास किया जो इन सीमाओं को कम करती हैं और उन शोध अंतरालों की पहचान करती हैं जो भविष्य के अध्ययनों का मार्गदर्शन कर सकती हैं और अधिक तुलनीय और पुनरुत्पादनीय मूल्यांकनों का समर्थन कर सकती हैं।
3. कार्यप्रणाली
2013 से 2025 के बीच प्रकाशित अध्ययनों पर एक साहित्य समीक्षा की गई, जिसमें IEEE Xplore, HAL Science Ouverte और Google Scholar डेटाबेस में खोज की गई। खोज रणनीतियों में "Monte Carlo Tree Search" और "MCTS" शब्दों को डिजिटल गेम्स, बोर्ड गेम्स और मल्टीप्लेयर गेम्स से संबंधित अभिव्यक्तियों के साथ जोड़ा गया। स्क्रीनिंग में उन कार्यों पर विचार किया गया जिनके शीर्षक या सार में MCTS, इसके किसी प्रत्यक्ष प्रकार या प्रतिस्पर्धी या सहकारी गेम्स पर लागू किसी हाइब्रिड विधि पर चर्चा की गई थी। दायरे से बाहर के अध्ययनों, पूर्ण पाठ तक पहुँच के बिना दस्तावेज़ों और उन कार्यों को बाहर रखा गया जिनका दायरा समीक्षा के उद्देश्यों के अनुरूप नहीं था।
खोजों से 24 रिकॉर्ड प्राप्त हुए, जिनमें से दो क्वेरीज़ के बीच दोहराए गए थे, जिसके परिणामस्वरूप 22 अद्वितीय संभावित रूप से प्रासंगिक कार्य प्राप्त हुए (17 अंग्रेज़ी में और पाँच फ़्रेंच में)। स्क्रीनिंग के बाद, 18 अध्ययनों को पूर्ण विश्लेषण के लिए चुना गया और चार को बाहर रखा गया। अंतिम संग्रह में IEEE Xplore से 13 अध्ययन, HAL से तीन और Google Scholar के माध्यम से पाए गए दो अध्ययन शामिल थे, और चयनित अध्ययनों में से 15 पाठ अंग्रेज़ी में और तीन फ़्रेंच में थे। कार्यों को खेल के प्रकार, उपयोग किए गए एल्गोरिदम, पर्यावरण बाधाओं, रिपोर्ट किए गए परिणामों और शमन रणनीतियों के आधार पर वर्गीकृत किया गया था। विषयगत विश्लेषण को सीमा की तीन संरचनात्मक श्रेणियों, प्रदर्शन सीमाएँ, सामरिक अंधे धब्बे और प्रतिद्वंद्वी मॉडलिंग में समझौते, और दो डोमेन-निर्भर प्रवर्धक, अपूर्ण जानकारी और वास्तविक समय के निर्णयों में व्यवस्थित किया गया था।
4. परिणाम और चर्चा
विश्लेषित अध्ययनों से संकेत मिलता है कि MCTS उन खेलों में सबसे अधिक सुसंगत प्रदर्शन करता है जिनमें सुस्पष्ट अवस्थाएँ, मध्यम शाखा-कारक और उच्च संख्या में सिमुलेशन के लिए पर्याप्त कम्प्यूटेशनल बजट होता है। चयनित 18 कार्यों में से आठ ने डिजिटल खेलों को संबोधित किया, छह ने बोर्ड या टेबलटॉप खेलों की जाँच की और शेष ने कार्ड खेलों, सामान्य खेल खेलने के वातावरण या संबंधित अनुप्रयोगों का विश्लेषण किया। MCTS-आधारित एल्गोरिद्म 14 अध्ययनों में उपयोग किए गए, जिन्हें अक्सर न्यूरल नेटवर्क, एक्शन स्पेस एब्स्ट्रैक्शन, सिमुलेशन नीतियों और पैरामीटर ट्यूनिंग तकनीकों के साथ संयोजित किया गया।
पहली सीमा जो पहचानी गई है, वह खोज प्रदर्शन से संबंधित है। यद्यपि सिमुलेशन की संख्या बढ़ाने से आमतौर पर निर्णय की गुणवत्ता में सुधार होता है, सीमांत लाभ कम होने लगते हैं क्योंकि नए सिमुलेशन उन प्रक्षेपपथों को फिर से देखने लगते हैं जिनकी पर्याप्त रूप से खोज हो चुकी है। गो, रीयल-टाइम रणनीति खेलों और टेबलटॉप खेलों में प्राप्त परिणाम दिखाते हैं कि कंप्यूटेशनल बजट को दोगुना करने से एक निश्चित बिंदु के बाद कम या कोई लाभ नहीं मिल सकता है। इसके अतिरिक्त, कौशल गहराई पर अध्ययन दिखाते हैं कि यह सीमा खेल की जटिलता और एजेंट के विन्यास दोनों पर निर्भर करती है। शमन रणनीतियों में क्रिया स्थान का अमूर्तन, सिमुलेशन का सरलीकरण और N-Tuple Bandit Evolutionary Algorithm (NTBEA) (GOODMAN; PEREZ-LIEBANA; LUCAS, 2024) के माध्यम से नीतियों, अन्वेषण स्थिरांकों और रोलआउट रणनीतियों का स्वचालित ट्यूनिंग शामिल है।
दूसरी सीमा सामरिक तर्क के अंध-बिंदुओं से मेल खाती है। चूँकि MCTS नमूनाकृत निरंतरताओं के औसत मान का अनुमान लगाता है, एल्गोरिद्म उन स्थितियों में विफल हो सकता है जिनमें विशिष्ट सामरिक अनुक्रमों, दीर्घकालिक खतरों या दुर्लभ विन्यासों को पहचानने की आवश्यकता होती है। गो में, सीढ़ियों और सेमेई जैसी स्थितियाँ ऐसे परिदृश्यों को दर्शाती हैं जिनमें अनुभवी खिलाड़ियों के लिए स्पष्ट सामरिक संरचना को खोज द्वारा पहचाना नहीं जा सकता।
तीसरी सीमा प्रतिद्वंद्वी मॉडलिंग से संबंधित है। तीन या अधिक प्रतिभागियों वाले खेलों में, खोज प्रक्रिया को न केवल वृक्ष की जड़ पर स्थित खिलाड़ी के निर्णयों का प्रतिनिधित्व करना होता है, बल्कि प्रत्येक प्रतिद्वंद्वी की संभावित प्रतिक्रियाओं का भी प्रतिनिधित्व करना होता है। जो मॉडल प्रत्येक प्रतिद्वंद्वी के लिए स्वतंत्र संरचनाएँ बनाए रखते हैं, वे रणनीतिक व्यवहार का बेहतर प्रतिनिधित्व करते हैं, हालाँकि वे गणनात्मक लागत को काफी बढ़ा देते हैं। इसके विपरीत, सरलीकृत दृष्टिकोण, जैसे पैरानॉयड सर्च और सामान्यीकृत नीतियाँ, इस लागत को कम करते हैं लेकिन प्रासंगिक व्यवहारों का प्रतिनिधित्व करने में विफल हो सकते हैं। साहित्य से पता चलता है कि चयनात्मक फोकस, प्रतिद्वंद्वियों की प्रतिक्रियाओं के सामान्यीकरण और वृक्ष विघटन पर आधारित दृष्टिकोण आशाजनक विकल्प हैं, हालाँकि बड़ी संख्या में प्रतिभागियों वाले खेलों में इनका अभी भी बहुत कम मूल्यांकन किया गया है (BAIER; KAISERS, 2020)।
अपूर्ण सूचना इन सीमाओं को और तीव्र कर देती है। ताश के खेलों, पोकीमोन और छिपी अवस्थाओं वाले अन्य वातावरणों में, निर्धारणीकरण, जिसमें अज्ञात सूचना के एक संभावित विन्यास को मान लिया जाता है और खोज ऐसे की जाती है मानो वह सत्य हो, असंगत रणनीतियों के विलय का कारण बन सकता है। सूचना समुच्चय MCTS, मोंटे कार्लो वृक्ष खोज का एक रूपांतर जिसे अनिश्चितता से निपटने के लिए डिज़ाइन किया गया है, उन अवस्थाओं को समूहित करके इस समस्या को कम करता है जिन्हें खिलाड़ी अलग नहीं कर सकता, और निर्णय के क्षण में वास्तव में उपलब्ध सूचना को ही संरक्षित रखता है (COWLING; POWLEY; WHITEHOUSE, 2012)। फिर भी, वातावरण में अंतर्निहित यादृच्छिकता और प्रतिद्वंद्वियों के व्यवहार का अनुमान लगाने की आवश्यकता उत्पन्न अनुमानों की विश्वसनीयता को सीमित करती रहती है।
रणनीतिक खेलों, MOBA और फर्स्ट-पर्सन शूटर जैसे रीयल-टाइम वातावरणों में, समय की बाधाएँ एक महत्वपूर्ण कारक बन जाती हैं। MCTS को संयोजनात्मक क्रिया-स्थानों, कई इकाइयों और आंशिक प्रेक्षणों का प्रबंधन करते हुए अत्यंत लघु अंतरालों में क्रियाओं का चयन करना होता है। इस संदर्भ में, पदानुक्रमित अमूर्तन, मैक्रो-क्रियाएँ, क्रिया छँटाई और पर्यवेक्षित अधिगम या सुदृढ़ीकरण अधिगम के माध्यम से प्राप्त नीतियाँ आवर्ती रणनीतियों के रूप में प्रकट होती हैं (ONTAÑÓN, 2013)। कुछ स्थितियों में, वैकल्पिक विधियाँ बेहतर प्रदर्शन कर सकती हैं। उदाहरण के लिए, रोलिंग होराइज़न एवोल्यूशनरी एल्गोरिदम (RHEA) लघु क्रिया-अनुक्रमों का विकास करता है और निरंतर पुनर्नियोजन करता है, जो सहकारी खेलों और अत्यधिक स्टोकेस्टिक वातावरणों के लिए विशेष रूप से उपयुक्त सिद्ध होता है जिनमें खोज वृक्ष शीघ्रता से बदलता है (SFIKAS; LIAPIS, 2022)।
वास्तविक समय के निर्णयों पर कम निर्भर MCTS के अनुप्रयोगों की भी पहचान की गई, जैसे स्वचालित संतुलन, प्लेटेस्टिंग और गेम डिज़ाइन के लिए समर्थन। इन परिदृश्यों में, प्रसंस्करण समय एक महत्वपूर्ण बाधा नहीं रह जाता, जिससे विभिन्न कॉन्फ़िगरेशनों को व्यापक रूप से खोजा जा सकता है, असंतुलनों की पहचान की जा सकती है और डिज़ाइन विकल्पों का मूल्यांकन किया जा सकता है। हालाँकि अधिकांश अध्ययन प्रस्तावित दृष्टिकोणों के पक्ष में परिणाम बताते हैं, कुछ कार्यों में प्रतिस्पर्धी तकनीकों की तुलना में MCTS का कम प्रदर्शन देखा गया, जैसा कि Kingdomino और Pandemic गेमों में।
5. निष्कर्ष
समीक्षा ने भविष्य के शोध के लिए पाँच प्रासंगिक अवसरों की भी पहचान की: (i) अपूर्ण सूचना वाले मल्टीप्लेयर गेम्स के लिए साझा बेंचमार्क का अंगीकरण और मानकीकरण; (ii) अधिक संख्या में प्रतिभागियों वाले गेम्स में प्रतिद्वंद्वी मॉडलिंग तकनीकों का व्यवस्थित मूल्यांकन; (iii) मानव खिलाड़ियों द्वारा अनुभव की गई जटिलता और खोज की प्रभावी गहराई के बीच संबंध की जाँच; (iv) पिक्स और बैन्स के इतिहास को ध्यान में रखते हुए बेस्ट-ऑफ-थ्री और बेस्ट-ऑफ-फाइव प्रतिस्पर्धी श्रृंखलाओं का अध्ययन; और (v) स्वचालित संतुलन, प्लेटेस्टिंग और प्रक्रियात्मक सामग्री निर्माण में MCTS अनुप्रयोगों का विस्तार।
संदर्भ
- [1]Baier, H.; Kaisers, M. (2020). Guiding multiplayer MCTS by focusing on yourself. In: IEEE Conference on Games (CoG), 550–557.
- [2]Browne, C. B. et al. (2012). A survey of Monte Carlo Tree Search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1–43.
- [3]Cowling, P. I.; Powley, E. J.; Whitehouse, D. (2012). Information set Monte Carlo tree search. IEEE Transactions on Computational Intelligence and AI in Games, 4(2), 120–143.
- [4]Goodman, J.; Perez-Liebana, D.; Lucas, S. (2024). Skill depth in tabletop board games. In: 2024 IEEE Conference on Games (CoG), 1–8.
- [5]Ontañón, S. (2013). The combinatorial multi-armed bandit problem and its application to real-time strategy games. In: Proceedings of the Ninth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 58–64.
- [6]Sfikas, K.; Liapis, A. (2022). Playing against the board: Rolling horizon evolutionary algorithms against Pandemic. IEEE Transactions on Games, 14(3), 339–349.