Super Mario je neřešitelný problém: Vědci z MIT dokázali, že hra skrývá komplexitu na úrovni finančních transakcí

Představte si, že jste ambiciózní instalatér z Brooklynu, který se vydává zachránit svou lásku z rukou obřích hub Goombas. Cesta je tak náročná, že žádný počítač – skutečný ani hypotetický – není dostatečně výkonný, aby zjistil, zda se vám to podaří.

Představte si, že jste ambiciózní instalatér z Brooklynu, který se vydává zachránit svou lásku z rukou obřích hub Goombas. Cesta je tak náročná, že žádný počítač – skutečný ani hypotetický – není dostatečně výkonný, aby zjistil, zda se vám to podaří. Podle výzkumu publikovaného skupinou MIT Hardness Group je určení, zda je vaše pátrání vůbec možné, přinejmenším stejně složité jako dešifrování šifrování za finančními transakcemi. A ano, řeč je o hře Super Mario.

MIT Hardness Group není oficiální výzkumná skupina, ale spíše zástupný název pro projekty z oblasti teoretické informatiky, včetně několika souvisejících se Super Mariem, které vznikly v rámci kurzu „Algoritmy a jejich složitost: Zábava s důkazy obtížnosti“ profesora Erika Demainea. Demaine, profesor informatiky a držitel prestižního ocenění MacArthur Fellowship za práci v oblasti výpočetní geometrie, se zabývá také teorií složitosti. Ta se zaměřuje na kategorizaci problémů podle toho, kolik času a paměti počítače potřebují k jejich vyřešení. Demaine je navíc vášnivým fanouškem Super Maria, což mu umožňuje propojit svou vášeň s výzkumem.

Během posledních 14 let Demaine a jeho spolupracovníci prokázali mnoho věcí o Super Mariovi, například že je ještě složitější než proslulý problém obchodního cestujícího nebo problém rozkladu velkých čísel na prvočinitele. Nejvíce však Demainea překvapily nové poznatky čtyř jeho studentů – Hayashi Ani, Holden Hall, Ricardo Ruiz a Naveen Venkat. Ti pro svůj závěrečný projekt v roce 2023 vytvořili pomocí fanouškovských editorů úrovní a platformy Super Mario Maker tak obtížné úrovně, že jsou nerozhodnutelné. To znamená, že je nemožné napsat počítačový program, který by vždy správně předpověděl, zda Mario může v těchto úrovních dosáhnout hradu. Předchozí výzkum řadil Super Maria do třídy složitosti PSPACE, ale nové objevy ho posunuly do RE-Complete, třídy nerozhodnutelných problémů, což je podle Demainea „nejtvrdší třída složitosti, jakou si pro tyto typy her dokážeme představit“.

Základem tohoto objevu je koncept nerozhodnutelných problémů, který v roce 1936 představil Alan Turing, otec moderní informatiky, se svým „problémem zastavení“. Ten dokazuje, že nelze sestrojit počítač, který by dokázal vyřešit vše. Podobně jako u Turingova problému zastavení, který ukázal, že je nemožné zjistit, zda se počítačový program zastaví, znamená nerozhodnutelná úroveň Super Maria, že je nemožné určit, zda lze libovolnou úroveň Maria porazit.

Důkazy nerozhodnutelnosti Super Maria se opírají o techniku zvanou redukce, při níž matematici převádějí problém, který se snaží vyřešit, na problém, o kterém už něco vědí. Tým rozložil úrovně Super Maria na lokalizované části Mariovy cesty, nazývané „moduly“ (gadgets). Jayson Lynch, výzkumný pracovník CSAIL a vedoucí algoritmů v MIT FutureTech, vysvětluje, že modul je cokoli v prostředí, co rozhoduje o tom, zda se Mario může dostat přes určitý vzor v úrovni. Příkladem je „dveřní modul“, který simuluje logické tvrzení pravda/nepravda pomocí pohybu ježatky Spinie.