ஏன் சூப்பர் மரியோ பெரும்பாலான அல்காரிதம்களை விட கணித ரீதியாக அதிக சிக்கலானது

ஒரு இளவரசியை மீட்கும் ஒரு பிளம்பரைப் பற்றிய எளிமையான பிளாட்ஃபார்மர் விளையாட்டாகத் தோன்றினாலும், சூப்பர் மரியோ உண்மையில் கோட்பாட்டு கணினி அறிவியலின் (theoretical computer science) ஆழமான மர்மங்களுக்குச் செல்லும் ஒரு நுழைவாயிலாகும். MIT-இன் புதிய ஆராய்ச்சி, இந்த விளையாட்டின் சில அமைப்புகள் கணித ரீதியாகத் தீர்மானிக்க முடியாதவை (undecidable) என்பதைக் கண்டறிந்துள்ளது, இது அவற்றை சாதாரண கணக்கீட்டுப் பிரச்சனைகளை விட மிக உயர்ந்த ஒரு சிக்கல் வகுப்பில் (complexity class) வைக்கிறது.

PSPACE முதல் RE-Complete வரை: சிக்கலில் ஒரு மிகப்பெரிய பாய்ச்சல்

பல ஆண்டுகளாக, MIT பேராசிரியர் எரிக் டெமைன் (Erik Demaine) உட்பட ஆராய்ச்சியாளர்களிடையே நிலவிய பொதுவான கருத்து என்னவென்றால், சூப்பர் மரியோ PSPACE சிக்கல் வகுப்பைச் சேர்ந்தது என்பதாகும். இந்த வகுப்பில் தீர்க்கக்கூடிய பிரச்சனைகள் உள்ளன, ஆனால் உள்ளீடு (input) அளவு அதிகரிக்கும் போது, அவை நடைமுறைக்குச் சாத்தியமில்லாத அளவு நினைவகம் மற்றும் நேரத்தைக் கோருகின்றன. PSPACE பிரச்சனைகள் கடினமானவை என்றாலும், போதுமான வளங்கள் இருந்தால் ஒரு கணினியால் அவற்றை அடிப்படையிலேயே "தீர்க்க முடியும்".

இருப்பினும், ஹயாஷி அனி (Hayashi Ani), ஹோல்டன் ஹால் (Holden Hall), ரிகார்டோ ரூயிஸ் (Ricardo Ruiz) மற்றும் நவீன் வெங்கட் (Naveen Venkat) ஆகிய மாணவர்களின் குழுவின் சமீபத்திய ஆய்வு இந்த அனுமானத்தை உடைத்துள்ளது. லெவல் எடிட்டர்கள் மற்றும் Super Mario Maker-ஐப் பயன்படுத்தி, ஆராய்ச்சியாளர்கள் RE-Complete ஆக இருக்கும் குறிப்பிட்ட நிலைகளை (levels) உருவாக்கினர். இதன் பொருள் விளையாட்டு தீர்மானிக்க முடியாத பிரச்சனைகளின் (undecidable problems) 영역த்திற்குள் நுழைந்துவிட்டது என்பதாகும். இந்த குறிப்பிட்ட சூழ்நிலைகளில், மரியோ வெற்றிகரமாக கொடித் தூணையோ அல்லது கோட்டையையோ சென்றடைய முடியுமா என்பதை எப்போதும் சரியாகக் கணிக்கக்கூடிய ஒரு கணினி நிரலை எழுதுவது கணித ரீதியாகச் சாத்தியமற்றது.

Halting Problem-உடனான தொடர்பு

ஒரு வீடியோ கேம் ஏன் தீர்மானிக்க முடியாததாக இருக்கும் என்பதைப் புரிந்துகொள்ள, ஆலன் டூரிங் (Alan Turing) மற்றும் Halting Problem-ஐப் பார்க்க வேண்டும். ஒரு குறிப்பிட்ட நிரல் (program) இறுதியில் நின்றுவிடுமா அல்லது எப்போதும் இயங்கிக்கொண்டே இருக்குமா என்பதைத் தீர்மானிக்கக்கூடிய ஒரு பொதுவான அல்காரிதம் இல்லை என்பதை டூரிங் நிரூபித்தார்.

MIT ஆராய்ச்சி குழு இந்த தர்க்கத்தை (logic) reduction எனப்படும் நுட்பத்தின் மூலம் மஷ்ரூம் கிங்டத்திற்கு (Mushroom Kingdom) பயன்படுத்தியது. சூப்பர் மரியோ நிலையை "gadgets" என்று அழைக்கப்படும் உள்ளூர் கூறுகளாகப் பிரிப்பதன் மூலம், ஆராய்ச்சியாளர்கள் விளையாட்டின் இயக்கவியலுக்குள் (mechanics) சிக்கலான கணக்கீட்டு தர்க்கத்தை உருவகப்படுத்த முடிந்தது. இந்த gadgets தர்க்க வாயில்களாக (logic gates) செயல்படுகின்றன; குழாய்கள், தளங்கள் மற்றும் Goombas அல்லது Spinies போன்ற எதிரிகள் குறிப்பிட்ட வடிவங்களில் அமைக்கப்பட்டிருக்கும் போது, அவை ஒரு டூரிங் இயந்திரத்தின் (Turing machine) நடத்தையைப் பிரதிபலிக்க முடியும். இதன் விளைவாக, மரியோ நிலையின் முடிவை அடைகிறாரா என்பதைக் கண்டறிவது, ஒரு சிக்கலான நிரல் எப்போதாவது நின்றுவிடுமா என்பதைக் கண்டறிவதற்குச் செயல்பாட்டு ரீதியாகச் சமமானதாகிறது.

AI மற்றும் கணினித் துறையின் எதிர்காலத்திற்கு இது ஏன் முக்கியமானது

இந்த கண்டுபிடிப்பு கேமர்களுக்கான ஒரு சுவாரஸ்யமான தகவல் மட்டுமல்ல; இது கணக்கீட்டின் அடிப்படை வரம்புகளை நினைவூட்டும் ஒரு ஆழமான விஷயமாகும். நாம் செயற்கை நுண்ணறிவு (Artificial Intelligence) மற்றும் தானியங்கி பகுத்தறிவின் (automated reasoning) எல்லைகளை விரிவுபடுத்தும் போது, எவ்வளவு செயலாக்கத் திறன் (processing power) அல்லது நினைவகம் இருந்தாலும், சில தர்க்கக் கட்டமைப்புகள் இயல்பாகவே எந்தவொரு அல்காரிதத்தின் எல்லைக்கும் அப்பாற்பட்டவை என்பதை நாம் அங்கீகரிக்க வேண்டும்.

எளிமையானதாகத் தோன்றும் ஒரு சூழலில் கூட தீர்மானிக்க முடியாத பிரச்சனைகள் இருக்கலாம் என்பதை நிரூபிப்பதன் மூலம், சிக்கல் கோட்பாட்டை (complexity theory) ஊடாடும், விதி அடிப்படையிலான அமைப்புகளுக்கு எவ்வாறு பயன்படுத்தலாம் என்பதை MIT Hardness Group காட்டுகிறது. இது நாம் சிக்கலான மென்பொருள்களை எவ்வாறு வடிவமைக்கிறோம், தானியங்கி அமைப்புகளை எவ்வாறு சரிபார்க்கிறோம் மற்றும் பெருகிவரும் அல்காரிதமிக் உலகில் எதை "கணக்கிட" முடியும் என்பதன் எல்லைகளை எவ்வாறு புரிந்துகொள்கிறோம் என்பதில் தாக்கத்தை ஏற்படுத்துகிறது.

முக்கியக் குறிப்புகள்

• தீர்மானிக்க இயலாமை (Undecidability): சில சூப்பர் மரியோ நிலைகள் இப்போது RE-Complete என வகைப்படுத்தப்பட்டுள்ளன, அதாவது ஒரு வீரரால் அவற்றை முடிக்க முடியுமா என்பதை எந்த அல்காரிதமும் ஒருபோதும் துல்லியமாகக் கணிக்க முடியாது.
• சிக்கல் மாற்றம் (Complexity Shift): இந்த விளையாட்டு "தீர்க்கக்கூடிய ஆனால் கடினமான" PSPACE வகுப்பிலிருந்து, Halting Problem-ஐப் பிரதிபலிக்கும் வகையில் தீர்மானிக்க முடியாத 영역த்திற்கு மாறியுள்ளது.
• கணக்கீட்டு Gadgets (Computational Gadgets): ஆராய்ச்சியாளர்கள் உலகளாவிய கணக்கீட்டை உருவகப்படுத்தும் சிக்கலான தர்க்க வாயில்களை உருவாக்க விளையாட்டின் இயக்கவியலை (குழாய்கள், எதிரிகள் மற்றும் தளங்கள்) "gadgets" ஆகப் பயன்படுத்தினர்.