Als Kind der 1990er Jahre kam ich natürlich nicht um das Kultspiel Tetris herum. Stundenlang versuchte ich auf meinem Gameboy die herabsinkenden Bausteine so zu positionieren, damit sie möglichst lückenlos das Spielfeld ausfüllten. Das Fiese dabei: Mit der Zeit fallen die Blöcke immer schneller vom oberen Bildschirmrand herunter – so schnell, dass meine Daumen kaum mit der Steuerung hinterherkamen. Ich kann mich zwar nicht mehr an alle Details erinnern, aber besonders weit kam ich bei Tetris leider nie.

Wenn ich rückblickend über Tetris nachdenke, sehe ich viele Verbindungen zur Mathematik (als ich noch »aktive Spielerin« war, ist mir das natürlich nicht aufgefallen). Im Prinzip lassen sich alle Spiele aus mathematischer Sicht untersuchen; ich habe in der Vergangenheit bereits über die Mathematik von »Candy Crush«, »Magic: The Gathering«, »Dobble« oder »Wordle« berichtet. Bei Tetris gibt es sogar eine ziemlich offensichtliche Verbindung zur Geometrie: Beim beliebten Kultspiel rieseln nacheinander sieben verschiedene Arten von Bausteinen vom oberen Spielfeld herab und bleiben auf der unteren Ebene liegen. Während des Sinkflugs kann ein Spieler die Bausteine drehen und nach links oder rechts verschieben. Ziel ist es, sie so anzuordnen, dass sie möglichst das gesamte Spielfeld lückenlos ausfüllen.

Wer sich gerne mit Mathematik beschäftigt, den erinnert diese Aufgabe vielleicht an Parkettierungsprobleme. Bei diesen muss man herausfinden, ob es möglich ist, eine Ebene lückenlos mit einem unendlich großen Satz an Kacheln zu bedecken. Aber Tetris unterscheidet sich von solchen Aufgaben in einem wesentlichen Punkt: Die Bausteine bauen sich nicht einfach immer höher auf. Falls eine Reihe vollständig von Blöcken ausgefüllt ist, dann wird diese Reihe gelöscht – die Bausteine verschwinden. Darüber befindliche Steine fallen dann bis zur nächsten Ebene herunter.

Selbstverständlich ist nicht nur mir der Zusammenhang zu Parkettierungsproblemen aufgefallen. Und deshalb war Tetris in der Vergangenheit Teil mehrerer mathematischer Facharbeiten. Insbesondere interessierten sich die Forschenden für die Frage, ob sich stets beurteilen lässt, ob ein Tetris-Spiel »lösbar« ist: Angenommen, man weiß, welche Steine in welcher Reihenfolge im Spiel erscheinen werden (und es sind nur endlich viele) – lassen sich die Bausteine dann so anordnen, dass das Spielfeld am Ende leer ist?

Mathematiker interessiert hierbei, wie aufwändig es ist, die oben genannte Frage zu beantworten. Sprich: Wie viel Rechenleistung muss man aufwenden, um anhand einer vorgegebenen Spielsituation herauszufinden, ob das Tetris-Spiel lösbar ist oder nicht? Wie sich herausstellt, ist diese Frage extrem schwer zu beantworten. Das macht es aus mathematischer Sicht zu einem der komplexesten Spiele überhaupt.

Was ist eigentlich komplex?

Die zuvor geschilderte Art von Problem fällt in den Forschungsbereich der Komplexitätstheorie. Eine mathematische Fragestellung gilt als umso komplexer, je schneller der benötigte Rechenaufwand mit der Größe des Problems anwächst.

Inzwischen haben Fachleute zahlreiche Komplexitätsklassen definiert, also Kategorien für die Schwierigkeit von Problemen. Die zwei bekanntesten unter ihnen heißen P und NP. Vereinfacht lassen sie sich so erklären: P-Probleme sind einfach zu lösen. NP-Probleme sind hingegen sehr schwer zu lösen, lassen sich aber dafür einfach überprüfen, falls man eine vermeintliche Lösung präsentiert bekommt. NP-Probleme kann man sich wie ein Sudoku-Rätsel vorstellen. Es dauert mitunter stundenlang, bis die Felder ausgefüllt sind; aber es braucht nur wenige Minuten, um zu prüfen, ob die Lösung korrekt ist.

• P-Probleme
  P-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 aufwändig erscheinen – aber ein Computer kann das stets bewältigen, egal wie riesig die Zahlen sind.
• NP-Probleme
  Bei NP-Problemen ist das hingegen anders. Diese können für einfache Spezialfälle vielleicht noch gelöst werden, aber 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.

Unter diesen Gesichtspunkten lässt sich auch das Kultspiel Tetris untersuchen, das der russische Programmierer Alexei Paschitnow im Jahr 1984 herausbrachte. Schnell entwickelte sich Tetris zu einem Kassenschlager: Es wurde allein mehr als 400 Millionen Mal als kostenpflichtiges Onlinespiel heruntergeladen. Zählt man die Verkäufe von Tetris-Spielen für Konsolen wie den Gameboy hinzu, wird die Gesamtzahl sogar auf 520 Millionen geschätzt.

Von Tetris zum Matheproblem

Aber wie bestimmt man überhaupt, wie komplex eine Aufgabe ist? Entscheidend ist dabei die Idee, verschiedene Probleme miteinander zu vergleichen. Der Gedanke ist hierbei: Wenn jeder Algorithmus, der Aufgabe A löst, auch eine Aufgabe B lösen kann, dann ist A komplexer als B. Mathematiker sagen: B ist auf A »reduzierbar«. Indem man also Tetris mit einem anderen bekannten P- oder NP-Problem vergleicht, lässt sich dessen Komplexität ermitteln. Aber welche Aufgabe soll als Referenz dienen?

Anfang der 1970er Jahre zeigten die Informatiker Stephen Cook und Leonid Levin, dass es ein bestimmtes NP-Problem gibt, das »SAT«-Problem, auf das sich alle anderen NP-Aufgaben reduzieren lassen. Damit ist SAT das komplexeste Problem der NP-Klasse. Wie sich allerdings kurze Zeit später herausstellte, trifft diese Eigenschaft nicht nur auf SAT zu: Es gibt weitere Aufgaben, auf die alle anderen NP-Probleme reduzierbar sind. Man nennt solche Probleme »NP-vollständig«. 1972 hat der Informatiker Richard Karp 21 NP-vollständige Aufgaben identifiziert, darunter das 3-Partitionsproblem.

Dieses Partitionsproblem haben Fachleute im Jahr 2003 mit Tetris in Verbindung gebracht. Das 3-Partitionsproblem beschäftigt sich mit der Frage, ob sich eine vorgegebene Menge ganzer Zahlen, zum Beispiel {1, 2, 5, 6, 7, 9}, so in Teilmengen mit je drei Elementen unterteilen lässt, dass die Summe der Zahlen in den Teilmengen stets gleich ist. Für {1, 2, 5, 6, 7, 9} wäre eine Aufteilung {1, 5, 9} und {2, 6, 7}; die Inhalte beider Teilmengen summieren sich jeweils zu 15. Nicht für jede vorgegebene Menge ist eine solche Aufteilung möglich. Herauszufinden, ob es diese gibt oder nicht, erweist sich als extrem schwer: Das 3-Partitionsproblem ist NP-vollständig.

Die Fachleute konnten 2003 zeigen, dass sich die Frage, ob ein Tetris-Spiel in einer vorgegebenen Spielsituation lösbar ist, auf das Partitionsproblem abbilden lässt. Damit haben sie bewiesen, dass die Fragen »Lässt sich eine Menge in eine 3-Partition zerlegen?« und »Kann man das Tetris-Spielfeld leeren?« aus mathematischer Sicht identisch sind. Hierfür setzten die Forschenden die Lücken im Tetris-Spiel mit den Teilmengen des Partitionsproblems gleich, und die fallenden Bausteine entsprechen den Zahlen, die aufgeteilt werden müssen. So konnten sie zeigen: Falls die Menge an Zahlen in dreielementige Teilmengen mit gleicher Summe aufteilbar ist, dann lässt sich auch das Tetris-Spielfeld komplett leeren.

Damit gehört Tetris zu den komplexesten Spielen. Denn die Frage, ob sich die vorgegebenen Steine passend anordnen lassen, fällt in die Klasse der NP-vollständigen Probleme. Je länger die Folge an Bausteinen ist, die das Spiel enthält, desto aufwändiger wird es für einen Computer, die Lösbarkeit zu ermitteln. Und tatsächlich werden herkömmliche Rechner sehr schnell überfordert sein: Es gibt keinen Algorithmus, der das Problem effizient lösen kann.

Tetris stößt an die Grenzen der Berechenbarkeit

Tatsächlich ist das aber noch nicht das Ende. Denn Tetris besitzt sogar noch komplexere Eigenschaften, wie die zwei Informatiker Hendrik Jan Hoogeboom und Walter Kosters von der Universität Leiden im Jahr 2004 herausfanden. Sie beschäftigten sich damals mit einer leicht abgewandelten Fragestellung. Angenommen, man würde das Spiel passiv spielen – also nur zuschauen, wie die Spielsteine von oben herabregnen, ohne sie zu drehen oder zu verschieben. Zudem sei der Zufallsgenerator des Spiels kaputt: Es sinken nur die länglichen I-förmigen Steine hinunter. Und nun fragten sich die beiden Forscher: Gibt es unter einer vorgegebenen Menge von Abfolgen von I-förmigen Steinen (in denen sie je eine unterschiedliche Platzierung und Ausrichtung haben) eine bestimmte Folge, für die das Tetris-Spielfeld am Ende leer ist? Anders ausgedrückt: Wenn ich Ihnen zum Beispiel acht verschiedene Möglichkeiten nenne, wie 40 I-förmige Steine auf ein leeres Tetris-Feld herabsinken – könnten Sie dann entscheiden, ob es unter diesen acht Möglichkeiten eine gibt, bei der das Spielfeld am Ende leer ist?

Wie Hoogeboom und Kosters bewiesen, ist diese Frage nicht nur schwer zu beantworten – also nicht nur NP-vollständig. Nein, sie ist sogar unentscheidbar. Das heißt, es gibt Fälle, in denen sich die Frage überhaupt nicht beantworten lässt. Nicht einmal dann, wenn man unendlich viel Rechenleistung zur Verfügung hätte. Denn tatsächlich lässt sich die genannte Fragestellung auf ein Problem abbilden, das mit den berüchtigten Unentscheidbarkeitssätzen von Kurt Gödel zusammenhängt. Diese besagen, dass es in der Mathematik stets Aussagen geben wird, die sich weder beweisen noch widerlegen lassen. Und das trifft auch auf Tetris zu. Es wird also immer Fragen rund um das Spiel geben, die sich nicht beantworten lassen.

Zugegeben: All diese Fragestellungen haben wahrscheinlich keinerlei Auswirkungen darauf, wie erfolgreich man beim Tetrisspielen ist. Bei der Geschwindigkeit, mit der die Steine herabsinken, bleibt kaum Zeit, um über mathematische Probleme nachzudenken. Und außerdem besteht der Witz des Spiels ja darin, dass man eben nicht im Voraus weiß, wo und in welcher Ausrichtung die nächsten Spielsteine erscheinen.

Was ich aber fast noch bemerkenswerter finde als die ganze Mathematik hinter Tetris, ist, dass es auch nach mehr als 40 Jahren immer wieder Fortschritte beim Spielen gibt. Und das, obwohl sich Tetris kaum verändert hat. So hat es eine als »Rolling« bezeichnete Spieltechnik (mit der sich sehr schnelle Eingaben machen lassen) erlaubt, so weit ins Spiel vorzudringen wie noch nie. Früher galt das 29. Level stets als unüberwindbare Grenze, ab der die Steine so schnell herunterregnen, dass selbst die weltbesten Spieler versagen. Doch durch das Rolling knackte im Jahr 2023 ein damals 13-Jähriger alle bisherigen Rekorde, spielte das Spiel bis zum Level 157 durch und brachte es damit zum Absturz. Mal sehen, welche Überraschungen Tetris in Zukunft noch bereithält.