🤖 AI

Automated Approach for Solving Infinite-state Polynomial Reachability Games

यह शोध पत्र एक सुदृढ़ (sound), अर्ध-पूर्ण (semi-complete) और उप-घातांकीय (sub-exponential) स्वचालित एल्गोरिदम प्रस्तुत करता है जो अनंत-अवस्था वाले बहुपद पहुँचतात्मकता खेलों (infinite-state polynomial reachability games) को हल करने के लिए रैंकिंग प्रमाणपत्रों का उपयोग करता है, और सिंडरेला-स्टेपमदर (Cinderella-Stepmother) जैसे चुनौतीपूर्ण परिदृश्यों में REACH खिलाड़ी के लिए जीतने वाली रणनीतियों की सफलतापूर्वक गणना करता है जहाँ पिछले तरीके विफल रहे थे।

मूल लेखक: Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Mehrdad Karrabi, Maximilian Seeliger, {\DJ}or{\dj}e Žikelić

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

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

CC BY 4.0

मूल लेखक: Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Mehrdad Karrabi, Maximilian Seeliger, {\DJ}or{\dj}e Žikelić

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

कल्पना कीजिए कि एक विशाल, अनंत शतरंज के बोर्ड पर एक खेल खेला जा रहा है जहाँ मोहरे केवल काले और सफेद वर्ग नहीं हैं, बल्कि तापमान, गति या जल स्तर जैसे जटिल गणितीय मान (values) हैं। यह शोध पत्र इन "अनंत-अवस्था" (infinite-state) वाले खेलों को हल करने का एक नया तरीका पेश करता है, जो विशेष रूप से दो खिलाड़ियों के बीच के संघर्ष पर केंद्रित है: REACH (आक्रमणकर्ता) और SAFE (रक्षक)।

यहाँ लेखक द्वारा किए गए कार्यों का रोजमर्रा के उदाहरणों का उपयोग करके एक सरल विवरण दिया गया है।

खेल: एक कभी न खत्म होने वाला खींचतान (Tug-of-War)

इन खेलों में, बोर्ड वास्तविक संख्याओं (जैसे थर्मामीटर की रीडिंग या बैंक खाते का बैलेंस) द्वारा परिभाषित होता है।

REACH का लक्ष्य: खेल को एक विशिष्ट "लक्ष्य क्षेत्र" (Target Zone) में धकेलना (जैसे बाल्टी का भर कर छलक जाना, या किसी रोबोट का गंतव्य तक पहुँचना)।
SAFE का लक्ष्य: खेल को उस "लक्ष्य क्षेत्र" से हमेशा दूर रखना।

आमतौर पर, यदि बोर्ड अनंत है, तो यह पता लगाना कि कौन जीतेगा, कंप्यूटर के लिए हल करना असंभव होता है। यह समुद्र तट पर रेत के हर एक कण को गिनने की कोशिश करने जैसा है ताकि यह देखा जा सके कि क्या आपके पास एक किला बनाने के लिए पर्याप्त रेत है; यह कार्य बहुत बड़ा है।

बड़ा विचार: "प्रोग्रेस मीटर" (रैंकिंग सर्टिफिकेट)

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

यह इस प्रकार काम करता है:

बैटरी का नियम: मीटर को हमेशा एक सकारात्मक संख्या (या शून्य) दिखानी चाहिए।
ड्रेन (Drain) का नियम: हर बार जब कोई चाल चली जाती है, तो बैटरी का स्तर कम से कम थोड़ा सा जरूर कम होना चाहिए।
विजेता: यदि बैटरी शून्य (या नकारात्मक) हो जाती है, तो खेल समाप्त हो जाता है, और REACH जीत जाता है क्योंकि वे लक्ष्य तक पहुँच गए।

चुनौती:

यदि SAFE की बारी है, तो मीटर को कम होना ही होगा, चाहे SAFE कोई भी चाल चुने। SAFE ऐसा कोई तरीका नहीं खोज सकता जिससे बैटरी ऊँची बनी रहे।
यदि REACH की बारी है, तो REACH को बस एक ऐसी चाल ढूँढनी है जो बैटरी को कम कर दे।

यदि आप एक ऐसा नक्शा बना सकते हैं जहाँ हर एक चाल बैटरी को कम करती है, तो आपने यह सिद्ध कर दिया है कि REACH अंततः जीत जाएगा, चाहे SAFE उन्हें रोकने के लिए कितनी भी कड़ी कोशिश क्यों न करे। यही वह "रैंकिंग सर्टिफिकेट" है।

समस्या: "अनंत विकल्प" का जाल

लेखकों ने इस विचार में एक खामी खोजी है। कल्पना कीजिए कि SAFE के पास एक सुपरपावर है: वह एक ही समय में अनंत विकल्पों में से चुन सकता है।

उदाहरण: कल्पना कीजिए कि SAFE बैटरी को 0.1 से कम कर सकता है, या 0.01 से, या 0.0000001 से। यदि SAFE लगातार छोटी और छोटी गिरावट चुनता रहता है, तो बैटरी वास्तव में शून्य तक कभी नहीं पहुँच पाएगी, भले ही वह कम हो रही हो। इस विशिष्ट "अनंत विकल्प" वाले परिदृश्य में, बैटरी मीटर वाला तरीका जीत सिद्ध करने में विफल रहता है।

हालाँकि, लेखकों ने सिद्ध किया कि यदि SAFE प्रत्येक चरण पर सीमित (finite) विकल्पों तक ही सीमित है (जैसे कि एक सामान्य बोर्ड गेम में), तो बैटरी मीटर वाला तरीका पूरी तरह से काम करता है और एक पूर्ण प्रमाण देता है।

समाधान: एक स्वचालित रोबोट सॉल्वर

शोध पत्र एक पूरी तरह से स्वचालित कंप्यूटर प्रोग्राम प्रस्तुत करता है जो निम्नलिखित कार्य करता है:

आकार का अनुमान लगाना: यह मान लेता है कि "बैटरी मीटर" एक बहुपद समीकरण (polynomial equation) है (एक फैंसी गणितीय सूत्र जिसमें $x, y, x^2$ जैसे चर शामिल हैं)।
खाली स्थानों को भरना: यह एक कंप्यूटर सॉल्वर का उपयोग करता है ताकि उस सटीक संख्या को खोजा जा सके जो सूत्र को एक वैध बैटरी मीटर के रूप में काम करने के योग्य बनाती है।
रणनीति आउटपुट करना: यदि इसे संख्याएँ मिल जाती हैं, तो यह आपको REACH के लिए जीतने वाली सटीक चालें और गणितीय प्रमाण (सर्टिफिकेट) देता है कि वे काम करती हैं।

यह विशेष क्यों है?
पिछले तरीके ऐसे थे जैसे कि हर एक टुकड़े को एक-एक करके जाँचकर पहेली को हल करने की कोशिश करना, जिसमें बहुत समय लगता था या जो जटिल पहेलियों पर विफल हो जाते थे। यह नया तरीका तेज़ (sub-exponential time) है और पिछले उपकरणों की तुलना में बहुत अधिक जटिल गणित (polynomials) को संभाल सकता है, जो साधारण रैखिक (linear) गणित तक ही सीमित थे।

वास्तविक दुनिया का परीक्षण: सिंडरेला-सौतेली माँ का खेल

अपने तरीके को सिद्ध करने के लिए, उन्होंने एक प्रसिद्ध पहेली जिसे सिंडरेला-सौतेली माँ के खेल के रूप में जाना जाता है, पर इसका परीक्षण किया।

सेटअप: एक सौतेली माँ (REACH) 5 बाल्टियों में पानी भरती है। एक सिंडरेला (SAFE) दो बाल्टियाँ खाली करती है। सौतेली माँ तब जीतती है जब कोई भी बाल्टी भर कर छलक जाती है।
चुनौती: वर्षों से, कंप्यूटर केवल तभी इसे हल कर सकते थे जब बाल्टियाँ बहुत छोटी हों। यदि बाल्टियाँ लगभग भरी हुई थीं (लेकिन पूरी तरह नहीं), तो कंप्यूटर अटक जाते थे।
परिणाम: लेखकों के नए टूल ने इस खेल को किसी भी बाल्टी के आकार के लिए हल कर दिया, यहाँ तक कि उन आकारों के लिए भी जो भरने के बेहद करीब थे। इसने सौतेली माँ के लिए एक ऐसी जीतने वाली रणनीति ढूँढ निकाली जिसे कोई अन्य कंप्यूटर टूल हल नहीं कर सका।

सारांश

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

तकनीकी सारांश: अनंत-अवस्था बहुपद पहुँच योग्यता खेलों (Infinite-state Polynomial Reachability Games) को हल करने के लिए स्वचालित दृष्टिकोण

समस्या विवरण

यह शोधपत्र अनंत-अवस्था पहुँच योग्यता खेलों (infinite-state reachability games) को हल करने की समस्या पर आधारित है। ये दो-खिलाड़ी, टर्न-आधारित खेल हैं जो ग्राफ पर खेले जाते हैं जहाँ नोड्स को एक REACH खिलाड़ी (जिसका उद्देश्य खेल को एक विशिष्ट लक्ष्य सेट की अवस्थाओं में धकेलना है) और एक SAFE खिलाड़ी (जिसका उद्देश्य लक्ष्य सेट से बचना है) के बीच विभाजित किया जाता है।

यद्यपि परिमित ग्राफ (finite graphs) पर पहुँच योग्यता खेल अच्छी तरह से समझे गए हैं और रैखिक समय (linear time) में हल किए जा सकते हैं, अनंत-अवस्था वाला संस्करण आम तौर पर अनिर्णायक (undecidable) होता है (राइस के प्रमेय के अनुसार), यहाँ तक कि उन प्रतिबंधित मामलों में भी जहाँ एक खिलाड़ी के पास केवल एक ही क्रिया होती है। मौजूदा विधियाँ अक्सर समस्या को तार्किक संतुष्टि (जैसे, कॉन्स्ट्रेंड हॉर्न क्लॉज़) या फिक्स्ड-पॉइंट गणनाओं में बदलने पर निर्भर करती हैं, लेकिन इन दृष्टिकोणों को बहुपद बाधाओं (polynomial constraints) को संभालने, पूर्णता गारंटी प्रदान करने, या कुशल रनटाइम प्राप्त करने में सीमाओं का सामना करना पड़ता है। यहाँ संबोधित विशिष्ट चुनौती वास्तविक-मान वाले चरों (real-valued variables) पर बहुपद बाधाओं (polynomial constraints) द्वारा परिभाषित खेलों में REACH खिलाड़ी के लिए एक जीतने वाली रणनीति के अस्तित्व को निर्धारित करना और उसकी गणना करना है।

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

1. रैंकिंग प्रमाणपत्र (Ranking Certificates)

मुख्य सैद्धांतिक योगदान पहुँच योग्यता खेलों के लिए रैंकिंग प्रमाणपत्रों की शुरूआत है। प्रोग्राम समाप्ति (program termination) को सिद्ध करने के लिए उपयोग किए जाने वाले रैंकिंग फलनों से प्रेरणा लेते हुए, एक रैंकिंग प्रमाणपत्र एक फलन $f: S \to \mathbb{R}$ है जो गेम स्टेट्स को वास्तविक मानों (real values) पर मैप करता है। REACH के लिए एक जीतने वाली रणनीति के गवाह (witness) के रूप में कार्य करने के लिए, $f$ को तीन शर्तों को पूरा करना चाहिए:

शुरुआत में गैर-ऋणात्मकता (Non-negativity at Start): $f(s_{init}) \ge 0$ ।
सुरक्षा प्रगति (SAFE का टर्न): यदि वर्तमान अवस्था $s$ thuộc SAFE की है और $f(s) \ge 0$ है, तो सभी संभावित उत्तराधिकारी अवस्थाओं $s'$ के लिए, $f(s) - 1 \ge f(s') \ge 0$ होना चाहिए। यह सुनिश्चित करता है कि SAFE मान को कम होने से नहीं रोक सकता।
पहुँच योग्यता प्रगति (REACH का टर्न): यदि वर्तमान अवस्था $s$ thuộc REACH की है और $f(s) \ge 0$ है, तो एक उत्तराधिकारी अवस्था $s'$ अस्तित्व में होनी चाहिए ताकि $f(s) - 1 \ge f(s') \ge 0$ हो सके। यह सुनिश्चित करता है कि REACH मान को स्पष्ट रूप से कम करने के लिए एक चाल चुन सकता है।

फलन का मान लक्ष्य सेट की ओर प्रगति के माप के रूप में कार्य करता है। शोधपत्र सिद्ध करता है कि ऐसे प्रमाणपत्र का अस्तित्व REACH के लिए एक मेमोरीलेस जीतने वाली रणनीति के अस्तित्व को दर्शाता है (Soundness)। हालाँकि यह प्रमाण नियम सामान्य अनंत-अवस्था खेलों के लिए पूर्ण (complete) नहीं है (क्योंकि SAFE अनंत मानों में से चुनने के लिए SAFE को एक अनबाउंडेड लोअर बाउंड की ओर ले जा सकता है), लेकिन यह तब सुदृढ़ (sound) और पूर्ण (complete) सिद्ध होता है जब SAFE के पास प्रत्येक चरण में सीमित विकल्प हों।

2. स्वचालित संश्लेषण एल्गोरिदम (Automated Synthesis Algorithm)

लेखक बहुपद पहुँच योग्यता खेलों (polynomial reachability games) के लिए एक पूर्णतः स्वचालित एल्गोरिदम प्रस्तावित करते हैं, जहाँ गार्ड्स, अपडेट और उद्देश्य वास्तविक चरों पर बहुपद असमानताओं (polynomial inequalities) द्वारा परिभाषित होते हैं। एल्गोरिदम चार चरणों में कार्य करता है:

टेम्पलेट सेटअप: एल्गोरिदम रैंकिंग प्रमाणपत्र $f$ और मेमोरीलेस रणनीति $\sigma$ के लिए अधिकतम डिग्री $D$ के प्रतीकात्मक बहुपद टेम्पलेट्स (symbolic polynomial templates) को निर्धारित करता है।
बाधा संग्रह (Constraint Collection): यह टेम्पलेट चरों पर बाधाओं का एक सिस्टम बनाता है। ये बाधाएं रैंकिंग प्रमाणफल की परिभाषा की शर्तों (C1–C3) को कूटबद्ध करती हैं, जिसमें कार्यों के स्थान पर प्रतीकात्मक टेम्पलेट्स का उपयोग किया जाता है।
क्वांटिफायर एलिमिनेशन (Quantifier Elimination): बाधाओं में सार्वभौमिक क्वांटिफायर (जैसे, "सभी $x$ के लिए") होते हैं। एल्गोरिदम इन बाधाओं को शुद्ध रूप से अस्तित्व संबंधी बहुपद बाधाओं (existentially quantified polynomial constraints) के एक सिस्टम में परिवर्तित करने के लिए पुतिनाट के प्रमेय (Putiner's theorem) (सामान्य बहुपदों के लिए) या फार्क्स के लेम्मा (Farkas' lemma) (रैखिक बहुपदों के लिए) पर आधारित एक अनुवाद लागू करता है।
समाधान (Solving): एक ऑफ-द-शेल्फ SMT सॉल्वर (जैसे, Z3, MathSAT5) परिणामी सिस्टम को हल करता है। समाधान से बहुपद टेम्पलेट्स के ठोस गुणांक (coefficients) प्राप्त होते हैं, जो एक वैध रैंकिंग प्रमाणपत्र और संगत जीतने वाली रणनीति का निर्माण करते हैं।

यह एल्गोरिदम सुदृढ़ (sound) है (कोई भी गणना की गई रणनीति सही है) और अर्ध-पूर्ण (semi-complete) है (यदि बहुपद प्रमाणपत्रों की श्रेणी के भीतर कोई समाधान मौजूद है और स्टेट स्पेस कॉम्पैक्ट है, तो यह समाधान खोजने की गारंटी देता है)। एक निश्चित बहुपद डिग्री के लिए इसका रनटाइम इनपुट आकार के संबंध में सब-एक्सपोनेंशियल (sub-exponential) है।

मुख्य योगदान

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

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

लेखकों ने अपने तरीके का मूल्यांकन दो प्राथमिक बेंचमार्क पर किया:

सिंडरेला-स्टेपमदर गेम (The Cinderella-Stepmother Game):
- शास्त्रीय संस्करण: स्टेपमदर (REACH) बाल्टियों में पानी वितरित करती है, और सिंडरेला (SAFE) दो आसन्न बाल्टियों को खाली करती है। लक्ष्य एक बाल्टी को ओवरफ्लो करना है।
- परिणाम: प्रस्तावित विधि ने $2 - 10^{-10}$ तक की बाल्टी क्षमता के लिए खेल को हल किया और, महत्वपूर्ण रूप से, $2 - \epsilon$ (जहाँ $\epsilon > 0$ ) के प्रतीकात्मक मामले के लिए 1 सेकंड से कम समय में हल किया।
- तुलना: अत्याधुनिक उपकरण (GenSys और rpgsolve) $2 - 10^{-10}$ वाले मामले में विफल रहे (टाइमआउट या समर्थित नहीं) और $2 - \epsilon$ वाले प्रतीकात्मक मामले को भी नहीं संभाल सके। यह इस खेल के लिए मनमाने परिशुद्धता मापदंडों (arbitrary precision parameters) का पहला स्वचालित समाधान है।
- गैर-रैखिक संस्करण: एक संस्करण जहाँ स्टेपमदर का वितरण मैनहट्टन नॉर्म ( $\ell_1$ ) के बजाय यूक्लिडियन नॉर्म ( $\ell_2$ ) द्वारा बाधित है, जो गैर-रैखिकता पेश करता है। प्रस्तावित विधि ने 1 सेकंड से कम समय में निश्चित क्षमता वाले मामलों को हल किया, जबकि बेसलाइन पूरी तरह विफल रही।
फॉल्टी रोबोट बेंचमार्क (Faulty Robot Benchmark):
- एक खेल जो एक रोबोट द्वारा रसायनों को मिलाने का मॉडल है जहाँ एक विरोधी दोष (faults) उत्पन्न करता है। रोबोट का लक्ष्य एक विशिष्ट घनत्व और आयतन तक पहुँचना है।
- परिणाम: प्रस्तावित विधि ने 44 सेकंड में खेल को हल किया। बेसलाइन GenSys 5 मिनट के टाइमआउट के भीतर समाप्त होने में विफल रहा।

महत्व और दावे

शोधपत्र का दावा है कि इसका दृष्टिकोण उपलब्ध विशेषताओं के एक अनूठे संयोजन की पेशकश करके अनंत-अवस्था पहुँच योग्यता खेलों को हल करने के क्षेत्र में अत्याधुनिक स्थिति (state of the art) को महत्वपूर्ण रूप से आगे बढ़ाता है:

बहुपद खेलों के लिए प्रयोज्यता: रैखिक अंकगणित तक सीमित पिछले सुदृढ़/अर्ध-पूर्ण तरीकों के विपरीत।
अर्ध-पूर्णता गारंटी: फिक्स्ड-पॉइंट विधियों के विपरीत जो समाप्त नहीं हो सकती हैं या जिनमें पूर्णता गारंटी की कमी होती है।
दक्षता: डबल-एक्सपोनेंशियल विकल्पों की तुलना में सब-एक्सपोनेंशियल रनटाइम।

लेखक इस बात पर जोर देते हैं कि उनकी विधि शास्त्रीय सिंडरेला-स्टेपमदर गेम के लिए मनमाने परिशुद्धता मापदंड ( $2 - \epsilon$ ) के साथ इष्टतम जीतने वाली रणनीति की गणना करने वाला पहला तरीका है, जो एक ऐसी समस्या थी जो स्वचालित सॉल्वरों के लिए खुली रह गई थी। वे अपनी सीमाओं को स्वीकार करते हैं, यह नोट करते हुए कि वर्तमान में उनका तरीका केवल बहुपद खेलों तक ही सीमित है और पहुँच योग्यता उद्देश्यों पर केंद्रित है, जिससे गैर-बहुपद खेलों और अन्य उद्देश्यों (जैसे, $\omega$ -रेगुलर या मात्रात्मक) के लिए भविष्य के कार्य के रूप में विस्तार की संभावना बनी रहती है।