A Super Mario játékok valódi klasszikusok, így a sorozat legelső darabjai is nem csak a mai napig élvezhetőek, de számtalan probléma kapcsán fel is használják őket. A Super Mario World volt például a bizonyíték arra, hogy egy virtuális valóságot belülről is meg lehet hekkelni – ahogy arról ebben a cikkünkben írtunk:

Ha valóban szimulációban élünk, így menekülhetünk belőle Tegyük fel, hogy tényleg szimulált valóságban élünk! Miként menekülhetünk belőle? Az első, a témának szentelt tanulmány összegyűjti az eddig módszereket, és ajánl egyet, ami tényleg működhet.

Most pedig arra jöttek rá a kutatók, hogy a Super Mario Bros sorozat rejt egy olyan lehetetlen problémát, amit még a világ legerősebb szuperszámítógépével sem lehet matematikailag megoldani. A probléma lényege, hogy a játék esetében lehetetlen előre kiszámítani, hogy bizonyos pályák teljesíthetőek-e, ennek meghatározására csak egyetlen mód akad: az, hogy ténylegesen is megpróbáljuk végigjátszani őket. Mint azt a New Scientist írja, ezt a következtetést a számítási komplexitás elméletének alkalmazásával vonták le, amely azt vizsgálja, hogy milyen nehéz és időigényes egyes problémák algoritmikus megoldása.

Erik Demaine és kollégái a Massachusettsi Műszaki Egyetemről (MIT) korábban kimutatták, hogy annak megállapítása, hogy lehetséges-e bizonyos Mario szintek teljesítése, az úgynevezett NP-nehéz problémák közé tartozik, ahol a komplexitás exponenciálisan növekszik. A csapat most pedig továbbfejlesztette ezt az eredményt, és bebizonyították, hogy bizonyos szinteken ezt a problémát nemcsak rendkívül nehéz, hanem egyenesen lehetetlen algoritmikusan megoldani. A probléma a sorozat számos címe esetén elekőkerül – így a New Super Mario Bros-t és a Super Mario Maker-t is érinti. Ez utóbbi játék azért különösen érdekes ebből a szempontból, mert ez lényegében egy pályaszerkesztő, ahol a játékosok állíthatnak elő szinteket. Ezek között pedig tényleg akadnak őrjítően nehezek is, de időnként felbukkan egy-egy elszánt, és végtelenül ügyes játékos, aki bebizonyítja, hogy akár ezek is teljesíthetőek.

A most a játékban kimutatott problémát az úgynevezett RE-complete kategóriába sorolják, ami azt jelenti, hogy egyetlen számítógép sem tudja megoldani őket, függetlenül annak teljesítményétől, amennyiben a rendelkezésre álló számítási idő véges. Demaine elmagyarázta, hogy annak megoldása, hogy egy Mario-szint teljesíthető-e, hasonló a leállítási probléma megoldásához, amely szerint nincs általános módszer annak előzetes meghatározására, hogy egy számítógépes program leáll-e vagy végtelen ideig fut, csak ha a programot ténylegesen elindítjuk.

A kutatás az egyedi készítésű pályákra összpontosított (feltehetően a Mario Maker játékból – a szerk.), amelyek lehetővé tették a csapat számára, hogy több száz vagy akár ezer ellenséget helyezzenek el egyetlen ponton. Ehhez el kellett távolítaniuk a játékkészítők által meghatározott korlátokat azzal kapcsolatban, hogy hány ellenség lehet jelen egy pályán. Miután eltávolították ezeket a korlátokat, az ellenségek elhelyezését felhasználva létre tudtak hozni egy absztrakt matematikai eszközt, amit számláló gépnek (counter machine) neveztek el, ami lényegében egy működő számítógép a játékban.

A számlálógép képes volt bonyolult számításokat végezni, és ezáltal a kutatók ki tudták mutatni, hogy ezen pályák megoldhatóságának a kikalkulálása olyan nehéz feladat, amit még a legnagyobb teljesítményű számítógép sem tud megoldani véges időn belül. Mint Demaine elmondta:

“Az alapgondolat az, hogy csak akkor tudod megoldani ezt a Mario pályát, ha ez a konkrét számítás befejeződik. És tudjuk, hogy nincs mód annak meghatározására, hogy ez bekövetkezik-e, így arra sincs mód, hogy meghatározzuk, megoldható-e a pálya.”

(Kép: Nintendo)