Ein Spiel „Super Mario Brothers“ zu beenden, kann schwer sein – sehr, sehr schwer.

Zu diesem Schluss kommt eine neue Arbeit von Forschern des MIT, der University of Ottawa und des Bard College at Simon's Rock. Sie zeigen, dass das Problem der Lösung eines Levels in „Super Mario Brothers“ genauso schwierig ist wie die schwierigsten Probleme in der „Komplexitätsklasse“ PSPACE, was bedeutet, dass es sogar noch komplexer ist als das Problem des Handlungsreisenden oder das Problem der Faktorisierung großer Zahlen oder eines der anderen schwierigen Probleme, die zur bekannteren Komplexitätsklasse NP gehören.

In einem Standardspiel „Super Mario Brothers“ rennt Mario über ein Gelände, das sich auf der rechten Seite des Bildschirms entfaltet. Während er gegen Monster kämpft, muss er verschiedene Aufgaben erfüllen, darunter das Navigieren durch Ziegelstrukturen, die aus der Grundebene des Spiels herausragen, aber auch ohne Unterstützung in der Luft hängen können. Der Abschluss eines Levels wird dadurch gekennzeichnet, dass Mario einen Fahnenmast erreicht.

Das neue Papier versucht nicht nachzuweisen, dass irgendeines der Levels in kommerziellen Versionen von „Super Mario Brothers“ PSPACE-schwer ist, sondern lediglich, dass es möglich ist, PSPACE-harte Levels aus den Rohmaterialien der „Super Mario“-Welt zu konstruieren.

Die Arbeit knüpft an eine Arbeit von vor zwei Jahren mit zwei gleichen Co-Autoren an, die zeigte, dass „Super Mario Brothers“ mindestens so schwer ist wie die schwierigsten Probleme in NP. Ob es jedoch schwieriger war, konnten die Forscher damals noch nicht feststellen. „PSPACE ist sein endgültiges Zuhause“, sagt Erik Demaine, MIT-Professor für Elektrotechnik und Informatik und Mitautor beider Artikel.

Demaine und seine Kollegen – Giovanni Viglietta, Postdoc in Elektrotechnik und Informatik an der University of Ottawa und Mitautor der früheren Arbeit; und Aaron Williams, Professor für Informatik am Bard College in Simon's Rock, werden ihre neue Arbeit nächste Woche auf der International Conference on Fun with Algorithms vorstellen.

Fragen der Proportionen

Theoretische Informatiker kategorisieren Algorithmen nach ihrer Ausführungszeit, die sie anhand der Anzahl der Datenelemente messen, die die Algorithmen manipulieren. Ein Algorithmus zum Finden der größten Zahl in einer Liste von N Zahlen hat beispielsweise eine Laufzeit proportional zu N. Ein Algorithmus, der beispielsweise die Flugentfernungen zwischen N Flughäfen auf einer Karte berechnet, hat eine Laufzeit proportional zu N^2 , denn für jeden Flughafen muss die Entfernung zu jedem anderen berechnet werden.

Algorithmen, deren Laufzeit proportional zu N potenziert ist, werden „Polynom“ genannt. Ein polynomialer Algorithmus, dessen Laufzeit beispielsweise proportional zu N^3 ist, ist langsamer als einer, dessen Laufzeit proportional zu N ist. Diese Unterschiede verblassen jedoch im Vergleich zu den Laufzeiten exponentieller Algorithmen, deren Laufzeit proportional zu 2^N ist .

Wenn ein Algorithmus, dessen Ausführungszeit proportional zu N ist, eine Sekunde benötigt, um eine Berechnung mit 100 Elementen durchzuführen, benötigt ein Algorithmus, dessen Ausführungszeit proportional zu N^3 ist, fast drei Stunden. Aber ein Algorithmus, dessen Ausführungszeit proportional zu 2^N ist, dauert 300 Trillionen Jahre.

Die Komplexitätsklasse NP ist eine Menge von Problemen, deren Lösungen in polynomieller Zeit verifiziert werden können, auch wenn das Finden dieser Lösungen – soweit bekannt – exponentielle Zeit in Anspruch nimmt. Um das bekannteste Beispiel zu verwenden: Das Faktorisieren einer 1.000-stelligen Zahl übersteigt wahrscheinlich die Kapazität aller Computer auf der Welt im Leben des Universums, aber die Überprüfung einer Lösung – das Multiplizieren der Faktoren – könnte ein Smartphone leisten.

PSPACE enthält wie NP Probleme, deren Lösung scheinbar exponentielle Zeit in Anspruch nimmt. Aber auch die Verifizierung der schwierigsten Probleme in PSPACE – der PSPACE-schweren Probleme – nimmt exponentiell Zeit in Anspruch. Das macht PSPACE in gewisser Weise zu einem natürlichen Ort für ein Videospiel. Herauszufinden, wie man ein teuflisch schwieriges Level von „Super Mario Brothers“ abschließt, könnte lange dauern, aber auch das Navigieren in diesem Level kann lange dauern, selbst mit der Lösung in der Hand.

Grundlegende Komponenten

In ihrer früheren Arbeit beschrieben Demaine, Viglietta und Kollegen eine generische Videospielstruktur, die sie eine verschlossene Tür nennen. Durch die Struktur muss ein Pfad führen, der entweder sicher überquert werden kann oder nicht, und es muss für den Spieler eine Möglichkeit geben, den Zustand des Pfads zu ändern.

Da die verschlossene Tür zwei mögliche Zustände hat, kann sie einen Teil des Computerspeichers darstellen, und da es einen Weg durch sie gibt, der geöffnet oder geschlossen werden kann, kann sie als Element eines Rechenschaltkreises dienen. Die Forscher konnten zeigen, dass jedes Rechenproblem durch verschlossene Türen beschrieben werden kann, die in der richtigen Konfiguration aneinandergereiht sind. Wenn das Problem exponentiell schwierig ist, ist es auch exponentiell schwierig herauszufinden, wie man das Level abschließt.

In der früheren Arbeit demonstrierten Demaine, Viglietta und ihre Kollegen in mehreren Versionen des Spiels „Donkey Kong Country“, wie man verschlossene Türen baut, in „Super Mario Brothers“ konnten sie jedoch nicht herausfinden, wie man eine solche baut. „Wir dachten, es sei unmöglich“, sagt Demaine.

Aber es ist nicht. Die in der neuen Arbeit beschriebene verschlossene Tür nutzt ein Monster aus der „Mario Brothers“-Welt namens „Stachel“, das sich ständig zwischen zwei Barrieren hin und her bewegt, aber niemals spontan über eine von ihnen springt. Als sich der Stachel jedoch einer Barriere nähert, kann Mario den Boden darunter anstoßen und ihn umwerfen. Befindet sich der Stachel in der neuen verschlossenen Tür der Forscher auf einer Seite einer Barriere, ist der Weg durch die Struktur unpassierbar. liegt es auf der anderen Seite, ist der Weg offen. Und separate Wege durch die Struktur ermöglichen es Mario, den Stachel von einer Seite zur anderen zu stoßen.

Spaß und Spiele

Das Ergebnis könnte Auswirkungen haben, die über das Design der immer verwirrenderen Spiele von „Super Mario Brothers“ hinausgehen. Mathematisch gesehen unterscheiden sich Videospiele nicht sehr von Rechenmodellen realer physikalischer Systeme, und die zum Nachweis der Komplexität verwendeten Werkzeuge könnten an das andere angepasst werden.

„Ich bin wirklich begeistert von dieser Art von Härtenachweisen und habe sie in den letzten Jahren stark vorangetrieben“, sagt Demaine. „Ich habe sogar einen ganzen Kurs über sie gehalten. Ich bin ziemlich gut darin, nur durch Übung, und ich wollte das irgendwie in eine Form bringen, die andere Leute lernen können. Der Kurs war also ein erster Versuch, dies zu tun. Aber es ist bereits eine wirklich nützliche Referenz. Ich schaue mir ständig diese Vorlesungsunterlagen an, um zu sehen: ‚Ist diese Variante dieses Problems schwierig?‘“

„Meine Hoffnung besteht darin, durch diesen Kurs und diese Art von Aufsätzen mehr Menschen dazu zu ermutigen, dies zu tun, weil dadurch wirklich viel Fachwissen aufgebaut wird, das es einfacher macht, Probleme zu meistern“, fährt er fort. „Je mehr Übung wir als Kollektiv bekommen, desto besser können wir solche Probleme lösen. Und es ist wichtig, die Grenzen von Algorithmen zu kennen.“