तकनीकी सारांश: 4×3 बोर्ड पर 2048 का सुदृढ़ समाधान (Strongly Solving)

समस्या की परिभाषा

यह शोध पत्र एक स्टोकेस्टिक (stochastic), एकल-खिलाड़ी गेम वेरिएंट: 2048 on a 4×3 board (जिसे 2048$^{4\times3}$ के रूप में चिन्हित किया गया है) के "सुदृढ़ समाधान" (strong solution) को संबोधित करता है। मानक 4×4 संस्करण के विपरीत, यह वेरिएंट 12 सेल वाले ग्रिड का उपयोग करता है। इस गेम को एक मार्कोव निर्णय प्रक्रिया (MDP) के रूप में मॉडल किया गया है जहाँ एक एजेंट (agent) समान मान वाले आसन्न टाइल्स (adjacent tiles) को जोड़ने के लिए क्रियाएं (ऊपर, नीचे, बाएँ, दाएँ) चुनता है। एक वैध क्रिया के बाद, बोर्ड की स्थिति नियत रूप से एक "आफ्टरस्टेट" (afterstate) में परिवर्तित हो जाती है (टाइल्स को खिसकाना और जोड़ना)। इसके बाद, वातावरण स्टोकेस्टिक रूप से एक नया टाइल (90% संभावना के साथ 2 और 10% संभावना के साथ 4) एक यादृच्छिक खाली सेल में उत्पन्न करता है, जिससे अगली स्थिति (next state) प्राप्त होती है।

उद्देश्य इष्टतम नीति $\pi^*$ और इष्टतम वैल्यू फंक्शन $v^*(s)$ की गणना करना है, जो किसी भी सुलभ अवस्था $s$ से अपेक्षित संचयी पुरस्कार (expected cumulative reward) को दर्शाता है। प्राथमिक चुनौती स्टेट स्पेस (state space) का आकार है: 4×3 वेरिएंट में लगभग $1.15 \times 10^9$ सुलभ अवस्थाएँ और $7.4 \times 10^8$ आफ्टरस्टेट्स हैं। यह पैमाना पिछले रूप से हल किए गए 3×3 संस्करण (Mini2048) की तुलना में लगभग $10^4$ गुना बड़ा है, जिससे मानक हार्डवेयर पर सीधा एन्यूमरेशन (enumeration) और स्टोरेज असंभव हो जाता है।

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

लेखक "आयु" (age) द्वारा स्टेट स्पेस विभाजन और सघन डेटा प्रतिनिधित्व (compact data representation) पर आधारित एक समाधान प्रस्तावित करते हैं।

1. आयु-आधारित विभाजन (Age-Based Partitioning)

मुख्य नवाचार बोर्ड पर सभी टाइल संख्याओं के योग के रूप में अवस्था की आयु (age) को परिभाषित करना है ($age(s) = \sum c_i$)।

• अपरिवर्तनीयता (Invariance): एक वैध क्रिया के बाद अवस्था और उसके तत्काल आफ्टरस्टेट के बीच आयु स्थिर रहती है (क्योंकि टाइल्स को जोड़ने से मानों का योग संरक्षित रहता है, और खिसकाने से मान नहीं बदलते)।
• प्रगति (Progression): स्टोकेस्टिक ट्रांज़िशन (नया टाइल उत्पन्न होने) के दौरान आयु 2 या 4 से बढ़ जाती है।
• एल्गोरिदम संबंधी निहितार्थ: यह गुण स्टेट स्पेस को आयु के आधार पर विसंयुक्त उपसमूहों (disjoint subsets) में विभाजित करने की अनुमति देता है।
  • फॉरवर्ड पास (एन्यूमरेशन): आयु $n$ की वैध अवस्थाओं को केवल आयु $n-2$ और $n-4$ के आफ्टरस्टेट्स से उत्पन्न किया जा सकता है। एल्गोरिदम बढ़ती आयु के माध्यम से पुनरावृति करता है, केवल तीन सेटों को मेमोरी में बनाए रखता है (वर्तमान आयु, आयु+2, आयु+4) ताकि सभी सुलभ अवस्थाओं और आफ्टरस्टेट्स को सूचीबद्ध किया जा सके।
  • बैकवर्ड पास (वैल्यू कंप्यूटेशन): इष्टतम मानों की गणना अधिकतम आयु से प्रारंभिक आयु की ओर पीछे की ओर पुनरावृति करके की जाती है। एक अवस्था का मान उसके सुलभ आफ्टरस्टेट्स का अधिकतम मान होता है; एक आफ्टरस्टेट का मान उसके सुलभ नेक्स्ट स्टेट्स का अपेक्षित मान होता है (स्पॉन प्रोबेबिलिटीज द्वारा भारित/weighted)।

2. सघन प्रतिनिधित्व (Compact Representation)

स्टोरेज आवश्यकताओं (अनुमानित ~4.4 TiB कच्चे 48-बिट ID) को संभालने के लिए, लेखक अनूठे स्टेट ID के सेटों को संग्रहीत करने के लिए एलियास-फानो कोड्स (Elias-Fano codes) का उपयोग करते हैं।

• संरचना: क्रमबद्ध अनूठे ID को उच्च-क्रम बिट्स ($h_i$) और निम्न-क्रम बिट्स ($l_i$) में विभाजित किया जाता है। निम्न बिट्स को एक निरंतर बिट-वेक्टर में संग्रहीत किया जाता है, जबकि उच्च बिट्स को रैंक ऑपरेशन्स का उपयोग करके एक स्पार्स बिट-वेक्टर $H$ में एनकोड किया जाता है।
• अनुकूलन (Optimizations):
  • सममिति न्यूनीकरण (Symmetry Reduction): ID को क्षैतिज, ऊर्ध्वाधर और 180-डिग्री घूर्णन सममितिओं के बीच न्यूनतम मान के लिए सामान्यीकृत किया जाता है।
  • बेस अनुकूलन (Base Adaptation): एक विशिष्ट आयु के लिए अधिकतम टाइल मान के आधार पर एनकोडिंग बेस को समायोजित किया जाता है।
  • सेल ड्रॉपिंग (Cell Dropping): एनकोडिंग के दौरान एक सेल की जानकारी छोड़ दी जाती है क्योंकि योग (आयु) कुल राशि को सीमित करता है, जिससे बाद में पूर्ण पुनर्निर्माण संभव होता है।
• दक्षता: यह सभी आफ्टरस्टेट ID के स्टोरेज को ~4.4 TiB से घटाकर लगभग 1.4 TiB कर देता है, जबकि कुशल लुकअप क्षमताएं बनाए रखता है। विशेष रूप से इष्टतम खेल के लिए, एक विशेष प्रतिनिधित्व (BuRR एल्गोरिदम का उपयोग करके) आवश्यकता को 300 GiB से कम तक कम कर देता है।

मुख्य परिणाम

• स्टेट स्पेस सांख्यिकी: कुल सुलभ अवस्थाओं की संख्या 1,152,817,492,752 है, और आफ्टरस्टेट्स की संख्या 739,648,886,170 है।
• इष्टतम अपेक्षित स्कोर: सबसे सामान्य प्रारंभिक अवस्थाओं (मान 2 के दो टाइल्स) के लिए, इष्टतम रणनीति के तहत अपेक्षित स्कोर लगभग 50,724.26 है।
  • 4 टाइल (आयु 6) वाली प्रारंभिक अवस्थाएँ थोड़ा कम अपेक्षित स्कोर (~50,720.62) देती हैं।
  • दो 4 टाइल्स (आयु 8) वाली प्रारंभिक अवस्थाएँ सबसे कम (~50,708.99) देती हैं, जो उच्च-मूल्य वाली टाइल्स के साथ शुरू करने के छोटे नुकसान को दर्शाती हैं।
• स्टेट वितरण: प्रति आयु अवस्थाओं की संख्या आम तौर पर प्रबंधनीय है (प्रति आयु $3 \times 10^6$ से कम), जिससे एल्गोरिदम को कई आयु स्तरों को मेमोरी में रखने की अनुमति मिलती है।
• टर्मिनल अवस्थाएँ (Terminal States): स्टेट काउंट डिस्ट्रीब्यूशन में "घाटियाँ" (valleys) उन आयु पर आती हैं जो 2048 के गुणज हैं, जो सीमित बोर्ड स्पेस के साथ बड़ी टाइल्स बनाने की कठिनाई को दर्शाती हैं। कुछ आयु (जैसे, 8190, 12286) में शून्य वैध आफ्टरस्टेट्स होते हैं क्योंकि उन योगों को बनाने के लिए उपलब्ध 12 सेल्स से अधिक टाइल्स की आवश्यकता होगी।
• एक्शन संवेदनशीलता (Action Sensitivity): इष्टतम और उप-इष्टतम क्रियाओं के बीच मान का अंतर आयु 2048 और 4096 के पास चरम पर होता है, जो यह सुझाव देता है कि बड़ी टाइल्स बनाने के तुरंत बाद शुरुआती निर्णय महत्वपूर्ण होते हैं।

महत्व और दावे

यह शोध पत्र दावा करता है कि उसने 2048$^{4\times3}$ वेरिएंट को सुदृढ़ रूप से हल (strongly solved) कर दिया है, जो स्टेट स्पेस के आकार के कारण पहले एक कठिन कार्य माना जाता था। इस कार्य का महत्व निम्नलिखित है:

1. स्केलेबिलिटी (Scalability): यह प्रदर्शित करना कि $10^9$ से अधिक अवस्थाओं वाला गेम ब्रूट-फोर्स विधियों के बजाय गेम-विशिष्ट संरचनात्मक गुणों (आयु) का लाभ उठाकर कुछ दिनों के भीतर एक व्यक्तिगत कंप्यूटर पर हल किया जा सकता है।
2. पद्धतिगत योगदान (Methodological Contribution): "आयु" विभाजन तकनीक का परिचय स्टेट स्पेस के एन्यूमरेशन और वैल्यू कंप्यूटेशन की अनुमति देता है जहाँ स्टेट वैल्यूज अपेक्षाओं (expectations) पर निर्भर करती है, जिससे $\alpha\beta$ प्रूनिंग (जो स्टोकेस्टिक वातावरण में अप्रभावी है) की आवश्यकता को प्रभावी ढंग से दरकिनार किया जा सके।
3. डेटा उपलब्धता: लेखक इष्टतम वैल्यू फंक्शन और स्टेट स्पेस का एक सघन प्रतिनिधित्व प्रदान करते हैं, जो भविष्य के सुदृढ़ शिक्षण (reinforcement learning) अनुसंधान और गेम विश्लेषण के लिए एक आधार रेखा (baseline) के रूप में कार्य करता है।
4. स्टोरेज दक्षता: विशाल स्टेट सेट को ~1.4 TiB तक कंप्रेस करने के लिए एलियास-फानो कोड्स का सफल अनुप्रयोग इस डेटासेट को मध्यम कम्प्यूटेशनल संसाधनों (जैसे, 4 TiB SSDs) वाले शोधकर्ताओं के लिए सुलभ बनाता है।

लेखक नोट करते हैं कि हालांकि प्राथमिक लक्ष्य गेम को हल करना था, लेकिन परिणामी डेटासेट और "आयु" की अवधारणा स्टोकेस्टिक गेम्स और सुदृढ़ शिक्षण मूल्यांकन में आगे के अध्ययन के लिए एक आधार के रूप में कार्य कर सकती है।