NEW SCIENTIST ⟩ Selle videomänguga jääks hätta isegi maailma võimsaim superarvuti

Foto: Nintendo

Arvutamine, kas videomänguseeria «Super Mario Bros» teatud tasemed on läbitavad enne nende mängimist, on matemaatiliselt võimatu, isegi kui teil oleks mitu aastat aega ja käepärast maailma võimsaim superarvuti.

«Me ei tea, kuidas tõestada, et mäng on lõbus, me ei tea, mida see matemaatiliselt tähendab, kuid saame tõestada, et see on keeruline ja see võib-olla annab ülevaate sellest, miks see lõbus on,» ütleb Massachusettsi tehnoloogiainstituudi teadlane Erik Demaine. «Mulle meeldib mõelda keerulisusest kui lõbu esindajast.»

Demaine ja tema kolleegid kasutavad oma töös tööriistu arvutusliku keerukuse valdkonnast, et uurida, kui keeruline ja aeganõudev on erinevate probleemide algoritmiline lahendamine.

Nad on varem tõestanud, et välja selgitada, kas «Mario» mängudes on võimalik teatud tasemeid läbida, on ülesanne, mis kuulub probleemide rühma, mida tuntakse NP-hard nime all ja mille keerukus kasvab astmeliselt. Seda kategooriat on äärmiselt raske arvutada kõigi, välja arvatud kõige väiksemate probleemide puhul.

Nüüd on teadlased astunud sammu kaugemale, näidates, et «Super Mario» mängude teatud tasemete puhul pole sellele küsimusele vastamine mitte ainult raske, vaid ka võimatu.

See kehtib sarja mitme osa kohta, sealhulgas «New Super Mario Bros» ja «Super Mario Maker». «Sellest keerulisemaks ei saa minna,» ütleb Demaine. «Kas jõuate finišisse? Pole olemas algoritmi, mis suudaks piiratud aja jooksul sellele küsimusele vastata.»

See võib tunduda vastuoluline, kuid selle lahendamatu kategooria probleeme, mida nimetatakse RE-complete'iks, ei saa arvutiga lahendada, olenemata sellest, kui võimas masin on, või kui kaua te sellel töötada lasete.

Demaine möönab, et «Mario» mängude tasemete sellesse kategooriasse sobitamiseks oli vaja pisut trikke. Esiteks vaadeldakse uuringus kohandatud tasemeid, mis võimaldasid meeskonnal paigutada sadu või tuhandeid vaenlasi ühte kohta.

Selleks tuli kaotada mängude väljaandjate seatud piirangud vaenlaste arvule, kes tasemel võivad olla. Seejärel sai meeskond kasutada vaenlaste paigutust tasemel, et luua abstraktne matemaatiline tööriist, mida nimetatakse loendusmasinaks, luues sisuliselt mängus toimiva arvuti.

See trikk võimaldas meeskonnal käivitada veel ühe arvutusliku mõistatuse, mida nimetatakse peatamisprobleemiks ja mis ütleb, et üldiselt pole võimalik teada saada, kas see programm kunagi lõpeb või lihtsalt töötab igavesti peale selle käivitamist.

Need matemaatiliste kontseptsioonide kihid võimaldasid meeskonnal lõpuks tõestada, et ükski mängutaseme analüüs ei saa kindlalt öelda, kas seda saab kunagi lõpule viia.

«Idee seisneb selles, et saate selle «Mario» taseme lahendada ainult siis, kui see konkreetne arvutus lõpeb, ja me teame, et seda pole võimalik kuidagi kindlaks teha ja seega pole ka võimalust kindlaks teha, kas saate seda taset lahendada,» ütleb Demaine.