શા માટે સુપર મારિયો મોટાભાગના અલ્ગોરિધમ્સ કરતા ગાણિતિક રીતે વધુ જટિલ છે

જોકે તે રાજકુમારીને બચાવતા પ્લમ્બર વિશેનો એક સાદો પ્લેટફોર્મર ગેમ જેવો દેખાઈ શકે છે, પરંતુ સુપર મારિયો ખરેખર થીયરેટિકલ કોમ્પ્યુટર સાયન્સના ઊંડા રહસ્યોમાં પ્રવેશવાનો એક માર્ગ છે. MIT ના નવા સંશોધનથી ખબર પડી છે કે ગેમના અમુક કન્ફિગરેશન્સ ગાણિતિક રીતે undecidable (નિર્ણય લેવા અશક્ય) છે, જે તેમને પ્રમાણભૂત કમ્પ્યુટેશનલ સમસ્યાઓથી ઘણું આગળના જટિલતા વર્ગ (complexity class) માં મૂકે છે.

PSPACE થી RE-Complete સુધી: જટિલતામાં એક મોટો ઉછાળો

વર્ષો સુધી, MIT ના પ્રોફેસર એરિક ડેમેન સહિતના સંશોધકો વચ્ચે એ સહમતિ હતી કે સુપર મારિયો PSPACE જટિલતા વર્ગમાં આવે છે. આ વર્ગમાં એવી સમસ્યાઓ હોય છે જે ઉકેલી શકાય તેવી છે, પરંતુ ઇનપુટનું કદ વધતા તે માટે અપ્રાયોગિક પ્રમાણમાં મેમરી અને સમયની જરૂર પડે છે. જોકે PSPACE સમસ્યાઓ મુશ્કેલ છે, તેમ છતાં પૂરતા સંસાધનો આપવા પર તે મૂળભૂત રીતે કમ્પ્યુટર દ્વારા "ઉકેલી શકાય તેવી" છે.

જોકે, વિદ્યાર્થીઓની એક ટીમ—હાયાશી અની, હોલ્ડન હોલ, રિકાર્ડો રુઈઝ અને નવીન વેંકટ—ના તાજેતરના કાર્યએ આ ધારણાને તોડી નાખી છે. લેવલ એડિટર્સ અને Super Mario Maker નો ઉપયોગ કરીને, સંશોધકોએ એવા ચોક્કસ લેવલ બનાવ્યા છે જે RE-Complete છે. આનો અર્થ એ છે કે ગેમ હવે undecidable સમસ્યાઓના ક્ષેત્રમાં પ્રવેશી છે. આ ચોક્કસ પરિસ્થિતિઓમાં, એવો કમ્પ્યુટર પ્રોગ્રામ લખવો ગાણિતિક રીતે અશક્ય છે જે હંમેશા સચોટ રીતે આગાહી કરી શકે કે મારિયો સફળતાપૂર્વક ધ્વજસ્તંભ અથવા કિલ્લા સુધી પહોંચી શકશે કે નહીં.

Halting Problem સાથેનો સંબંધ

વીડિયો ગેમ શા માટે undecidable હોઈ શકે છે તે સમજવા માટે, આપણે એલન ટ્યુરિંગ અને Halting Problem તરફ પાછા જોવું જોઈએ. ટ્યુરિંગે સાબિત કર્યું હતું કે એવો કોઈ સાર્વત્રિક અલ્ગોરિધમ નથી જે નક્કી કરી શકે કે કોઈપણ આપેલ પ્રોગ્રામ અંતે અટકી જશે કે કાયમ માટે ચાલશે.

MIT ની સંશોધન ટીમે reduction તરીકે ઓળખાતી તકનીક દ્વારા મશરૂમ કિંગડમ (Mushroom Kingdom) પર આ તર્ક લાગુ કર્યો. સુપર મારિયો લેવલને "gadgets" તરીકે ઓળખાતા સ્થાનિક ઘટકોમાં વિભાજિત કરીને, સંશોધકો ગેમની મિકેનિક્સની અંદર જટિલ કમ્પ્યુટેશનલ લોજિકનું અનુકરણ (simulate) કરવા સક્ષમ બન્યા. આ ગેજેટ્સ લોજિક ગેટ્સ તરીકે કામ કરે છે; જ્યારે પાઈપો, પ્લેટફોર્મ્સ અને Goombas અથવા Spinies જેવા દુશ્મનોના ચોક્કસ પેટર્નમાં ગોઠવવામાં આવે છે, ત્યારે તેઓ ટ્યુરિંગ મશીનનું વર્તન કરી શકે છે. પરિણામે, મારિયો લેવલના અંત સુધી પહોંચશે કે નહીં તે નક્કી કરવું એ એક જટિલ પ્રોગ્રામ ક્યારેય અટકશે કે નહીં તે નક્કી કરવા સમાન બની જાય છે.

AI અને કમ્પ્યુટિંગના ભવિષ્ય માટે આ શા માટે મહત્વનું છે

આ શોધ માત્ર ગેમર્સ માટે મનોરંજક તથ્ય નથી; તે કમ્પ્યુટેશનની મૂળભૂત મર્યાદાઓની ગહન યાદ અપાવે છે. જેમ જેમ આપણે આર્ટિફિશિયલ ઇન્ટેલિજન્સ અને ઓટોમેટેડ રીઝનિંગની સીમાઓ વધારી રહ્યા છીએ, તેમ આપણે એ સ્વીકારવું જોઈએ કે અમુક તાર્કિક માળખાઓ કુદરતી રીતે જ કોઈપણ અલ્ગોરિધમની પહોંચ બહાર છે, પછી ભલે ગમે તેટલી પ્રોસેસિંગ પાવર અથવા મેમરી ઉપલબ્ધ હોય.

એક દેખીતી રીતે સરળ વાતાવરણમાં undecidable સમસ્યાઓ હોઈ શકે છે તે સાબિત કરીને, MIT Hardness Group દર્શાવે છે કે જટિલતા સિદ્ધાંત (complexity theory) ને ઇન્ટરેક્ટિવ, નિયમ-આધારિત સિસ્ટમ્સ પર કેવી રીતે લાગુ કરી શકાય છે. આનાથી આપણે જટિલ સોફ્ટવેર કેવી રીતે ડિઝાઇન કરીએ છીએ, ઓટોમેટેડ સિસ્ટમ્સને કેવી રીતે ચકાસીએ છીએ અને વધતા જતાં અલ્ગોરિધમિક વિશ્વમાં શું "ગણતરી" કરી શકાય છે તેની સીમાઓને કેવી રીતે સમજીએ છીએ તેના પર અસર પડે છે.

મુખ્ય મુદ્દાઓ

• Undecidability: અમુક સુપર મારિયો લેવલને હવે RE-Complete તરીકે વર્ગીકૃત કરવામાં આવ્યા છે, જેનો અર્થ છે કે કોઈ પણ અલ્ગોરિધમ ક્યારેય સંપૂર્ણ રીતે આગાહી કરી શકશે નહીં કે ખેલાડી તેને પૂર્ણ કરી શકશે કે નહીં.
• Complexity Shift: ગેમ "ઉકેલી શકાય તેવી પરંતુ મુશ્કેલ" PSPACE વર્ગમાંથી undecidable ના ક્ષેત્રમાં ખસી ગઈ છે, જે Halting Problem નું પ્રતિબિંબ પાડે છે.
• Computational Gadgets: સંશોધકોએ યુનિવર્સલ કમ્પ્યુટેશનનું અનુકરણ કરતા જટિલ લોજિક ગેટ્સ બનાવવા માટે ગેમ મિકેનિક્સ (પાઈપો, દુશ્મનો અને પ્લેટફોર્મ્સ) ને "gadgets" તરીકે ઉપયોગમાં લીધા હતા.