मोंटे कार्लो ट्री सर्च (MCTS) एक अनुमानी ट्री सर्च एल्गोरिदम है जिसका उपयोग निर्णय प्रक्रियाओं के लिए किया जाता है, विशेष रूप से बोर्ड गेम खेलने वाले सॉफ्टवेयर में। यह सबसे आशाजनक चालों पर ध्यान केंद्रित करके गेम ट्री को हल करता है, सर्च स्पेस के यादृच्छिक नमूने के आधार पर सर्च ट्री का विस्तार करता है। MCTS को 2016 में न्यूरल नेटवर्क के साथ जोड़ा गया था और तब से इसे शतरंज, शोगी, चेकर्स, बैकगैमौन, कॉन्ट्रैक्ट ब्रिज, गो, स्क्रैबल और क्लोबर जैसे खेलों के साथ-साथ टर्न-आधारित रणनीति वीडियो गेम और अन्य डोमेन पर लागू किया गया है।
एल्गोरिदम बार-बार प्लेआउट या रोल-आउट के माध्यम से संचालित होता है, जहां खेलों को यादृच्छिक चालों के साथ पूर्णता तक सिम्युलेट किया जाता है। इन प्लेआउट के परिणामों का उपयोग गेम ट्री में नोड्स को भार देने के लिए किया जाता है, जो भविष्य के चयन को अधिक आशाजनक चालों की ओर मार्गदर्शन करता है। MCTS के प्रत्येक दौर में चार चरण होते हैं: चयन, विस्तार, सिमुलेशन और बैकप्रोपेगेशन।
इतिहास
मोंटे कार्लो विधि, जो नियतात्मक समस्याओं के लिए यादृच्छिक नमूने का उपयोग करती है, 1940 के दशक से चली आ रही है। 1987 में, ब्रूस अब्रामसन ने मिनिमैक्स सर्च को यादृच्छिक गेम प्लेआउट पर आधारित अपेक्षित-परिणाम मॉडल के साथ जोड़ा, और टिक-टैक-टो और अन्य खेलों पर इसकी प्रभावशीलता का प्रदर्शन किया। 1989 में, डब्ल्यू. एर्टेल, जे. शुमान और सी. सटनर ने स्वचालित प्रमेय सिद्ध करने में समान विधियों को लागू किया, जिससे सर्च समय में सुधार हुआ। 1992 में, बी. ब्रुगमैन ने गो खेलने वाले प्रोग्राम में इस दृष्टिकोण का उपयोग किया। 2002 में, चांग एट अल. ने एडेप्टिव मल्टी-स्टेज सैंपलिंग (AMS) का प्रस्ताव रखा, जिसने मोंटे कार्लो ट्री में UCB-आधारित अन्वेषण और दोहन की शुरुआत की, जिससे UCT की नींव पड़ी।
2006 में, रेमी कूलोम ने मोंटे कार्लो ट्री सर्च शब्द गढ़ा, जबकि एल. कोक्सिस और सी. सेज़ेपेस्वारी ने UCT (ट्री पर लागू ऊपरी विश्वास सीमा) एल्गोरिदम विकसित किया। एस. गेली एट अल. ने MoGo प्रोग्राम में UCT लागू किया, जिसने 2008 तक 9x9 गो में डैन स्तर हासिल किया। 2012 में, ज़ेन प्रोग्राम ने 19x19 बोर्ड पर एक शौकिया 2 डैन खिलाड़ी के खिलाफ मैच जीता। गूगल डीपमाइंड के अल्फागो, जो न्यूरल नेटवर्क के साथ MCTS का उपयोग करता है, 2015 में एक पेशेवर मानव गो खिलाड़ी को हराने वाला पहला प्रोग्राम बना और 2016 में ली सेडोल को हराया।
संचालन का सिद्धांत
MCTS का ध्यान यादृच्छिक नमूने के आधार पर सर्च ट्री का विस्तार करके सबसे आशाजनक चालों का विश्लेषण करने पर है। प्रत्येक प्लेआउट खेल को अंत तक सिम्युलेट करता है, और परिणाम नोड्स को भार देते हैं ताकि बेहतर चालें अधिक बार चुनी जाएं। बेसिक प्योर मोंटे कार्लो गेम सर्च प्रत्येक कानूनी चाल पर समान प्लेआउट लागू करता है और सबसे अधिक जीत वाली चाल का चयन करता है।
MCTS के प्रत्येक दौर में चार चरण शामिल हैं:
- चयन: रूट से शुरू करके, लीफ नोड तक पहुंचने तक क्रमिक चाइल्ड नोड्स का चयन करें।
- विस्तार: लीफ से एक या अधिक चाइल्ड नोड्स बनाएं, जब तक कि खेल का फैसला न हो जाए।
- सिमुलेशन: नए नोड से एक यादृच्छिक प्लेआउट पूरा करें।
- बैकप्रोपेगेशन: नए नोड से रूट तक के पथ पर नोड आंकड़ों को अपडेट करें।
UCT एल्गोरिदम
UCT एल्गोरिदम ऊपरी विश्वास सीमा सूत्र का उपयोग करके अन्वेषण और दोहन को संतुलित करता है। यह चाइल्ड नोड्स का चयन उनकी औसत जीत दर और कम देखे गए नोड्स के लिए बोनस के आधार पर करता है, जिससे ट्री आशाजनक चालों की ओर विस्तार कर सकता है जबकि विकल्पों की खोज जारी रहती है। यह दृष्टिकोण MCTS दक्षता के लिए केंद्रीय है।
अनुप्रयोग
MCTS का उपयोग हेक्स, हवाना, गेम ऑफ द अमेज़न और अरिमा जैसे बोर्ड गेम के प्रोग्रामों में किया गया है, साथ ही मिसेज पैक-मैन और फेबल लीजेंड्स जैसे रीयल-टाइम वीडियो गेम में भी। यह स्कैट, पोकर, मैजिक: द गैदरिंग और सेटलर्स ऑफ कैटन जैसे गैर-नियतात्मक खेलों पर भी लागू होता है। खेलों के अलावा, MCTS की खोज योजना और अनुकूलन समस्याओं में भी की गई है।
महत्व
MCTS का गहरे न्यूरल नेटवर्क के साथ संयोजन, जैसा कि अल्फागो में है, ने कृत्रिम बुद्धिमत्ता और मशीन लर्निंग में एक मील का पत्थर साबित हुआ। इसने प्रदर्शित किया कि कैसे अनुमानी सर्च को गहन शिक्षण विधियों के साथ एकीकृत किया जा सकता है ताकि जटिल डोमेन में अलौकिक प्रदर्शन प्राप्त किया जा सके, जिसने जनरेटिव एआई में बाद के शोध को प्रभावित किया।