Ученые из MIT доказали, что уровни в Super Mario алгоритмически неразрешимы

Die fabelhafte Welt der Mathematik: Manche Level im Kultspiel Super Mario sind unlösbar In meiner Kindheit musste ich während der Schulferien oft viele Stunden auf der Rückbank eines Autos verbringen. Meine Eltern fuhren mit mir und meinem Bruder meist zu unserer Verwandtschaft nach Frankreich. Das hieß: acht bis zehn Stunden lang auf dem Engen Sitz des Autos die Zeit totschlagen. Umso glücklicher war ich, als ich meinen ersten Gameboy bekam – und dazu das Spiel »Super Marioland«. Als ältestes Gameboy-Spiel der Super-Mario-Reihe bestand die Schwierigkeit vor allem darin, dass man nicht zwischenspeichern konnte und nach dem Ausschalten stets wieder von vorne beginnen musste. Es brauchte viel Zeit und Geduld, um sich bis ins letzte Level vorzuarbeiten, den Endgegner zu besiegen, und Prinzessin Daisy zu retten. Genau diese Zeit hatte ich ja auf den langen Autofahrten, und nicht ohne Stolz kann ich sagen, dass »Super Marioland« eines der wenigen Spiele ist, die ich mehrmals von Anfang bis Ende durchgespielt habe. Doch ich muss zugeben, dass mir das Spiel an manchen Tagen unlösbar vorkam – was definitiv meinem mangelnden Können zuzuschreiben ist. Umso überraschter war ich, als ich kürzlich über eine mathematische Forschungsarbeit aus dem Jahr 2024 mit diesem verheißungsvollen Titel stolperte: »You Can’t Solve These Super Mario Bros. Levels: Undecidable Mario Games«. Darin beweisen vier Forschende vom Massachusetts Institute of Technology (MIT), dass viele neuere Spiele der Super-Mario-Reihe aus mathematischer Sicht maximal komplex sind – und damit unlösbare Probleme enthalten. Mehr zu Mathematik im Kino, Spielen und Popkultur Fasziniert Sie die popkulturelle Seite der Mathematik – oder suchen Sie nach Nerd-Wissen, mit dem Sie auf Partys glänzen können? Dann könnten Ihnen auch diese Beiträge gefallen: - Warum »Good Will Hunting« Mathematiker ärgert - Die mysteriöse Zahl im Programmcode von Quake 3 - Die verborgene Mathematik im Verstand von Sherlock Holmes Alle bereits erschienen Artikel dieser Kolumne finden Sie hier. Ein Teil der theoretischen Informatik – manche Menschen würden den Bereich auch der Mathematik zuordnen – beschäftigt sich mit der Komplexität von Problemen. Es geht hierbei darum, zu beurteilen, wie aufwendig es in der Theorie ist, eine Lösung zu erarbeiten, und die Probleme entsprechend zu kategorisieren. Auf diese Weise lässt sich beurteilen, welche Aufgaben potenziell durch einen Computer – oder überhaupt – lösbar sind. Ein Beispiel für eine »einfache« Aufgabe ist die Frage, ob in einem Netzwerk zwei Punkte miteinander verbunden sind. Je größer ein Netzwerk ist, desto aufwendiger ist es zwar, eine Lösung zu finden – aber die Anzahl der Rechenschritte skaliert höchstens polynomiell mit der Netzwerkgröße (also mit der Netzwerkgröße potenziert mit einer Konstanten) und nicht etwa exponentiell (also eine Konstante potenziert mit der Netzwerkgröße). Für solche Probleme haben Fachleute die Komplexitätsklasse »P« eingeführt. Dann gibt es noch Aufgaben, die deutlich schwieriger zu lösen sind. Der Aufwand steigt hierbei exponentiell mit der Größe, das ist etwa bei der optimalen Routenfindung der Fall. Auch wenn solche Probleme komplex sind, lassen sie sich aber recht schnell auf ihre Korrektheit hin kontrollieren. Derartige Aufgaben fallen daher in eine andere Problemklasse, die als »NP« bezeichnet wird. - P-ProblemeP-Probleme sind vergleichsweise einfach zu lösen: Der Rechenaufwand steigt nur langsam mit der Größe des Problems an. Möchte man zum Beispiel zwei Zahlen miteinander multiplizieren, kann das bei sehr großen Zahlen zwar aufwendig erscheinen – aber ein Computer kann das stets bewältigen, egal wie riesig die Zahlen sind. - NP-ProblemeBei NP-Problemen ist das hingegen anders. Diese können für einfache Spezialfälle vielleicht noch gelöst werden, doch es gibt keine effiziente Methode, um allgemeine Aufgaben dieser Art zu berechnen. Ein typisches NP-Problem besteht darin, zu einer vorgegebenen Zahl die Primteiler zu bestimmen: jene Primzahlen, die miteinander multipliziert die ursprüngliche Zahl ergeben. Für einfache Beispiele wie 15 lassen sich die Primteiler (3 und 5) schnell ermitteln. Doch wenn man die Primteiler einer 1000-stelligen Zahl berechnen möchte, sind Computer schnell überfordert. NP-Probleme zeichnen sich aber auch dadurch aus, dass sich ihre Lösung einfach überprüfen lässt. Falls mir jemand eine 1000-stellige Zahl und ihre vermeintlichen Primteiler vorgibt, kann ich die Primzahlen miteinander multiplizieren (das ist ja aus mathematischer Sicht einfach, weil es ein P-Problem ist) und sofort sehen, ob das Ergebnis mit der 1000-stelligen Zahl übereinstimmt. Es gibt aber auch Probleme, die keine Lösung besitzen, zum Beispiel das Halteproblem: Bereits im Jahr 1937 bewies der Mathematiker Alan Turing, dass es keinen Algorithmus geben kann, der allgemein beurteilt, ob ein Computerprogramm zum Halten kommt oder bis in alle Ewigkeit weiterläuft. Solche Aufgaben sind algorithmisch unlösbar: Eine Rechenvorschrift mit einer endlichen Anzahl von Schritten genügt nicht, um sie zu bewältigen. Und wie die Fachleute des MIT 2024 zeigten, fallen auch einige Super-Mario-Spiele in diese unlösbare Problemklasse. Schwer, schwerer, Super Mario Um zu beweisen, dass eine Aufgabe in eine bestimmte Problemklasse fällt, nutzen Fachleute das Prinzip der »Reduktion«. Man reduziert hierfür ein Problem auf ein anderes. Wenn man zum Beispiel zeigen kann, dass die Lösung einer Frage rund um ein Super-Mario-Spiel das Halteproblem lösen würde, dann ist Super Mario mindestens so komplex wie das Halteproblem selbst. Genau das haben die Forschenden vom MIT gemacht. Sie haben sich hierbei auf die Frage fokussiert, ob ein Level in einem Super-Mario-Spiel lösbar ist – was bedeutet, dass man es prinzipiell durch Ausprobieren aller endlichen Eingabefolgen bewältigen kann – und das mit dem Halteproblem gleichgesetzt. Die Fachleute zogen hierfür eine vereinfachte Variante des Halteproblems heran. Wie sich zeigt, lässt sich dieses bereits für besonders simple Computermodelle formulieren, sogenannte Zählmaschinen. Dabei handelt es sich um ein theoretisches Modell eines Rechners, das nur eine Handvoll Befehle ausführen kann: einen Zählwert um eins erhöhen (»Inkrement«), um eins verringern (»Dekrement«), anhalten (»Halt«) und, falls der Zählwert gleich null ist, zu einer anderen Anweisung springen (»Jumpif-Zero«). Schon eine rudimentäre Maschine mit diesen Fähigkeiten führt zum Halteproblem. Wie die Forschenden zeigten, kann man mit einigen Spielen der Super-Mario-Reihe eine Zählmaschine implementieren. Dadurch lässt sich die Frage, ob die Maschine irgendwann anhält, auf folgende Frage übertragen: Kann die Spielfigur in diesem Level das Ziel erreichen? Monster zählen Hierfür codierten die MIT-Fachleute einen Zählwert durch die Anzahl der gegnerischen Figuren im Spiel. Zuerst haben sie also die betrachteten Spiele in der Theorie so modifiziert, dass sie über kein Zeitlimit verfügen und die Anzahl der Gegner nicht mehr begrenzt wird. »Die meisten dieser Spiele (sogar das ursprüngliche Super Mario Bros. aus dem Jahr 1985) verfügen über Mechanismen, mit denen im Laufe der Zeit beliebig viele Gegner generiert werden können«, schreiben die Fachleute in ihrer Veröffentlichung. »Doch es ist schwierig, die richtige Kombination von Mechanismen zu finden, um die spezifische Funktionalität eines Zählers mit Inkrement-, Dekrement- und Jumpif-Zero-Funktionen zu implementieren.« Trotzdem ist ihnen das gelungen. Das Team zerlegte dafür den möglichen Weg von Mario in einem Level in einzelne Abschnitte, die jeweils einem Rechenbefehl der Zählmaschine entsprechen. So wird zum Beispiel der Zähler erhöht, also ein Gegner gespawnt, wenn Mario einen bestimmten Pfad durchquert. Das entspricht der Inkrement-Funktion. Andere Wege hingegen verringern die Anzahl der Gegner (Dekrement); und wieder andere Bereiche können einen Durchgang öffnen, wenn es keine Gegner mehr gibt (Jumpif-Zero). Falls sich für Mario so irgendwann der Weg zum Ziel öffnet, ist das derart simulierte Computermodell in den Halt-Zustand gekommen. Um herauszufinden, ob es für Mario stets eine Möglichkeit gibt, das Ziel zu erreichen, müsste man also herausfinden, ob die zugehörige Zählmaschine zum Halten kommt. Da das Halteproblem aber im allgemeinen unentscheidbar ist, gilt das auch für die Lösbarkeit eines Super-Mario-Levels. Die Fachleute vom MIT haben diese Beweisidee explizit auf mehrere Super-Mario-Spiele übertragen, nämlich auf die 2006 veröffentlichte Serie New Super Mario Bros. sowie die zehn Jahre später erschienenen Super-Mario-Maker-Spiele in allen Spielvarianten (Super Mario Bros. 1 und 3, Super Mario World, New Super Mario Bros. U und Super Mario 3D World). In der zugrunde liegenden Forschungsarbeit des MIT-Teams können Sie bei Interesse detailliert nachlesen, welche Handlungen in welcher Spielversion eine Zählmaschine codieren und so zum Halteproblem führen. »Wir wissen nicht, wie man beweisen kann, ob ein Spiel Spaß macht«, sagte einer der MIT-Fachleute, Erik Demaine, zu »New Scientist«. »Aber wir können beweisen, dass es schwierig ist, und das gibt vielleicht einen Einblick, warum es Spaß macht.« Da Super Mario maximal komplex ist, könnte es nach diesem Kriterium eines der spaßigsten Spiele überhaupt sein. Für mich war das auf den langen Autofahrten definitiv der Fall – auch wenn die von mir gespielte Version Super Marioland nicht zu der Klasse der komplexesten Spiele gehört. Sie haben ein Lieblingstheorem, ein mathematisches Thema, das Sie fasziniert, oder eine Lieblingszahl? Dann kommentieren Sie doch gerne den Artikel oder schreiben Sie eine Mail an: [email protected] – und vielleicht taucht Ihre Anregung in einer der folgenden Kolumnen auf.