💻 computer science

An ASP-based approach to Solving General Stochastic Two-Player Games

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

मूल लेखक: Yifan He, Michael Thielscher

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

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

CC BY 4.0

मूल लेखक: Yifan He, Michael Thielscher

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

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

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

यहाँ उनके दृष्टिकोण का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है:

1. समस्या: "रैंडम" खिलाड़ी

मानक गेम थ्योरी में, कंप्यूटर दो बुद्धिमान खिलाड़ियों (जैसे शतरंज) के खिलाफ सटीक चाल चलने में बहुत अच्छे होते हैं। लेकिन जब आप इसमें अनिश्चितता/रैंडमनेस (जैसे पासा फेंकना या कार्ड निकालना) जोड़ देते हैं, तो गणित जटिल हो जाता है।

पुराना तरीका: पिछले कंप्यूटर प्रोग्राम दो बुद्धिमान खिलाड़ियों (जैसे शतरंज) वाले खेल या एक खिलाड़ी और एक रैंडम तत्व (जैसे सॉलिटेयर) वाले खेल को संभाल सकते थे। वे एक साथ दो बुद्धिमान खिलाड़ियों और एक रैंडम तत्व वाले खेल को नहीं संभाल सकते थे।
लक्ष्य: लेखक "जनरल स्टोकेस्टिक टू-प्लेयर गेम्स" को हल करना चाहते थे। इसे टिक-टैक-टो के रूप में सोचें, जहाँ हर बार जब आप 'X' रखने की कोशिश करते हैं, तो 30% संभावना होती है कि वह स्थान 'O' में बदल जाए, या 50% संभावना होती है कि आपकी चाल पूरी तरह से बाधित हो जाए।

2. नया टूल: SQASP (एक "जादुई ब्लूप्रिंट")

लेखकों ने एक नई भाषा बनाई जिसे स्टोकेस्टिक आंसर सेट प्रोग्रामिंग (SQASP) कहा जाता है।

उपमा: कल्पना कीजिए कि आप एक घर डिजाइन कर रहे हैं। आपके पास एक ब्लूप्रिंट (खेल के नियम) है। अतीत में, आप केवल दो विशिष्ट प्रकार के बिल्डरों के लिए घर डिजाइन कर सकते थे: एक जो एक जीनियस रणनीतिकार (प्रतिद्वंद्वी) है और दूसरा जो सख्त नियमों का पालन करने वाला एक रोबोट है।
नवाचार: SQASP एक नए प्रकार का ब्लूप्रिंट जैसा है जो एक निर्माण स्थल का वर्णन कर सकता है जहाँ एक जीनियस रणनीतिकार, एक रोबोट और एक जुआरी (Gambler) मिलकर काम कर रहे हैं।
- जीनियस (खिलाड़ी X) जीतना चाहता है।
- प्रतिद्वंद्वी (खिलाड़ी O) खिलाड़ी X को रोकने की कोशिश करता है।
- जुआरी (रैंडम) यह तय करने के लिए सिक्का उछालता है कि आगे क्या होगा।
SQASP कंप्यूटर को यह पूछने की अनुमति देता है: "जीतने की मेरी उच्चतम संभव संभावना क्या है, यह मानते हुए कि मेरा प्रतिद्वंद्वी मुझे रोकने के लिए पूरी तरह से खेल रहा है, और जुआरी जो चाहे वह कर सकता है?"

3. ट्रांसलेटर: ब्लूप्रिंट को पहेली में बदलना

कंप्यूटर "ब्लूप्रिंट" की भाषा नहीं समझते। वे "लॉजिक पज़ल" (तर्क पहेली) की भाषा समझते हैं।

प्रक्रिया: लेखकों ने एक ट्रांसलेटर बनाया (एक टूल जिसे sqasp2x2ssat कहा जाता है)। यह उनके फैंसी SQASP ब्लूप्रिंट को लेता है और उसे एक्सटेंडेड स्टोकेस्टिक सैटिस्फिएबिलिटी (XSSAT) नामक एक विशाल लॉजिक पहेली में बदल देता है।
रूपक: कल्पना कीजिए कि SQASP केक बनाने की एक जटिल रेसिपी है। ट्रांसलेटर एक मशीन है जो उस रेसिपी को एक विशाल, बहु-स्तरीय सुडोकू पहेली में बदल देती है। एक बार जब पहेली हल हो जाती है, तो उत्तर आपको जीतने की सटीक संभावना बताता है।
सॉल्वर: उन्होंने इस सुडोकू को सुलझाने के लिए एक मौजूदा सॉल्वर (SharpSSAT) का उपयोग किया। यदि सॉल्वर कहता है "हाँ, इस पहेली को हल किया जा सकता है," तो इसका मतलब है कि खिलाड़ी के पास जीतने की रणनीति है। यदि यह 67% की संभावना की गणना करता है, तो वह सबसे अच्छा संभव परिणाम है।

4. "क्वांटिफायर शिफ्टिंग" का कमाल

पेपर ने क्वांटिफायर शिफ्टिंग (Quantifier Shifting) नामक एक विशिष्ट अनुकूलन तकनीक का भी परीक्षण किया।

उपमा: कल्पना कीजिए कि आप एक टूर्नामेंट आयोजित कर रहे हैं।
- विधि A (बेसलाइन): आप प्रत्येक खिलाड़ी की चाल को सूचीबद्ध करते हैं, फिर जांचते हैं कि चालें वैध हैं या नहीं, फिर देखते हैं कि खेल समाप्त हुआ या नहीं।
- विधि B (शिफ्टिंग): आप चालों को सूचीबद्ध करने से पहले ही जांच लेते हैं कि चालें वैध हैं या नहीं। यह तेज़ लगता है क्योंकि आप उन चालों की योजना बनाने में समय बर्बाद नहीं करते जो अवैध हैं।
परिणाम: दो बुद्धिमान खिलाड़ियों वाले खेलों (डिटरमिनिस्टिक गेम्स) में, यह "शिफ्टिंग" तकनीक एक बड़ी गति वृद्धि (speed boost) है। हालाँकि, लेखकों ने पाया कि "जुआरी" (स्टोकेस्टिक गेम्स) वाले खेलों में, इस तकनीक से कोई खास फर्क नहीं पड़ा।
क्यों? उनके द्वारा उपयोग किया गया सॉल्वर (SharpSSAT) बहुत स्मार्ट है। इसमें एक अंतर्निहित "डिटेक्टिव" (जिसे यूनिट प्रोपेगेशन कहा जाता है) है जो अपने आप अवैध चालों का पता लगा लेता है, चाहे आपने निर्देश किस भी क्रम में दिए हों। इसलिए, निर्देशों को पुनर्व्यवस्थित करने की आवश्यकता नहीं थी।

5. परिणाम: इसने कैसा प्रदर्शन किया?

टीम ने टिक-टैक-टो, कनेक्ट-4 और निम (Nim) जैसे क्लासिक खेलों के विविध संस्करणों पर अपने सिस्टम का परीक्षण किया, जिसमें "रैंडम" खिलाड़ी को जोड़ा गया था।

प्रदर्शन: उनकी नई विधि मानक "फॉरवर्ड सर्च" विधियों (जो कि एक कंप्यूटर के मन में लाखों बार खेल खेलने जैसा है) के प्रतिस्पर्धी रही।
कमी: यह छोटे बोर्डों (जैसे 3x3 या 4x4) पर बहुत अच्छा काम करता है। हालाँकि, जब खेल बहुत बड़ा हो जाता है (जैसे निम में 100 टुकड़ों का ढेर), तो लॉजिक पहेली इतनी बड़ी हो जाती है कि कंप्यूटर के लिए इसे उचित समय में हल करना कठिन हो जाता है।
निष्कर्ष: यह विधि एंडगेम इवैल्यूएशन (अंत के खेल का मूल्यांकन) के लिए उत्कृष्ट है। यदि खेल लगभग समाप्त होने वाला है, तो यह सिस्टम एक सामान्य गेम-प्लेइंग AI को बता सकता है, "हे, यदि आप यह चाल चलते हैं, तो आपके जीतने की 99% संभावना है," जिससे उसे अंतिम निर्णय लेने में मदद मिलती है।

सारांश

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

उन्होंने क्या दावा नहीं किया:

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

तकनीकी सारांश: सामान्य स्टोकेस्टिक टू-प्लेयर गेम्स को हल करने के लिए एक ASP-आधारित दृष्टिकोण

समस्या विवरण

जनरल गेम प्लेइंग (GGP) सिस्टम बिना किसी पूर्व ज्ञान के रनटाइम विवरणों के आधार पर रणनीतिक खेल खेलने का लक्ष्य रखते हैं। गेम डिस्क्रिप्शन लैंग्वेज (GDL) और इसका विस्तार GDL-II ऐसे खेलों को निर्दिष्ट करने के लिए मानक औपचारिकताएं हैं, जहाँ GDL-II रैंडमनेस (स्टोकेस्टिसिटी) और आंशिक अवलोकन (partial observability) का समर्थन करता है। जबकि ASP को नियत (deterministic) सिंगल- और टू-प्लेयर GDL गेम्स को हल करने के लिए सफलतापूर्वक लागू किया गया है, मौजूदा ASP फ्रेमवर्क में एडवरसेरियल (minimax) और स्टोकेस्टिक व्यवहारों को एक साथ व्यक्त करने की क्षमता का अभाव है। फलस्वरूप, अनिश्चितता वाले दो-प्लेयर टर्न-टेकिंग GDL गेम्स को हल करने के लिए ASP-आधारित विधियों का उपयोग करने में एक अंतराल है।

कार्यप्रणाली

लेखक एक नया भाषा और एक ट्रांसलेशन-आधारित सॉल्वर पेश करके दो-प्लेयर स्टोकेस्टिक GDL गेम्स को हल करने के लिए एक अभिनव दृष्टिकोण प्रस्तावित करते हैं।

1. स्टोकेस्टिक क्वांटिफाइड आंसर सेट प्रोग्रामिंग (SQASP)

ASP और स्टोकेस्टिक गेम सॉल्विंग के बीच के अंतर को पाटने के लिए, यह पेपर SQASP पेश करता है, जो चांस क्वांटिफायर (chance quantifiers) के साथ QASP (क्वांटिफाइड ASP) का विस्तार करता है।

सिंटैक्स (Syntax): एक SQASP प्रोग्राम $Q_1.x_1 \dots Q_n.x_n \ P$ के रूप में लेता है, जहाँ $P$ एक सामान्य लॉजिक प्रोग्राम है और क्वांटिफायर $Q_i$ अस्तित्वगत ( $\exists$ ), सार्वभौमिक ( $\forall$ ), या चांस ( $\mathcal{R}_{p}$ ) हो सकते हैं।
सिमेंटिक्स (Semantics): एक SQASP प्रोग्राम को संतुष्ट करने की अधिकतम प्रायिकता को पुनरावर्ती (recursively) रूप से परिभाषित किया जाता है। चांस क्वांटिफायर $\mathcal{R}_{p}$ एक वेरिएबल के सत्य होने की प्रायिकता $p$ असाइन करता है, जो सब-फॉर्मुलों के आधार पर अपेक्षित मान (expected value) की गणना करता है।
ट्रांसलेशन (Translation): लेखक एक टूल, sqasp2xssat लागू करते हैं जो SQASP प्रोग्राम को एक्सटेंडेड स्टोकेस्टिक सैटिस्फिएबिलिटी (XSSAT) फॉर्मुलों में अनुवादित करता है। XSSAT, चांस क्वांटिफायर के साथ क्वांटिफाइड बुलियन फॉर्मुलों (QBF) का विस्तार करता है। ट्रांसलेशन मौजूदा टूल्स (जैसे lp2sat) का लाभ उठाता है ताकि लॉजिक प्रोग्राम $P$ को एक CNF फॉर्मूला $\psi$ में परिवर्तित किया जा सके जिसके मॉडल $P$ के स्टेबल मॉडल्स के अनुरूप होते हैं।

2. GDL गेम्स को SQASP में एनकोडिंग करना

मुख्य योगदान एक SQASP प्रोग्राम $\Psi$ का निर्माण है जिससे इसकी अधिकतम संतुष्टि प्रायिकता $n$ स्टेप्स के भीतर खिलाड़ी $x$ की अधिकतम जीत की प्रायिकता ( $P_x^w(S_0, n)$ ) के बराबर होती है। एनकोडिंग दो मुख्य चरणों में आगे बढ़ती है:

सहकारी बेसलाइन (Cooperative Baseline): सबसे पहले, एक लॉजिक प्रोग्राम $P_c$ बनाया जाता है यह मानते हुए कि सभी खिलाड़ी (विरोधी $o$ और रैंडम प्लेयर $r$ सहित) एक टर्मिनल स्टेट तक पहुँचने के लिए सहयोग करते हैं जहाँ $x$ जीतता है। यह वैध गेम प्रोग्रेशन, $n$ स्टेप्स के भीतर समाप्ति, और लक्ष्य अवस्था की प्राप्ति सुनिश्चित करता है।
एडवरसेरियल और स्टोकेस्टिक मॉडलिंग: प्रोग्राम को फिर विरोधी और वातावरण के विशिष्ट व्यवहारों को कैप्चर करने के लिए विस्तारित किया जाता है:
- एडवरसेरियल प्लेयर ( $o$ ): निर्णय वेरिएबल्स (dec_o) पर सार्वभौमिक क्वांटिफिकेशन ( $\forall$ ) का उपयोग करके मॉडल किया गया है। यह सॉल्वर को उस वर्स्ट-केस परिदृश्य पर विचार करने के लिए मजबूर करता है जहाँ विरोधी $x$ की जीत की प्रायिकता को कम करता है। एनकोडिंग नियमों की संख्या को कम करने के लिए एक्शन्स के लॉगरिदमिक प्रतिनिधित्व का उपयोग करती है।
- स्टोकेस्टिक प्लेयर ( $r$ ): चांस क्वांटिफायर ( $\mathcal{R}_{1/i}$ ) का उपयोग करके मॉडल किया गया है। एनकोडिंग यह सुनिश्चित करती है कि यदि गेम समाप्त नहीं हुआ है, तो रैंडम प्लेयर उपलब्ध कानूनी चालों में से ठीक एक कानूनी एक्शन को समान रूप से (uniformly) चुनता है। यह कानूनी एक्शन्स को गिनकर और निर्णय वेरिएबल्स (dec_r) पर प्रायिकता बाधाओं को लागू करके प्राप्त किया जाता है।

3. क्वांटिफिकेशन रणनीतियाँ (Quantification Strategies)

पेपर परिणामी XSSAT फॉर्मूला के लिए दो क्वांटिफिकेशन रणनीतियों की जांच करता है:

बेसलाइन मेथड ( $Q_b$ ): सभी नॉन-चॉइस एटम्स (जैसे legal, terminal) को चॉइस एटम्स के सख्त टेम्पोरल ऑर्डर का पालन करते हुए सबसे आंतरिक अस्तित्वगत ब्लॉक में रखा जाता है।
डिपेंडेंसी-आधारित मेथड ( $Q_d$ ): नियत गेम्स के लिए तकनीकों से प्रेरित, यह विधि नॉन-चॉइस एटम्स को यथासंभव जल्दी क्वांटिफायर प्रीफिक्स में लाने के लिए शिफ्ट करती है, जो उनके द्वारा निर्भर चॉइस एटम्स के तुरंत बाद आते हैं। इसका उद्देश्य does पर ब्रांच करने से पहले legal जैसे मानों को फिक्स करके सर्च स्पेस को कम करना है।

मुख्य योगदान

प्रथम ASP-आधारित सॉल्वर फॉर स्टोकेस्टिक GDL: यह पेपर दो-प्लेयर, स्टोकेस्टिक, टर्न-टेकिंग GDL गेम्स को हल करने के लिए पहला दृष्टिकोण प्रस्तुत करता है।
SQASP भाषा: स्टोकेस्टिक क्वांटिफाइड आंसर सेट प्रोग्रामिंग का परिचय, जो एक लॉजिक प्रोग्रामिंग फ्रेमवर्क के भीतर एडवरसेरियल और स्टोकेस्टिक रीजनिंग को एकीकृत करता है।
ट्रांसलेशन-आधारित सॉल्वर: sqasp2xssat का विकास, जो SQASP को XSSAT फॉर्मुलों में परिवर्तित करता है, जिससे गेम सॉल्विंग के लिए मौजूदा XSSAT सॉलवर्स (विशेष रूप से SharpSSAT) का उपयोग करना संभव होता है।
सैद्धांतिक शुद्धता: लेखक प्रमेय 2 और 3 के माध्यम से औपचारिक प्रमाण प्रदान करते हैं, जो GDL गेम में अधिकतम जीत की प्रायिकता और उत्पन्न SQASP/XSSAT फॉर्मूला की अधिकतम संतुष्टि प्रायिकता के बीच समानता स्थापित करते हैं।

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

लेखकों ने Tic-Tac-Toe, Connect-4 और Nim के स्टोकेस्टिक वेरिएशन्स पर अपने दृष्टिकोण का मूल्यांकन किया, जिसमें SQASP-आधारित पद्धति (दोनों $Q_b$ और $Q_d$ क्वांटिफिकेशन का उपयोग करते हुए) की तुलना फॉरवर्ड सर्च एक्सपेक्टेड मिनिमैक्स (EMM) सॉल्वर से की गई।

प्रदर्शन: ASP-आधारित दृष्टिकोण छोटे स्टोकेस्टिक गेम्स के लिए फॉरवर्ड सर्च के साथ प्रतिस्पर्धी है। कई मामलों में (जैसे Tic-Tac-Toe, Connect-3), ASP सॉल्वर EMM के समान समय सीमा के भीतर अक्सर समान जीत की प्रायिकता की गणना करता है।
क्वांटिफायर शिफ्टिंग: आश्चर्यजनक रूप से, SharpSSAT सॉल्वर का उपयोग करते समय डिपेंडेंसी-आधारित क्वांटिफिकेशन ( $Q_d$ ) ने $Q_b$ की तुलना में महत्वपूर्ण प्रदर्शन सुधार नहीं दिया। लेखक इस प्रभाव को SharpSSAT के आंतरिक यूनिट प्रोपेगेशन मैकेनिज्म को जिम्मेदार मानते हैं, जो क्वांटिफायर ऑर्डर की परवाह किए बिना एटम्स (जैसे legal) के मान निकाल सकता है, जिससे स्पष्ट शिफ्टिंग की आवश्यकता कम हो जाती है।
स्केलेबिलिटी सीमाएँ (Scalability Limits): दृष्टिकोण बड़े स्टेट स्पेस के साथ संघर्ष करता है, जैसे बड़े पाइल साइज़ के साथ स्टोकेस्टिक Nim। परिणामी XSSAT फॉर्मूले वर्तमान सॉलवर्स के लिए बहुत बड़े (एक मिलियन क्लॉज से अधिक) हो जाते हैं, जबकि EMM डायनेमिक प्रोग्रामिंग और ट्रांसपोज़िशन टेबल्स के कारण अच्छा स्केल करता है।

महत्व और दावे

पेपर दावा करता है कि प्रस्तावित ASP-आधारित दृष्टिकोण जनरल गेम प्लेइंग सिस्टम में एंडगेम इवैल्यूएशन के लिए एक व्यवहार्य विकल्प प्रदान करता है। नियत गेम्स के लिए सफल अनुप्रयोग को स्टोकेस्टिक डोमेन में विस्तारित करके, यह कार्य प्रदर्शित करता है कि लॉजिक प्रोग्रामिंग अनिश्चितता और एडवरसेरियल रीजनिंग को प्रभावी ढंग से संभाल सकती है।

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