Super Mario ist mathematisch unmöglich zu lösen – DW – 17.06.2024

Super Mario ist mathematisch unmöglich zu lösen – DW – 17.06.2024
Super Mario ist mathematisch unmöglich zu lösen – DW – 17.06.2024
-

Forscher am Massachusetts Institute of Technology (MIT) haben mit einem unkonventionellen Ansatz neue Grenzen bei der Untersuchung der Rechenkomplexität eröffnet und dabei das beliebte Videospiel Super Mario Bros. als Testgelände genutzt. Das von Professor Erik Demaine geleitete Team hat festgestellt, dass bestimmte Level des Spiels unentscheidbar sind, das heißt, es gibt keinen Algorithmus, der vorhersagen kann, ob sie überwunden werden können, ohne sie tatsächlich zu spielen, selbst mit dem leistungsstärksten Supercomputer der Welt.

Dieses Ergebnis stammt aus einer detaillierten Studie mehrerer Titel der Franchise, darunter New Super Mario Bros und Super Mario Maker, die kürzlich auf dem Preprint-Server veröffentlicht wurden arXiv.

„Von den 2D-Mario-Spielen, die seit New Super Mario Bros. veröffentlicht wurden, haben wir gezeigt, dass alle außer Super Mario Wonder unentscheidbar sind“, stellen die Wissenschaftler in ihrer Studie fest.

Die Untersuchung ergab, dass bestimmte Super Mario Bros-Levels, wie etwa die in New Super Mario Bros und Super Mario Maker, nicht nur schwierig, sondern auch unentscheidbar sind. Bild: NINTENDO/AP/picture Alliance

Super Mario Bros.: Unlösbare Probleme

Mithilfe von Tools zur Berechnung der Komplexität stellten die Forscher fest, dass einige Level des Spiels zu einer Kategorie mathematischer Probleme gehören, die als NP-schwer bekannt sind und deren Lösung exponentiell komplexer wird. Doch Demaine und sein Team gingen noch einen Schritt weiter und zeigten, dass die Frage, ob sie auf bestimmten Ebenen überwunden werden können, nicht nur schwierig, sondern sogar unmöglich ist.

„Es kann nicht schwieriger sein“, kommentierte Demaine Neuer Wissenschaftler. „Können Sie das Ziel erreichen? Es gibt keinen Algorithmus, der diese Frage in endlicher Zeit beantworten kann“, fügte er hinzu.

Einfach ausgedrückt: Diese unentscheidbaren Probleme, bekannt als RE-vollständig, können von keinem Computer gelöst werden, unabhängig von seiner Leistung oder der ihm zur Verfügung stehenden Zeit.

„Es ist faszinierend, sich vorzustellen, dass Schwierigkeit ein Ersatz für Spaß sein könnte“, erzählt Demaine Neuer Wissenschaftler, der darauf hinweist, dass wir immer noch nicht vollständig verstehen, was aus mathematischer Sicht den Spaß an einem Spiel ausmacht. Allerdings könnte die diesen Ebenen innewohnende Unentzifferbarkeit Hinweise auf die Attraktivität der Herausforderungen geben, die sie mit sich bringen, überlegt Demaine.

Diese Forschung unterstreicht nicht nur die Komplexität einiger Videospiele, sondern auch ihre Fähigkeit, fortgeschrittene mathematische Probleme zu veranschaulichen. Bild: Nintendo/dpa/picture Alliance

Simulation einer Zählmaschine

Um zu diesen Schlussfolgerungen zu gelangen, erstellten die Forscher benutzerdefinierte Level, füllten einen einzigen Punkt mit Hunderten von Feinden und beseitigten die Grenzen der Spieleditoren. Dieser Ansatz ermöglichte es ihnen, innerhalb des Spiels eine Zählmaschine zu bauen, ein theoretisches Modell, das den Betrieb eines Computers simuliert.

Mit dieser Methode konnten sie das Problem mit dem berühmten Stall-Problem in Verbindung bringen, das besagt, dass es nicht möglich ist, zu bestimmen, ob ein Computerprogramm beendet wird oder auf unbestimmte Zeit läuft, außer indem man es ausführt. Damit zeigten sie, dass keine Analyse mit Sicherheit vorhersagen kann, ob ein Level abgeschlossen werden kann.

Diese Untersuchungen bereichern nicht nur die mathematische und computergestützte Theorie, sondern legen auch einen neuen Weg nahe, Videospiele und deren Design zu verstehen. Wenn Sie also das nächste Mal mit einem Mario-Level konfrontiert werden, denken Sie daran, dass Sie es mit einem der komplexesten Computerrätsel zu tun haben.

Felipe Espinosa Wang mit Informationen von New Scientist und arXiv.

-