Offline Nash Solvers Meet Online Tree Search in Multi-Agent Games on Graphs
यह शोध पत्र प्रिमिटिव-गाइडेड ट्री सर्च (PGTS) प्रस्तुत करता है, जो एक हाइब्रिड फ्रेमवर्क है जो ग्राफ पर मल्टी-एजेंट पर्स्यूट-इवेजन (पीछा करने और बचने वाले) खेलों को प्रभावी ढंग से हल करने के लिए सुलभ उप-खेलों (सब-गेम्स) पर ऑफलाइन सटीक नैश इक्विलिब्रियम गणनाओं को ऑनलाइन ट्री सर्च के साथ जोड़ता है, जो मौजूदा लर्निंग और ह्यूरिस्टिक बेसलाइन्स से काफी बेहतर प्रदर्शन करता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
एक विशाल, घुमावदार शहर की सड़कों वाले मानचित्र पर खेले जाने वाले एक हाई-स्टेक्स टैग (पकड़ने वाले खेल) के खेल की कल्पना करें। आपके पास "टैगर्स" (लाल टीम) की एक टीम है जो "रनर" (नीली टीम) को गुप्त निकास तक पहुँचने से पहले पकड़ने की कोशिश कर रही है। समस्या क्या है? जैसे-जैसे आप मैदान में अधिक खिलाड़ी जोड़ते हैं, संभावित चालों की संख्या विस्फोट की तरह बढ़ती जाती है। यह शतरंज के हर एक चाल की भविष्यवाणी करने की कोशिश करने जैसा है, लेकिन एक साथ लाखों मोहरे हिल रहे हैं। यदि आप एक ही समय में हर एक खिलाड़ी के लिए सटीक चाल की गणना करने की कोशिश करते हैं, तो आपका मस्तिष्क (या कंप्यूटर) गणितीय ओवरलोड के कारण क्रैश हो जाता है।
लंबे समय तक, शोधकर्ताओं ने इसे हल करने के दो मुख्य तरीके आजमाए, और दोनों में बड़ी खामियां थीं। पहला तरीका यह था कि खेल शुरू होने से पहले ही हर संभव स्थिति के लिए सटीक रणनीति को पहले से कैलकुलेट (pre-calculate) कर लिया जाए। लेकिन यह एक भूलभुलैया में प्रवेश करने से पहले उसके हर संभव रास्ते को याद करने जैसा है; यदि भूलभुलैया थोड़ी सी भी बदल जाती है, या यदि अन्य खिलाड़ी कुछ ऐसा अजीब करते हैं जिसकी आपने उम्मीद नहीं की थी, तो आपका याद किया हुआ नक्शा बेकार हो जाता है। दूसरा तरीका खेल के दौरान तुरंत सोचना (think on the fly) था, जिसमें सबसे अच्छा कदम चुनने के लिए लाखों भविष्य के परिदृश्यों का अनुकरण (simulation) किया जाता है। लेकिन इतने सारे खिलाड़ियों के साथ, शाखाओं को खोजने की संख्या इतनी विशाल हो जाती है कि कंप्यूटर उलझकर रह जाता है और समय पर सबसे अच्छा रास्ता नहीं खोज पाता।
यहाँ एक नया नायक आता है: प्रिमिटिव-गाइडेड ट्री सर्च (PGTS)। PGTS को एक स्मार्ट कोच के रूप में सोचें जो दोनों दुनियाओं के सर्वश्रेष्ठ गुणों को मिलाता है।
कोच का गुप्त हथियार: "मिनी-गेम" लाइब्रेरी
पूरे विशाल खेल को एक साथ हल करने के बजाय, PGTS कोच खेल शुरू होने से पहले लाइब्रेरी में जाता है और खेल के कई छोटे, सरल संस्करणों को हल करता है। इन्हें "प्रिमिटिव सब-टीम गेम्स" कहा जाता है।
- कल्पना करें कि 1-ब-1 टैग गेम को हल करना।
- फिर 2-ब-1 गेम (दो टैगर बनाम एक रनर)।
कोच इन छोटे खेलों को पूरी तरह से हल करता है और उत्तरों को एक "चीट शीट" (पॉलिसी और वैल्यूज का कैश) में लिख देता है। यह ऑफलाइन हिस्सा है। यह तेज़ है क्योंकि खेल छोटे हैं।
गेम डे: स्मार्ट ट्री सर्च
जब वास्तविक खेल शुरू होता है, तो कोच केवल अनुमान नहीं लगाता, और न ही वह पुराने चीट शीट पर निर्भर रहता है। वे एक ट्री सर्च (Tree Search) का उपयोग करते हैं, जो सड़क के मोड़ पर आगे क्या है, यह देखने जैसा है। लेकिन यहाँ जादू है:
- गाइडेड एक्सपेंशन (Guided Expansion): हर संभव चाल को देखने के बजाय (जिसमें बहुत समय लगेगा), कोच चीट शीट का उपयोग करके केवल उन चालों को देखता है जो उन छोटे 1-ब-1 और 2-ब-1 खेलों के आधार पर आशाजनक लगती हैं। यह कोच के कहने जैसा है, "हे, 2-ब-1 की स्थिति में, टैगर्स आमतौर पर यह करते हैं, इसलिए आइए अपनी सोच वहीं केंद्रित करें।"
- लीफ वैल्यू एस्टीमेशन (Leaf Value Estimation): जब कोच विचार पथ के अंत (एक "लीफ" या पत्ती) पर पहुँचता है, तो उसे खेल के अंत तक पूरे खेल का अनुकरण करने की आवश्यकता नहीं होती। वे बस वर्तमान स्थितियों को देखते हैं, बड़ी टीम को वापस उन छोटे 1-ब-1 और 2-ब-1 समूहों में तोड़ देते हैं, और अंतिम स्कोर का अनुमान लगाने के लिए पूर्व-निर्धारित चीट शीट का उपयोग करते हैं।
यह टीम को एक पूरे समूह के रूप में पूरी तरह से समन्वय करने की अनुमति देता है, जबकि वे छोटे 1-ब-1 और 2-ब-1 खेलों के उपयोग से गति भी बनाए रखते हैं।
पेपर क्या कहता है (और क्या नहीं कहता)
लेखकों ने इस नए कोच का परीक्षण कई अलग-अलग मानचित्रों पर किया, जिसमें एक 7x7 ग्रिड, एक जटिल "स्कॉटलैंड यार्ड" मैप, और अटलांटा का एक वास्तविक दुनिया का मैप (151 नोड्स के साथ) शामिल था। उन्होंने सिमुलेशन चलाए जहाँ ग्रिड पर खेल 6 टाइम स्टेप्स तक चला और बड़े मैप्स पर 9 टाइम स्टेप्स तक चला।
परिणाम प्रभावशाली थे। इन सिमुलेशन में, PGTS टीम (चाहे "रिग्रेट मैचिंग" या "डिकपल्ड UCT" निर्णय शैली का उपयोग कर रही हो) ने लगातार मौजूदा सर्वोत्तम तरीकों को पछाड़ दिया।
- ट्रिकी "ग्रिड 2" मैप पर, पुराने तरीकों ने लगभग 0.25 से 0.37 का वर्स्ट-केस यूटिलिटी स्कोर किया, जबकि PGTS ने 0.40 से 0.46 स्कोर किया।
- स्कॉटलैंड यार्ड मैप पर, अंतर बहुत बड़ा था: पुराने तरीकों ने 0.00 या 0.05 जितना कम स्कोर किया, जबकि PGTS ने 0.68 से 0.73 स्कोर किया।
- एक "स्मार्ट" रनर के खिलाफ भी, जो केवल सीधी रेखा में नहीं भाग रहा था, PGTS ने अपनी पकड़ बनाए रखी, जबकि अन्य तरीके (जिन्हें साधारण रनर्स पर प्रशिक्षित किया गया था) विफल हो गए।
पेपर स्पष्ट रूप से ट्री सर्च के बिना केवल पूर्व-निर्धारित मिनी-गेम्स (डिकम्पोजिशन) पर निर्भर रहने के खिलाफ तर्क देता है। उन्होंने पाया कि हालांकि मिनी-गेम्स अच्छे हैं, वे यह पकड़ने में विफल रहते हैं कि पूरी टीम को मिलकर कैसे काम करना चाहिए। यदि आप केवल मिनी-गेम्स का उपयोग करते हैं, तो टीम का समन्वय टूट जाता है और प्रदर्शन काफी गिर जाता है। ट्री सर्च वह गोंद है जो टीम के समन्वय को एक साथ रखता है।
निष्कर्ष
यह कोई जादुई छड़ी नहीं है जो ब्रह्मांड की हर समस्या को हल कर दे, लेकिन इन विशिष्ट सिमुलेशन की दुनिया में, यह गेम-चेंजर है। लेखक दिखाते हैं कि एक विशाल, डरावनी समस्या को छोटे, हल करने योग्य टुकड़ों में तोड़कर और फिर उन टुकड़ों का उपयोग एक स्मार्ट सर्च को गाइड करने के लिए करके, आप सबसे अच्छी मौजूदा रणनीतियों को हरा सकते हैं। उन्होंने विभिन्न ग्राफ टोपोलॉजी पर व्यापक कंप्यूटर सिमुलेशन के माध्यम से यह सिद्ध किया, जिससे यह दिखाया गया कि उनकी विधि मजबूत है, भले ही दूसरी टीम चालाक होने की कोशिश करे।
पेपर सुझाव देता है कि इस दृष्टिकोण को अन्य प्रकार के मल्टी-एजेंट गेम्स और ऐसी स्थितियों में भी विस्तारित किया जा सकता है जहाँ आप सब कुछ नहीं देख सकते (पार्शियल ऑब्जर्वेबिलिटी), लेकिन फिलहाल, उन्होंने इसे केवल इन विशिष्ट पर्सूट-इवेजन (पीछा करने और बचने वाले) सिमुलेशन में प्रदर्शित किया है। यह एक चतुर तकनीक है जो एक गणितीय दुःस्वप्न को एक प्रबंधनीय पहेली में बदल देती है, यह साबित करती है कि कभी-कभी, बड़े खेल को जीतने का सबसे अच्छा तरीका पहले छोटे खेलों में महारत हासिल करना होता है।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।