सुपर मारिओ बहुतेक अल्गोरिदमपेक्षा गणितीयदृष्ट्या अधिक जटिल का आहे

एका राजकुमारीला वाचवणाऱ्या प्लंबरबद्दलचा साधा प्लॅटफॉर्मर गेम वाटत असला तरी, सुपर मारिओ प्रत्यक्षात सैद्धांतिक संगणक विज्ञानातील (theoretical computer science) खोलवरच्या रहस्यांचे प्रवेशद्वार आहे. MIT च्या नवीन संशोधनानुसार, या गेममधील काही विशिष्ट रचना गणितीयदृष्ट्या 'अनिर्णयक्षम' (undecidable) आहेत, ज्यामुळे त्या मानक संगणकीय समस्यांच्या पलीकडे असलेल्या जटिलतेच्या वर्गात (complexity class) येतात.

PSPACE पासून RE-Complete पर्यंत: जटिलतेतील एक मोठी झेप

अनेक वर्षे, MIT चे प्राध्यापक एरिक डेमेनसह संशोधकांमध्ये असा एकमत होते की सुपर मारिओ PSPACE जटिलता वर्गामध्ये (complexity class) मोडतो. या वर्गामध्ये अशा समस्यांचा समावेश होतो ज्या सोडवता येतात, परंतु इनपुटचा आकार वाढल्यास त्यासाठी प्रचंड मेमरी आणि वेळेची आवश्यकता असते. PSPACE समस्या कठीण असल्या तरी, पुरेशी संसाधने उपलब्ध असल्यास संगणकाद्वारे त्या मूलभूतपणे "सोडवता" येतात.

तथापि, हयाशी एनी, होल्डन हॉल, रिकार्डो रुइझ आणि नवीन वेंकट या विद्यार्थ्यांच्या टीमने केलेल्या अलीकडील संशोधनाने हा समज मोडीत काढला आहे. लेव्हल एडिटर्स आणि Super Mario Maker चा वापर करून, संशोधकांनी अशा विशिष्ट लेव्हल्स तयार केल्या आहेत ज्या RE-Complete आहेत. याचा अर्थ असा की हा गेम आता अनिर्णयक्षम समस्यांच्या (undecidable problems) क्षेत्रात प्रवेश केला आहे. या विशिष्ट परिस्थितीत, मारिओ यशस्वीरित्या ध्वजस्तंभ (flagpole) किंवा किल्ल्यापर्यंत पोहोचू शकेल की नाही, याचा अचूक अंदाज लावू शकणारा संगणक प्रोग्राम लिहिणे गणितीयदृष्ट्या अशक्य आहे.

Halting Problem शी असलेले नाते

एखादा व्हिडिओ गेम अनिर्णयक्षम का असू शकतो हे समजून घेण्यासाठी, आपल्याला अ‍ॅलन ट्युरिंग आणि Halting Problem कडे वळावे लागेल. ट्युरिंगने सिद्ध केले की असा कोणताही वैश्विक (universal) अल्गोरिदम नाही जो एखादा प्रोग्राम शेवटी थांबेल की कायमस्वरूपी चालू राहील हे ठरवू शकेल.

MIT च्या संशोधन पथकाने reduction नावाच्या तंत्राद्वारे हा तर्क 'मशरूम किंगडम'ला लागू केला. सुपर मारिओची लेव्हल "गॅजेट्स" (gadgets) म्हणून ओळखल्या जाणाऱ्या स्थानिक घटकांमध्ये विभागून, संशोधक गेमच्या मेकॅनिक्समध्ये जटिल संगणकीय तर्क (computational logic) सिम्युलेट करण्यास सक्षम झाले. हे गॅजेट्स 'लॉजिक गेट्स'प्रमाणे काम करतात; जेव्हा ते पाईप्स, प्लॅटफॉर्म्स आणि गुंबा (Goombas) किंवा स्पायनीज (Spinies) सारख्या शत्रूंच्या विशिष्ट पॅटर्नमध्ये मांडले जातात, तेव्हा ते ट्युरिंग मशीनच्या वर्तनाची प्रतिकृती तयार करू शकतात. परिणामी, मारिओ लेव्हलच्या शेवटी पोहोचेल की नाही हे ठरवणे, हे एखादा जटिल प्रोग्राम कधी थांबेल हे ठरवण्याइतकेच कार्यात्मकदृष्ट्या समान होते.

AI आणि संगणकीय क्षेत्राच्या भविष्यासाठी हे का महत्त्वाचे आहे

हा शोध केवळ गेमर्ससाठी एक मनोरंजक तथ्य नाही; तर तो संगणकीय प्रक्रियेच्या (computation) मूलभूत मर्यादांची एक गंभीर आठवण करून देतो. जसे आपण कृत्रिम बुद्धिमत्ता (Artificial Intelligence) आणि स्वयंचलित तर्कशास्त्राच्या (automated reasoning) सीमा विस्तारत आहोत, तसे आपल्याला हे मान्य करावे लागेल की काही तार्किक संरचना (logical structures) कोणत्याही अल्गोरिदमच्या पलीकडे आहेत, मग कितीही प्रोसेसिंग पॉवर किंवा मेमरी उपलब्ध असली तरीही.

एक साधे वाटणारे वातावरण देखील अनिर्णयक्षम समस्यांचे घर असू शकते हे सिद्ध करून, MIT Hardness Group ने जटिलता सिद्धांत (complexity theory) परस्परसंवादी, नियम-आधारित प्रणालींना (interactive, rule-based systems) कसा लागू केला जाऊ शकतो हे दाखवून दिले आहे. वाढत्या अल्गोरिदमिक जगात आपण जटिल सॉफ्टवेअर कसे डिझाइन करतो, स्वयंचलित प्रणालींची पडताळणी कशी करतो आणि काय "गणना" (calculated) केले जाऊ शकते याच्या सीमा कशा समजून घेतो, यावर याचे परिणाम होतील.

मुख्य निष्कर्ष

• अनिर्णयक्षमता (Undecidability): सुपर मारिओच्या काही लेव्हल्स आता RE-Complete म्हणून वर्गीकृत केल्या आहेत, याचा अर्थ असा की कोणताही अल्गोरिदम खेळाडू ती लेव्हल पूर्ण करू शकेल की नाही याचा अचूक अंदाज लावू शकणार नाही.
• जटिलतेतील बदल (Complexity Shift): हा गेम "सोडवता येण्यासारखा पण कठीण" असलेल्या PSPACE वर्गातून अनिर्णयक्षमतेच्या क्षेत्रात गेला आहे, जे Halting Problem चे प्रतिबिंब आहे.
• संगणकीय गॅजेट्स (Computational Gadgets): संशोधकांनी गेम मेकॅनिक्सचा (पाईप्स, शत्रू आणि प्लॅटफॉर्म्स) "गॅजेट्स" म्हणून वापर करून जटिल लॉजिक गेट्स तयार केले, जे वैश्विक संगणन (universal computation) सिम्युलेट करतात.