🤖 AI

Global Policy-Space Response Oracles for Two-Player Zero-Sum Games

यह शोधपत्र ग्लोबल PSRO को प्रस्तुत करता है, जो दो-खिलाड़ी शून्य-योग खेलों (two-player zero-sum games) के लिए एक नवीन एल्गोरिदम है, जो जनसंख्या शोषणशीलता (Population Exploitability) को सीधे कम करने के लिए एक दो-चरणीय अन्वेषण-चयन ढांचे का उपयोग करके मौजूदा पॉलिसी-स्पेस रिस्पांस ओरेकल (PSRO) विधियों में सुधार करता है, जिससे कम पॉलिसी पुनरावृत्तियों (policy iterations) के साथ नैश इक्विलिब्रियम (Nash equilibria) की ओर कम शोषणशीलता और तेज़ अभिसरण (faster convergence) प्राप्त होता है।

मूल लेखक: Junyu Zhang, Feihong Yang, Jian Wang, Chao Wang, Xudong Zhang

प्रकाशित 2026-05-28

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Junyu Zhang, Feihong Yang, Jian Wang, Chao Wang, Xudong Zhang

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

मुख्य चित्र: एक विशाल खेल में पूर्ण रणनीति खोजना

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

इसे हल करने के लिए, शोधकर्ता PSRO (पॉलिसी-स्पेस रिस्पांस ओरेकल) नामक एक विधि का उपयोग करते हैं। PSRO को खिलाड़ियों की एक टीम के लिए एक ट्रेनिंग कैंप के रूप में समझें।

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

लक्ष्य एक ऐसी छोटी टीम बनाना है जो इतनी अच्छी हो कि वह बिल्कुल उस "परफेक्ट" टीम की तरह कार्य करे जो तब मौजूद होती यदि आप पूरे ब्रह्मांड के हर संभव मूव के विरुद्ध अभ्यास कर सकते।

समस्या: "लोकल हीरो" का जाल

यह पेपर तर्क देता है कि इस ट्रेनिंग कैंप को चलाने के पुराने तरीके में एक दोष है।

पुराना तरीका (प्रतिबंधित-गेम-आधारित):
कल्पना कीजिए कि आपका ट्रेनिंग कैंप एक छोटा, बंद कमरा है। कोच एक नया चैलेंजर इस आधार पर चुनता है कि वह उस छोटे कमरे के अंदर वर्तमान टीम को कैसे हराता है।

समस्या: एक चैलेंजर एक "लोकल हीरो" हो सकता है। वे उस छोटे कमरे में वर्तमान टीम को हराने में माहिर होते हैं, लेकिन वे वास्तविक, बड़े खेल के लिए बहुत खराब हो सकते हैं।
परिणाम: आप लगातार "लोकल हीरोज" को जोड़ते रहते हैं। आपकी टीम उस छोटे कमरे में खेलने में बेहतर और बेहतर होती जाती है, लेकिन आप अपना समय और पैसा बर्बाद कर रहे हैं। आपको टीम में वास्तव में अच्छा खिलाड़ी जोड़ने से पहले लगभग हर एक संभव खिलाड़ी को जोड़ना पड़ सकता है। यह अक्षम है।

समाधान: "ग्लोबल स्काउट" (ग्लोबल PSRO)

लेखक एक नई विधि प्रस्तावित करते हैं जिसे Global PSRO कहा जाता है। केवल यह देखने के बजाय कि छोटे कमरे में कौन जीतता है, वे पूछते हैं: "यदि हम इस नए खिलाड़ी को अपनी टीम में जोड़ते हैं, तो इससे पूरे खेल में हमारे जीतने की संभावना कितनी बढ़ जाती है?"

वे पॉपुलेशन एक्सप्लॉयटेबिलिटी (PE) नामक एक मीट्रिक का उपयोग करते हैं। PE को एक "कमजोरी स्कोर" के रूप में समझें।

उच्च PE: आपकी टीम में एक बड़ा छेद है जिसका एक स्मार्ट प्रतिद्वंद्वी फायदा उठा सकता है।
कम PE: आपकी टीम ठोस है; उसे हराना कठिन है।

Global PSRO कैसे काम करता है (दो-चरणों की प्रक्रिया):

चरण 1: कास्टिंग कॉल (एक्सप्लोरेशन/अन्वेषण)
सिर्फ एक नया खिलाड़ी मांगने के बजाय, कोच उम्मीदवारों का एक बैच मांगता है। वे इन उम्मीदवारों को वर्तमान टीम के कई अलग-अलग संस्करणों के खिलाफ प्रशिक्षित करते हैं, न कि केवल "सर्वश्रेष्ठ" के खिलाफ। यह संभावित नए खिलाड़ियों का एक विविध पूल बनाता है।
चरण 2: ऑडिशन (चयन)
यही जादुई हिस्सा है। कोच केवल उस उम्मीदवार को नहीं चुनता जो ऑडिशन में सबसे अधिक मैच जीता हो। इसके बजाय, वे सिमुलेशन चलाते हैं: "यदि हम कैंडिडेट A को टीम में जोड़ते हैं, तो हमारी नई कमजोरी का स्कोर (PE) क्या होगा?" फिर वे यही कैंडिडेट B, कैंडिडेट C, आदि के लिए करते हैं।

वे उस उम्मीदवार को चुनते हैं जिसके परिणामस्वरूप पूरी टीम का न्यूनतम कमजोरी स्कोर (Lowest Weakness Score) प्राप्त होता है।
वे एक "सेफ्टी नेट" खिलाड़ी (नई टीम के लिए बेस्ट रिस्पांस) भी जोड़ते हैं ताकि यह सुनिश्चित हो सके कि उन्होंने कुछ मिस नहीं किया है।

उपमा (Analogy):
कल्पना कीजिए कि आप एक सॉकर टीम बना रहे हैं।

पुराना तरीका: आप लगातार ऐसे खिलाड़ियों को साइन करते रहते हैं जो आपकी वर्तमान डिफेंस के खिलाफ गोल करने में माहिर हैं, भले ही वे वास्तविक लीग की गति को नहीं संभाल सकते। अंत में, आपके पास 50 खिलाड़ियों की एक ऐसी टीम होती है जो अभ्यास में तो बहुत अच्छे हैं लेकिन वास्तविक मैच हार जाते हैं।
Global PSRO: आप 10 नए खिलाड़ियों का परीक्षण करते हैं। प्रत्येक के लिए, आप एक सिमुलेशन चलाते हैं: "यदि हम प्लेयर X को साइन करते हैं, तो दुनिया की सर्वश्रेष्ठ विपक्षी टीम हमारे खिलाफ कितने गोल करेगी?" आप उस खिलाड़ी को साइन करते हैं जो आपकी टीम को वास्तविक दुनिया में सबसे कठिन मुकाबले वाली टीम बनाता है, भले ही वे अभ्यास में सबसे शानदार स्कोरर न रहे हों।

यह क्यों महत्वपूर्ण है

यह पेपर गणितीय रूप से सिद्ध करता है और पोकर और लियार्स डाइस जैसे खेलों के माध्यम से प्रयोगों द्वारा दिखाता है कि यह नई विधि बहुत अधिक कुशल है।

तेज़: यह बहुत कम ट्रेनिंग स्टेप्स के साथ "परफेक्ट" स्तर तक पहुँच जाता है।
स्मार्ट: यह उन खिलाड़ियों को जोड़ने के जाल से बचता है जो केवल खेल के सीमित दृश्य में अच्छे दिखते हैं।
मजबूत (Robust): यह एक चतुर ट्रिक (कंप्यूटर ब्रेन पैरामीटर्स साझा करना) का उपयोग करता है ताकि सुपरकंप्यूटर की आवश्यकता के बिना एक साथ कई उम्मीदवारों का परीक्षण किया जा सके।

सारांश

यह पेपर Global PSRO पेश करता है, जो जटिल खेलों के लिए AI को प्रशिक्षित करने का एक स्मार्ट तरीका है। केवल वर्तमान अभ्यास मैच में जीतने के आधार पर अगला खिलाड़ी चुनने के बजाय, यह उस खिलाड़ी को चुनता है जो पूरी टीम को वास्तविक दुनिया के खिलाफ सबसे मजबूत बनाता है। यह एक ऐसे कर्मचारी को काम के विवरण (Job Description) के अनुसार काम करने के लिए रखने और एक ऐसे कर्मचारी को रखने के बीच का अंतर है जो वास्तव में कंपनी की सबसे बड़ी समस्याओं को हल करता है।

तकनीकी सारांश: दो-खिलाड़ी शून्य-योग खेलों के लिए ग्लोबल पॉलिसी-स्पेस रिस्पॉन्स ओरेकल (Global Policy-Space Response Oracles)

1. समस्या विवरण (Problem Statement)

बड़े पैमाने के दो-खिलाड़ी शून्य-योग (two-player zero-sum) खेलों में नैश इक्विलिब्रियम (Nash equilibria) की गणना करना कम्प्यूटेशनल रूप से कठिन है क्योंकि उनके स्ट्रैटेजी स्पेस अत्यंत विशाल होते हैं। पॉलिसी-स्पेस रिस्पॉन्स ओरेकल (PSRO) फ्रेमवर्क एक सीमित स्ट्रैटेजी सेट (पॉपुलेशन) को पुनरावृत्ति (iteratively) के माध्यम से विस्तारित करके और प्रेरित "मेटा-गेम" को हल करके इस समस्या का समाधान करता है, जिसमें आमतौर पर बेस्ट रिस्पॉन्स (BRs) उत्पन्न करने के लिए डीप रिइन्फोर्समेंट लर्निंग (DRL) का उपयोग किया जाता है।

PSRO में एक केंद्रीय चुनौती स्ट्रैटेजी पॉपुलेशन कंस्ट्रक्शन है: सीमित कम्प्यूटेशनल बजट के तहत एक स्ट्रैटेजी सेट को कैसे असेंबल किया जाए ताकि प्रेरित प्रतिबंधित खेल (restricted game) पूर्ण खेल का सटीक अनुमान लगा सके। मौजूदा PSRO वेरिएंट्स रिस्ट्रिक्टेड-गेम-बेस्ड मेटा-स्ट्रैटेजी सॉल्वर्स (RGB-MSSs) पर निर्भर करते हैं, जो वर्तमान प्रतिबंधित खेल के पे-ऑफ मैट्रिक्स का उपयोग करके मेटा-स्ट्रैटेजी की गणना करते हैं। लेखक तर्क देते हैं कि यह दृष्टिकोण अक्षम विस्तार (inefficient expansions) की ओर ले जाता है। क्योंकि RGB-MSSs वर्तमान पॉपुलेशन के बाहर की रणनीतियों की अनदेखी करते हैं, इसलिए परिणामी BRs स्थानीय रूप से मजबूत हो सकते हैं, लेकिन वे ग्लोबल एक्सप्लोइटेबिलिटी (पूर्ण-खेल इक्विलिब्रियम से दूरी) को कम करने में बहुत कम योगदान देते हैं। सबसे खराब स्थितियों में, RGB-MSSs को पूरे स्ट्रैटेजी स्पेस को शामिल करने की आवश्यकता हो सकती है, भले ही एक बहुत छोटा इक्विलिब्रियम सपोर्ट मौजूद हो।

2. कार्यप्रणाली: ग्लोबल PSRO (Methodology: Global PSRO)

लेखक ग्लोबल PSRO का प्रस्ताव करते हैं, जो एक कैंडिडेट स्ट्रैटेजी जोड़े जाने के बाद पॉपुलेशन की गुणवत्ता को स्पष्ट रूप से अनुकूलित (optimize) करके पॉपुलेशन विस्तार को निर्देशित करता है। इस गुणवत्ता के लिए मुख्य मीट्रिक पॉपुलेशन एक्सप्लोइटेबिलिटी (PE) है, जिसे पूर्ण-खेल विरोधियों के विरुद्ध प्रतिबंधित पॉपुलेशन पर समर्थित किसी भी मिश्रित रणनीति (mixed strategy) द्वारा प्राप्त न्यूनतम एक्सप्लोइटेबिलिटी के रूप में परिभाषित किया गया है।

कार्यप्रणाली एक दो-चरणीय एक्सप्लोरेशन-सिलेक्शन (Exploration–Selection) फ्रेमवर्क से बनी है:

चरण I: एक्सप्लोरेशन (Exploration)

एक एकल मेटा-स्ट्रैटेजी के विरुद्ध एक एकल BR प्रशिक्षित करने के बजाय, ग्लोबल PSRO विविध कैंडिडेट रिस्पॉन्स का एक पूल बनाता है।

मिक्सचर पूल (Mixture Pool): एक मेटा-स्ट्रैटेजीज़ का सेट $S_t = \{\sigma_k\}_{k=1}^K$ बनाया जाता है। इसमें एक बेस मेटा-स्ट्रैटेजी (जैसे, एक मानक RGB-MSS जैसे कि Restricted-Game NE से) और प्रोबेबिलिटी सिम्प्लेक्स से समान रूप से सैंपल की गई $K-1$ अतिरिक्त मिश्रण (mixtures) शामिल हैं (उदाहरण के लिए, डिरिचलेट वितरण के माध्यम से)।
कंडीशनल ट्रेनिंग (Conditional Training): मल्टी-कैंडिडेट ट्रेनिंग को व्यवहार्य बनाने के लिए, एक एकल कंडीशनल पॉलिसी नेटवर्क $\pi_\theta(a|s, \sigma)$ को DRL (PPO) के माध्यम से प्रशिक्षित किया जाता है ताकि प्रत्येक $\sigma_k \in S_t$ के लिए अनुकूलित रिस्पॉन्स आउटपुट किया जा सके। इससे कैंडिडेट स्ट्रैटेजीज़ का एक सेट $\{\pi_k\}$ प्राप्त होता है।

चरण II: सिलेक्शन (Selection)

फ्रेमवर्क यह मूल्यांकन करता है कि कौन सा कैंडिडेट, यदि पॉपुलेशन में जोड़ा जाता है, तो सबसे कम PE परिणामी होगा।

PE एस्टीमेशन (PE Estimation): प्रत्येक कैंडिडेट एक्सपेंशन $\Pi_r \cup \{\pi_k\}$ के लिए, एल्गोरिदम PE का अनुमान लगाता है। यह एक रिग्रेट मिनिमाइजेशन (RM) – बेस्ट रिस्पॉन्स प्रक्रिया का उपयोग करके किया जाता है। प्रत्येक कैंडिडेट के लिए रिग्रेट-मिनिमाइजिंग मिश्रण $\rho_k$ के विरुद्ध बेस्ट रिस्पॉन्स को ट्रैक करने के लिए एक कंडीशनल इवैल्यूएटर नेटवर्क $\beta_\psi(a|s, \sigma)$ का उपयोग किया जाता है।
रेगुलराइज्ड स्कोरिंग (Regularized Scoring): एस्टीमेशन एरर्स के विरुद्ध मजबूती सुनिश्चित करने के लिए (जहाँ एक कैंडिडेट केवल इसलिए अच्छा लग सकता है क्योंकि उसे एस्टीमेशन मिश्रण में कम बार खेला जाता है), एक रेगुलराइज्ड स्कोर का उपयोग किया जाता है:
$\widehat{PE}^{reg}_k = (1 - \hat{p}_k)(\widehat{PE}(\Pi_r; G) - U(\beta_k, \rho_r)) + \widehat{PE}_k$
जहाँ $\hat{p}_k$ मिश्रण में नई स्ट्रैटेजी को दिया गया मास (mass) है।
एक्सपेंशन (Expansion): वह कैंडिडेट $k^*$ जो रेगुलराइज्ड PE को न्यूनतम करता है, उसे चुना जाता है। पॉपुलेशन को चुने गए कैंडिडेट $\pi_{k^*}$ और संबंधित इवैल्यूएशन BR $\beta_{k^*}$ (एक Anytime-PSRO स्टाइल एक्सपेंशन) को जोड़कर विस्तारित किया जाता है।

3. प्रमुख योगदान (Key Contributions)

RGB-MSS सीमाओं का सैद्धांतिक विश्लेषण: लेखक सिद्ध करते हैं कि केवल प्रतिबंधित-गेम पे-ऑफ्स (RGB-MSSs) पर निर्भर रहने से अत्यधिक अक्षम पॉपुलेशन विस्तार हो सकता है। वे थ्योरम 3.2 के माध्यम से प्रदर्शित करते हैं कि किसी भी RGB-MSS के लिए, ऐसे खेल मौजूद हैं जहाँ अभिसरण (convergence) के लिए सभी $N$ प्योर स्ट्रैटेजीज़ को जोड़ने की आवश्यकता होती है, जबकि एक इंस्टेंस-स्पेसिफिक सॉल्वर $O(S)$ इटरेशन में इक्विलिब्रियम तक पहुँच सकता है (जहाँ $S$ इक्विलिब्रियम सपोर्ट साइज है)।
ऑप्टिमाइज़ेशन फॉर्मूलेशन: वे स्ट्रैटेजी पॉपुलेशन कंस्ट्रक्शन को एक स्पष्ट ऑप्टिमाइज़ेशन समस्या के रूप में फॉर्म्युलेट करते हैं: पोस्ट-एक्सपेंशन PE को कम करना। यह विस्तार प्रक्रिया को पूर्ण-खेल इक्विलिब्रियम के प्राथमिक लक्ष्य के साथ सीधे संरेखित करता है।
ग्लोबल PSRO एल्गोरिदम: वे इस फ्रेमवर्क को एक स्केलेबल DRL-आधारित एल्गोरिदम के रूप में स्थापित करते हैं। प्रमुख तकनीकी नवाचारों में शामिल हैं:
- पैरामीटर शेयरिंग (Parameter Sharing): कई कैंडिडेट उत्पन्न करने और PE को एक साथ अनुमानित करने के लिए कंडीशनल न्यूरल नेटवर्क का उपयोग करना, जिससे कम्प्यूटेशनल लागत कम हो जाती है।
- रेगुलराइज्ड सिलेक्शन (Regularized Selection): एक स्कोरिंग मैकेनिज्म जो उन कैंडिडेट्स के चयन को रोकता है जो केवल एस्टीमेशन नॉइज़ के कारण फायदेमंद दिखाई देते हैं।
अभिसरण गारंटी (Convergence Guarantees): एक सटीक ऑरेकल की धारणा के तहत, यह फ्रेमवर्क मानक PSRO के परिमित-इटरेशन अभिसरण (finite-iteration convergence) गुणों को बनाए रखता है, जबकि एडवर्सरियल गेम फैमिलीज़ में बेहतर इटरेशन कॉम्प्लेक्सिटी प्रदान करता है (थ्योरम 4.3)।

4. प्रयोगात्मक परिणाम (Experimental Results)

प्रयोग मानक दो-खिलाड़ी शून्य-योग एक्सटेंसिव-फॉर्म गेम्स पर किए गए: कुहन पोकर (Kuhn Poker), लियार्स डाइस (Liar's Dice), लुडेक पोकर (Leduc Poker), और गूफ़स्पिएल (Goofspiel - 5 और 13 कार्ड)।

PSRO वेरिएंट्स के साथ तुलना: मैच किए गए एनवायरनमेंट इंटरेक्शन बजट के तहत, ग्लोबल PSRO ने नैश, अल्फा रैंक, PRD, यूनिफॉर्म और एनीटाइम PSRO सॉल्वर्स का उपयोग करने वाले मानक PSRO वेरिएंट्स की तुलना में लगातार कम पॉपुलेशन एक्सप्लोइटेबिलिटी (PE) प्राप्त की। सुधार बड़े खेलों (लुडेक पोकर, गूफ़स्पिएल) में सबसे महत्वपूर्ण था।
डाइवर्सिटी-ड्रिवन मेथड्स के साथ तुलना: ग्लोबल PSRO ने PSD-PSRO (एक डाइवर्सिटी-ड्रिवन वेरिएंट) को पछाड़ दिया, जो यह दर्शाता है कि केवल विविध एडिशन को प्रोत्साहित करना, स्पष्ट रूप से PE को कम करने के लिए चयन करने की तुलना में कम प्रभावी है। ग्लोबल PSRO के एक्सप्लोरेशन फेज में डाइवर्सिटी ऑब्जेक्टिव जोड़ने से कुछ खेलों में मामूली लाभ हुआ।
कंडीशनल पॉपुलेशन मेथड्स के साथ तुलना: ग्लोबल PSRO ने न्यूPL (NeuPL) को पछाड़ दिया, जो कंडीशनल पैरामीटर शेयरिंग का भी उपयोग करता है। यह प्रदर्शन में सुधार को केवल पैरामीटर शेयरिंग आर्किटेक्चर के बजाय सिलेक्शन मैकेनिज्म (पोस्ट-एक्सपेंशन PE को कम करना) के कारण आइसोलेट करता है।
एब्लेशन स्टडीज (Ablation Studies): किसी भी घटक को हटाने (जैसे, केवल एक्सप्लोइटेशन का उपयोग करना, रैंडम सिलेक्शन, या PE रेगुलराइजेशन को हटाना) से प्रदर्शन में गिरावट आई, जिससे पुष्टि हुई कि ग्लोबल इंफॉर्मेशन एक्सप्लोरेशन और PE-बेस्ड सिलेक्शन का संयोजन महत्वपूर्ण है।

5. महत्व और दावे (Significance and Claims)

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

लेखक ग्लोबल PSRO को बड़े पैमाने के शून्य-योग खेलों के लिए एक व्यावहारिक, स्केलेबल समाधान के रूप में प्रस्तुत करते हैं जो कम पॉलिसी इटरेशन के साथ बेहतर इक्विलिब्रियम एप्रोक्सिमेशन प्राप्त करता है। वे उल्लेख करते हैं कि उनका चर्चा दो-खिलाड़ी शून्य-योग खेलों तक सीमित है, क्योंकि मल्टीप्लेयर जनरल-सम सेटिंग्स में PE मीट्रिक को विस्तारित करना गैर-तुच्छ (non-trivial) है क्योंकि इसमें सैडल-पॉइंट स्ट्रक्चर का नुकसान होता है। भविष्य के कार्य के रूप में व्यापक गेम क्लासों के लिए फ्रेमवर्क का विस्तार करने और उन सेटिंग्स के लिए स्केलेबल PE एप्रोक्सिमेशन विकसित करने का सुझाव दिया गया है।