💻 computer science

Parallelizing Counterfactual Regret Minimization

यह शोध पत्र एक सामान्यीकृत समानांतरकरण ढांचे (parallelization framework) को प्रस्तुत करता है जो काउंटरफैक्चुअल रिग्रेट मिनिमाइजेशन (CFR) एल्गोरिदम को लीनियर अलजेब्रा ऑपरेशन्स के रूप में पुनर्गठित करता है, जिससे GPU-त्वरित कार्यान्वयन सक्षम होता है जो मौजूदा CPU-आधारित विधियों की तुलना में चार गुना अधिक क्रम (orders of magnitude) तक की गति वृद्धि प्राप्त करता है।

मूल लेखक: Juho Kim, Tuomas Sandholm

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

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

CC BY 4.0

मूल लेखक: Juho Kim, Tuomas Sandholm

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

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

हालाँकि, एक समस्या है: इस छात्र द्वारा उपयोग की जाने वाली "नोटबुक" बहुत विशाल है। यदि खेल बड़ा है, तो छात्र को अपना नोटबुक एक-एक पन्ना करके, बहुत धीरे-धीरे पढ़ना और लिखना होगा। यह एक विशाल हवेली को केवल एक टूथब्रश से साफ करने की कोशिश करने जैसा है।

यह शोध पत्र इस तरीके से उस एकल टूथब्रश को एक विशाल औद्योगिक वैक्यूम क्लीनर से बदलने का तरीका पेश करता है। लेखकों, जुहो किम और ट्यूमास सैंडहोम ने यह पता लगाया कि कैसे वे कंप्यूटर को एक साथ कई श्रमिकों का उपयोग करके सफाई (सीखने) करने के लिए सक्षम बना सकते हैं, न कि केवल एक के।

यहाँ बताया गया है कि उन्होंने इसे सरल भाषा में कैसे किया:

1. पुराना तरीका: एक लेन वाला राजमार्ग

पारंपरिक रूप से, कंप्यूटर गेम ट्री (सभी संभावित चालों का मानचित्र) को एक लंबी, घुमावदार सड़क पर चलती एक अकेली कार की तरह प्रोसेस करता है। वह हर चौराहे पर जाता है, एक निर्णय लेता है, अगले कदम पर बढ़ता है, और यही प्रक्रिया दोहराता है। भले ही आपके पास एक बहुत तेज़ कार (एक तेज़ कंप्यूटर) हो, फिर भी उसे पूरी सड़क अकेले ही तय करनी होगी। इसमें बहुत समय लगता है।

2. नया तरीका: एक असेंबली लाइन

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

उन्होंने गेम ट्री को एक घुमावदार सड़क के बजाय, एक फैक्ट्री असेंबली लाइन के रूप में पुनर्कल्पित किया।

एक कार्यकर्ता के पूरी लाइन पर चलने के बजाय, उन्होंने खेल को परतों (जैसे एक इमारत के फर्श) में विभाजित किया।
उन्होंने विशेष "लॉजिक मैट्रिसेस" (इन्हें ब्लूप्रिंट या कन्वेयर बेल्ट के रूप में सोचें) का उपयोग किया ताकि जानकारी को पूरे गेम ट्री में एक साथ ऊपर और नीचे ले जाया जा सके।
एक GPU (एक ग्राफिक्स कार्ड, जो मूल रूप से हजारों छोटे श्रमिकों वाला एक सुपर-चार्ज्ड कैलकुलेटर है) का उपयोग करके, वे एक साथ हजारों ऐसे "फ्लोर" को प्रोसेस कर सकते थे।

3. परिणाम: समय की गति बढ़ाना

लेखकों ने इस नए "असेंबली लाइन" तरीके का परीक्षण पुराने "एकल कार" तरीके के विरुद्ध सात अलग-अलग खेलों का उपयोग करके किया, जो छोटे खेलों (जैसे एक सरलीकृत पोकर गेम) से लेकर विशाल खेलों (जैसे एक जटिल बैटलशिप गेम) तक विस्तृत थे।

छोटे खेल: छोटे खेलों के लिए, नया तरीका वास्तव में धीमा था। क्यों? क्योंकि एक विशाल असेंबली लाइन स्थापित करने में समय लगता है, और एक छोटे काम के लिए, केवल एक टूथब्रश उठा लेना तेज़ होता है।
बड़े खेल: जैसे-जैसे खेल बड़े होते गए, नए तरीके की गति में जबरदस्त उछाल आया। सबसे बड़े खेलों के लिए, उनका GPU-आधारित सिस्टम एक सामान्य CPU पर चलने वाले मानक कंप्यूटर प्रोग्राम (OpenSpiel) की तुलना में 18,889 गुना तक तेज़ था।

इसे समझने के लिए: यदि पुराने तरीके को रणनीति सीखने में एक वर्ष का समय लगता, तो नया तरीका इसे लगभग 15 मिनट में कर सकता था।

4. इसका क्या अर्थ है (और क्या नहीं)

लेखक इस बात को लेकर बहुत स्पष्ट हैं कि उन्होंने क्या हासिल किया है:

उन्होंने खेल को छोटा नहीं बनाया: उन्होंने ऐसा कोई तरीका नहीं खोजा जिससे पहले असंभव माने जाने वाले खेल को हल किया जा सके।
उन्होंने समाधान को तेज़ बनाया: उन्होंने समाधान खोजने की प्रक्रिया को नाटकीय रूप रूप से तेज़ कर दिया।

यह एक केक बनाने के तेज़ तरीके जैसा है। आप अभी भी एक बार में एक ही केक बना सकते हैं और एक ही ओवन का उपयोग कर सकते हैं, लेकिन यदि आपके पास 10,000 ओवन वाली एक फैक्ट्री है, तो आप उसी केक को बहुत कम समय में बना सकते हैं।

मुख्य निष्कर्ष (Takeaway)

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

शोध पत्र विशेष रूप से उल्लेख करता है कि यह तकनीक एल्गोरिदम के सबसे उन्नत संस्करणों (जैसे CFR+, DCFR, और PCFR) के लिए काम करती है और लोकप्रिय गेम सॉफ़्टवेयर लाइब्रेरी के साथ संगत है, जो इसे आज के गेम-सॉल्विंग AI पर काम करने वाले किसी भी व्यक्ति के लिए एक व्यावहारिक उपकरण बनाती है।

तकनीकी सारांश: काउंटरफैक्चुअल रिग्रेट मिनिमाइजेशन का समानांतरकरण (Parallelizing Counterfactual Regret Minimization)

समस्या विवरण

जबकि समानांतरकरण (parallelization) कृत्रिम बुद्धिमत्ता का एक आधारशिला रहा है, जिसने बड़े मॉडलों के प्रशिक्षण समय को नाटकीय रूप से कम कर दिया है, इसका अनुप्रयोग कम्प्यूटेशनल गेम सॉल्विंग (computational game solving) में अपेक्षाकृत अनछुआ रहा है। सेफियस (Cepheus), लिब्राटस (Libratus), प्लुरिबस (Pluribus) जैसे बड़े अपूर्ण-सूचना वाले खेलों (imperfect-information games) को हल करने में किसी न किसी रूप में समानांतरता का उपयोग करने के बावजूद, काउंटरफैक्चुअल रिग्रेट मिनिमाइजेशन (CFR) एल्गोरिदम को समानांतर करने के विशिष्ट तंत्रों को सामान्यीकृत नहीं किया गया है। रेइस और रुडोल्फ (Reis and Rudolf) जैसे मौजूदा प्रयास अक्सर पुनरुत्पादकता (reproducibility) की समस्याओं से जूझते हैं, प्रत्येक थ्रेड के लिए जटिल कंट्रोल फ्लो की आवश्यकता होती है, या उप-इष्टतम द्विघाती कार्य जटिलता (suboptimal quadratic work complexity) का परिणाम देते हैं। डोमेन-विशिष्ट दृष्टिकोण (जैसे सेफियस में) में सामान्यता का अभाव है। लेखक एक सामान्यीकृत, डोमेन-स्वतंत्र ढांचे की आवश्यकता की पहचान करते हैं जो CFR और इसके टैबुलर वेरिएंट्स को उनकी प्रभावशीलता प्रदान करने वाले एल्गोरिद्मिक गुणों से समझौता किए बिना त्वरित कर सके।

कार्यप्रणाली (Methodology)

लेखक एक सामान्यीकृत समानांतरकरण ढांचे का प्रस्ताव करते हैं जो सीक्वेंस-फॉर्म संस्करण के CFR को रैखिक बीजगणित (linear algebra) संचालन की एक श्रृंखला के रूप में पुनर्गठित करता है। यह रूपांतरण गेम सॉल्विंग के लिए मानक, अत्यधिक अनुकूलित रैखिक बीजगणित तकनीकों (विशेष रूप से GPU पर) को लागू करने की अनुमति देता है।

मुख्य तकनीकी दृष्टिकोण

CFR को रैखिक बीजगणित के रूप में पुनर्गठित करना:
पेपर CFR में निहित ट्री ट्रैवर्सल चरणों (रणनीति अपडेट के लिए टॉप-डाउन और उपयोगिता अवलोकन के लिए बॉटम-अप) को मैट्रिक्स-वेक्टर ऑपरेशन्स में परिवर्तित करता है। यह लॉजिक मैट्रिसेस (मैट्रिक्स जिनमें $\{0, 1\}$ में प्रविष्टियाँ होती हैं) का उपयोग करके विभिन्न डेटा निरूपणों के बीच सामंजस्य स्थापित करता है:
- सीक्वेंस बनाम नोड निरूपण: लॉजिक मैट्रिक्स $A \in \mathbb{R}^{P \times \Sigma}$ प्रति-नोड वेक्टर्स ( $\mathbb{R}^P$ ) और प्रति-सीक्वेंस वेक्टर्स ( $\mathbb{R}^\Sigma$ ) के बीच रूपांतरण करता है।
- व्यवहार संबंधी निरूपण (Behavioral Representation): लॉजिक मैट्रिक्स $B$ व्यवहार संबंधी निरूपण ( $\mathbb{R}^{\Sigma^+}$ ) में रूपांतरण को संभालता है, जिसमें खाली अनुक्रम (empty sequence) को बाहर रखा जाता है।
- एक्शन एग्रीगेशन (Action Aggregation): लॉजिक मैट्रिक्स $C$ निर्णय बिंदुओं पर उपलब्ध क्रियाओं (actions) के माध्यम से मानों को एकत्रित करता है, जिससे मैट्रिक्स गुणन के माध्यम से L1-नॉर्मलाइजेशन और एक्सपेक्टेशन गणना संभव होती है।
समानांतर ट्री ट्रैवर्सल (Parallelized Tree Traversal):
रिकर्सिव ट्री ट्रैवर्सल के बजाय, एल्गोरिदम ट्री-फॉर्म सीक्वेंशियल डिसीजन प्रोसेस (TFSDP) को लेवल स्ट्रक्चर में विघटित करता है। एडजसेंसी मैट्रिसेस $L^{(d)}$ प्रत्येक गहराई $d$ पर किनारों (edges) का प्रतिनिधित्व करते हैं।
- टॉप-डाउन ट्रैवर्सल (रणनीति प्रसार के लिए) $L^{(1)}, L^{(2)}, \dots, L^{(k)}$ को क्रमिक रूप से लागू करके किया जाता है।
- बॉटम-अप ट्रैवर्सल (उपयोगिता संचय के लिए) इन मैट्रिसेस को उल्टे क्रम में लागू करके किया जाता है।
- ये ऑपरेशन्स कंप्रेस्ड स्पार्स रो (CSR) स्पार्स मैट्रिक्स-वेक्टर मल्टीप्लिकेशन का उपयोग करके कार्यान्वित किए जाते हैं, जो समानांतर हार्डवेयर पर अत्यधिक कुशल है।
एल्गोरिद्मिक अनुकूलन:
यह ढांचा मॉड्यूलर होने के लिए डिज़ाइन किया गया है। कोर समानांतर संचालित ऑपरेशन्स (NEXTSTRATEGY और OBSERVEUTILITY) को परिभाषित किया गया है, और विशिष्ट CFR वेरिएंट्स को इन कोर फंक्शन्स में सरल ऑपरेशन्स जोड़कर लागू किया जाता है:
- CFR+: रेग्रेट्स (regrets) में फ्लोरिंग ऑपरेशन जोड़ता है।
- डिस्काउंटेड CFR (DCFR): सकारात्मक और नकारात्मक रेग्रेट्स पर समय-निर्भर स्केलिंग कारक लागू करता है।
- प्रेडिक्टिव CFR (PCFR): तात्कालिक रेग्रेट्स के लिए एक प्रेडिक्शन वेक्टर को शामिल करता है।

मुख्य योगदान

सामान्यीकृत ढांचा: पेपर एक डोमेन-स्वतंत्र ढांचे को प्रस्तुत करता है जो CFR को रैखिक बीजगणित के रूप में मानता है, जिससे यह किसी भी टैबुलर CFR वेरिएंट (CFR, CFR+, DCFR, PCFR, PCFR+) के लिए लागू हो जाता है।
सैद्धांतिक विश्लेषण: वर्क-डेप्थ मॉडल का उपयोग करते हुए, लेखक सिद्ध करते हैं कि समानांतर एल्गोरिदम वही कुल कार्य जटिलता ( $W = \Theta(|P|)$ ) बनाए रखता है जो अनुक्रमिक सीक्वेंस-फॉर्म CFR की है, जिससे समानांतरता की अनुपस्थिति में दक्षता का कोई नुकसान नहीं होता है। डेप्थ को $D = \Theta(k \log B)$ के रूप में दिखाया गया है, जहाँ $k$ ट्री की ऊंचाई है और $B$ ब्रांचिंग फैक्टर है।
ओपन-सोर्स कार्यान्वयन: पिछले GPU प्रयासों के विपरीत, यह कार्य OpenSpiel लाइब्रेरी के साथ संगत एक ओपन-सोर्स कार्यान्वयन प्रदान करता है, जो पुनरुत्पादकता और एकीकरण की सुविधा प्रदान करता है।
स्केलेबिलिटी (Scalability): यह एल्गोरिदम केवल सबगेम बाउंड्रीज़ के बजाय हर गहराई पर गेम को विभाजित करता है, जिससे सेफियस जैसे पिछले आर्किटेक्चर की तुलना में उच्च समानांतरता प्राप्त हो सकती है।

प्रयोगात्मक परिणाम

लेखकों ने अपने GPU-त्वरित कार्यान्वयन का मूल्यांकन सात बेंचमार्क गेम्स के विभिन्न आकारों (कुह्न पोकर के 58 नोड्स से लेकर लार्ज बैटलशिप के $5.2 \times 10^7$ नोड्स तक) पर गूगल डीपमाइंड के OpenSpiel (Python और C++) CPU-आधारित कार्यान्वयन के विरुद्ध किया।

छोटे गेम्स: छोटे गेम्स (जैसे कुह्न पोकर, ल्यूड पोकर) के लिए, GPU ओवरहेड के कारण CPU कार्यान्वयन की तुलना में धीमापन होता है।
बड़े गेम्स: जैसे-जैसे गेम का आकार बढ़ता है, समानांतर कार्यान्वयन CPU बेसलाइन्स की तुलना में काफी बेहतर प्रदर्शन करता है।
- स्मॉल बैटलशिप के लिए, स्पीडअप OpenSpiel के C++ कार्यान्वयन की तुलना में लगभग $2.1 \times 10^2$ गुना तेज है।
- मीडियम बैटलशिप के लिए, स्पीडअप $1.2 \times 10^3$ तक पहुँच जाता है।
- लार्ज बैटलशिप के लिए, स्पीडअप $4.1 \times 10^3$ है।
- कुल मिलाकर, GPU कार्यान्वयन OpenSpiel के Python कार्यान्वयन की तुलना में 18,889 गुना और इसके C++ कार्यान्वयन की तुलना में 3,413 गुना तक तेज़ है।
अभिसरण (Convergence): प्रयोगों से पता चलता है कि समानांतर कार्यान्वयन वॉल-क्लॉक समय के मुकाबले समान एक्सप्लोिटेबिलिटी रिडक्शन (exploitability reduction) प्राप्त करता है, लेकिन बहुत कम समय में, और यह स्पीडअप गेम के आकार के बढ़ने के साथ अधिक स्पष्ट होता जाता है।

महत्व और दावे

पेपर दावा करता है कि जबकि यह समानांतरकरण तकनीक आवश्यक रूप से गेम के आकार (मेमोरी क्षमता के संदर्भ में) को नहीं बढ़ाती है, यह इष्टतम समाधान खोजने के लिए आवश्यक समय को नाटकीय रूप से कम करती है।

अनुसंधान त्वरण (Research Acceleration): प्राथमिक मूल्य प्रस्ताव अनुसंधानकर्ताओं को बहुत तेज़ टर्नअराउंड समय के साथ परिकल्पनाओं, नए CFR वेरिएंट्स और हाइपरपैरामीटर व्यवस्थाओं का परीक्षण करने में सक्षम बनाना है।
पुनरावृत्ति सेटिंग्स (Repetitive Settings): यह ढांचा उन खेलों के लिए विशेष रूप से उपयोगी है जो बार-बार होने वाली सेटिंग्स (जैसे अलग-अलग स्टैक साइज के साथ पोकर) में खेले जाते हैं, जहाँ व्यक्तिगत गेम ट्री समान होते हैं, जिससे तेजी से पुनः समाधान (re-solving) संभव होता है।
अनुकूलता (Compatibility): लेखक इस बात पर जोर देते हैं कि उनकी विधि OpenSpiel के साथ पूर्ण अनुकूलता बनाए रखती है, जिससे इसे गेम डेफिनिशन को फिर से लिखे बिना मौजूदा गेम-थ्योरेटिक रिसर्च के लिए एक ड्रॉप-इन एक्सेलेरेटर के रूप में उपयोग किया जा सकता है।
विनम्रता (Modesty): लेखक स्पष्ट रूप से कहते हैं कि उनका योगदान पिछले आर्किटेक्चर (जैसे सेफियस का सबगेम स्प्लिटिंग) के साथ परस्पर अनन्य (not mutually exclusive) नहीं है; बल्कि, उनकी तकनीक को और अधिक समानांतरता के लिए ऐसे आर्किटेक्चर के साथ बढ़ाया जा सकता है। वे यह भी स्वीकार करते हैं कि हालांकि वे CPU बनाम GPU की तुलना करते हैं, उनके परिणाम नियमित उपयोग के मामलों में भी समानांतरता की क्षमता को उजागर करते हैं, हालांकि वे यह दावा नहीं करते कि वे उन खेलों को हल करते हैं जो मेमोरी बाधाओं के कारण पहले हल करने योग्य नहीं थे।