¶ Tetris
Tetris ist ein beliebtes Computerspiel erstmals veröffentlicht in 1984[1]. Das Ziel des Spiels ist es nacheinander von oben nach unten fallende Spielsteine so zu verschieben und platzieren, dass möglichst viele horizontale Reihen gefüllt werden. Eine vollständig gefüllte Reihe wird gelöscht und die spielende Person erhält Punkte. Das Spiel endet, falls die Spielsteine zu hoch gestapelt werden und einer den oberen Spielfeldrand berührt.
¶ Spielablauf
In Tetris erscheinen Spielsteine, auch Tetrominos genannt, in verschiedenen Formen, wobei stets nur ein Spielstein nach dem anderen erscheint.
Abb. 1: Alle Tetris Spielsteine mit beigefügten Namen (eigene Darstellung, Namen und Orientierungen adaptiert aus Tetris is hard, even to approximate[2])
In den meisten Versionen des Spiels ist die Reihenfolge dieser Spielsteine zufällig. Die spielende Person steuert aktiv den neuen Spielstein, der kontinuierlich von oben nach unten fällt, bis dieser entweder auf den unteren Rand den Spielfeldes oder von oben auf einen zuvor platzierten Spielstein stößt. Der fallende Spielstein kann beliebig oft nach links oder nach rechts verschoben oder um 90º rotiert werden. Die einzige Begrenzung hierbei ist, dass der Spielstein hierbei aber nicht durch andere Spielsteine wandern darf. Sobald eine Reihe vollständig gefüllt ist, verschwindet sie, die Reihen über der freigeräumten Reihe werden um eins nach unten verschoben und man erhält Punkte. Es können auch mehrere Reihen gleichzeitig freigeräumt werden. Werden mit Hilfe eines "I"-Steins vier Reihen gleichzeitig geräumt, bezeichnet man dies als Tetris. Das Ziel des Spiels ist es möglichst viele Reihen zu füllen und löschen. In Tetris kann meist nicht gewonnen werden, da das Spiel einfach so lange weiter geht, bis ein Spielstein den oberen Spielfeldrand berührt.
¶ Die "Offline Version" von Tetris
Um den späteren Beweis für die NP-Vollständigkeit zu vereinfachen, verwenden wir eine sog. offline Version von Tetris. Diese offline Version unterscheidet sich vom herkömmlichen Tetris hauptsächlich in einem Aspekt. Die Reihenfolge der Spielsteine ist vollständig deterministisch und endlich, im Vergleich zur probabilistischen und unendlichen Spielsteinreihenfolge des üblichen Spiels. Da die Schwierigkeit von offline Tetris grundlegend einfacher ist als die des herkömmlichen Tetris, können wir somit die Komplexität des herkömmlichen Tetris erahnen.
¶ Komplexität von Tetris-Spielzielen
Viele verschiedene Ziele sind in (offline) Tetris NP-Vollständig[2:1], darunter:
- Das Maximieren der Anzahl von freigeräumten Reihen bei einer gegeben Spielsteinreihenfolge
- Das Maximieren der Anzahl an platzierten Spielsteinen bevor das Spiel zu Ende geht
- Das Maximieren der Anzahl an Tetrisen
- Das Minimieren der maximal erreichten Höhe bei einer gegeben Spielsteinreihenfolge
¶ Formalisierung des gesamten Spielablaufs
Für die Formulierung unseres -Problems benötigen wir klare Definitionen unseres Spielzustandes
¶ Das Spielfeld
Unser Spielfeld besteht aus Reihen und Spalten. Die Felder sind dabei von unten nach oben und links nach rechts indiziert, wobei für jedes Feld mit und gilt, dass es entweder gefüllt oder nicht gefüllt ist. Außerdem können keine gefüllten Reihen existieren, da diese sofort geräumt werden und es existieren keine vollständig leeren Reihen unter gefüllten Feldern.
¶ Die Spielsteine
Abb. 2 Spielsteine mit markiertem Zentrum (eigene Darstellung, adaptiert aus Tetris is hard, even to approximate[2:2])
Wir können den Zustand jedes unserer sieben Spielsteine mit Hilfe eines 4-Tupels darstellen.
- beschreibt hierbei um welche Art Spielstein es sich handlet
- beschreibt die Orientierungen ausgehend von dem Urzustand des Spielsteins
- die Position des Zentrums des Spielsteins (s. Abb. 2) auf unserem Spielfeld
- beschreibt ob der Spielstein sich noch bewegen kann oder nicht
Zum Beispiel wird der Zustand des folgenden Spielsteins mit dem Tupel beschrieben:
Abb. 3: T auf dem Spielfeld (eigene Darstellung)
¶ Rotieren
Unser Rotationsmodell ist eine berechenbare Funktion , wobei und Zustände sind, der Rotationswinkel und unser Spielfeld.
Breukelaar et al formulierten für folgende Bedingungen:[2:3]
- Falls die Rotation legal ist, dann gilt für ein , wobei und die neue Position des Zentrums nach der Rotation sind. Falls die Rotation nicht legal ist, gilt
- Die Legalität hängt nur von der -großen Nachbarschaft des Spielsteins ab
- Für eine "leere" Nachbarschaft gilt also, dass die Rotation legal ist
- Falls eine Rotation legal ist, dann belegt kein Feld was bereits in belegt ist
- Die Funktion muss "angemessen" sein:
5.1 Ein Spielstein kann nicht von einer Region des Spielfelds zu einer anderen springen. Es muss ein Pfad von leeren Feldern von zu in existieren
5.2 Ein Spielstein kann nicht an einer übermäßig eingeengten Stelle des Spielfelds vorbeikommen. In anderen Worten, wenn eine ein Feld breite Lücke existiert, darf keiner unserer Steine außer möglicherweise ein I-Stein hindurchkommen
¶ Der Spielablauf
Jetzt können wir also den Spielablauf an sich beschreiben. Unsere legalen Spielzüge für ein Spielstein und einem Spielfeld sind also:
- Eine Rotationen mit
- Eine Verschiebung um eine Spalte, sofern die benachbarten Felder von in hinreichend frei sind und keine Blockaden oder anderen Spielsteine die Bewegung verhindern. Hier ist unser neuer Zustand
- Unseren Spielstein um eine Reihe fallen lassen, falls alle Felder direkt unterhalb unseres Spielsteins frei sind in . Der neue Zustand ist
- Eine Fixierung, falls unser Spielstein den unteren Spielfeldrand oder einen anderen Speilstein unter sich berührt.
Für einen fixierten Spielstein gibt es logischerweise keinen legalen Zug, da wir immer nur unseren einen nicht fixierten Spielstein kontrollieren.
Wir definieren uns außerdem noch einen Ablauf (trajectory) eines Spielsteins auf unserem Spielfeld , was einfach eine Reihe von legalen Zügen ist, die in einer Fixierung enden. Nach eines solchen Ablaufs erhalten wir ein neues Spielfeld . Z.B. haben wir das leere Spielfeld . Wir rotieren unseren Spielstein zweimal um im Uhrzeigersinn und bewegen ihn in das linksuntere Eck des Spielfelds. Dies ist unser Ablauf , der zum Spielfeld (vgl. Abb. 3) führt.
Da in unserer offline Version von Tetris, alle Spielsteine im vorhinein bekannt sind. Definieren wir unser Tetris Spiel . In anderen Worten, unser Spielfeld zu Beginn und unsere Spielsteine die folgen werden.
Unser Spielablauf kann somit also mit Hilfe einer Ablaufssequenz (trajectory sequence) beschrieben werden. ist einfach eine Sequenz für unser Spiel , wo der Ablauf eines Spielsteins auf dem Spielfeld für das neue Spielfeld verantwortlich ist.
¶ Die NP-Vollständigkeit von Tetris
¶ Tetris liegt in NP
Wie zuvor erwähnt, gibt es in Tetris mehrere Ziele welche wir betrachten können. Formal definieren wir also unser Problem für ein Ziel wie folgt:
Eingabe: Ein Tetris Spiel
Frage: Existiert eine Ablaufssequenz , so dass erfüllt ist?
Breukelaar et al zeigen, dass für jedes azyklische Ziel gilt, dass [2:4]. Ein Ziel ist azyklisch, falls für alle Spiele eine Ablaufssequenz existiert, in der keine Spielsteinzustände wiederholt werden, wie bspw. unseren Spielstein -mal im Uhrzeigersinn um rotieren. Die Ziele die wir betrachten sind azyklisch, da sie nur davon abhängig sind wo letztenendes der Spielstein platziert wird. Indem wir die Zustände einzelnd abprüfen, können wir also den Wahrheitswert von in polynomieller Zeit überprüfen[2:5].
Angenommen wir haben also ein Spiel , gesucht ist ein Algorithmus. Wir raten zunächst eine azyklische Ablaufssequenz . Das Überprüfen ob legal ist erfolgt erneut in polynomieller Zeit , in dem wir die einzelnen Züge bei den gegebenen Spielfeldern überprüfen. Da wir uns eben auf azyklische beschränken, ist die Anzahl an Zuständen in den Abläufen auf begrenzt. Der Grund dafür ist, dass unser Spielstein maximal in jeder Position in seinen Orientierungen auftauchen kann und zuletzt noch in einer fixierten Position. Somit gilt . Wir können also in = überprüfen ob erfüllt ist und da wir azyklische betrachten, genügt es azyklische zu erraten.
¶ Reduktionsbeweis
¶ 3-PARTITION
In diesem Reduktionsbeweis reduzieren Breukelaar et al von auf das Problem. Das Problem ist nach Garey und Johnson NP-vollständig[3] und ist dabei wie folgt definiert:
Eingabe: Eine Reihe von nicht-negativen, ganzen Zahlen und eine nicht-negative, ganze Zahl , wobei für jede Zahl gilt
Frage: Existiert eine Partitionierung in Dreiermengen , so dass für alle gilt,
Aufgrund der späteren Konstruktion unseres Spielfelds, wollen wir nur ein erlauben, welches durch teilbar ist. Dafür können wir einfach unsere bestehende Partitionsinstanz nehmen und alle Zahlen, also und , mit multiplizieren.
¶ Konstruktion des Spielfelds
Hier beginnen wir zuerst mit dem Ziel "Maximieren der Anzahl an freigeräumten Reihen", auf mehr Ziele wird später eingegangen. Die Höhe und Breite unseres Spielfelds ist immer abhängig von unserer Partitionsinstanz und es gibt mehrere Wege es aufzubauen. Eine Methode wurde von Demaine et al in 2003 vorgestellt[4]. Hier konzentrieren wir uns aber auf die überarbeitete, vereinfachte Methode aus 2004, nach der Zusammenführung der Paper von Demaine et al und Breukelaar et al[2:6]. Die Idee ist hierbei, dass unser Spielfeld sogenannte "Buckets" besitzt, welche die Dreiergruppen unser Partition repräsentieren. Die Breite dieser Buckets beträgt dabei immer 4, die Höhe der Buckets ist jedoch mit abhängig von unserer Partitionsinstanz. Der Aufbau der Buckets folgt hierbei einem periodischen Muster:
- Die erste Spalte ist leer bis auf die letzten zwei Reihen
- Die zweite Spalte ist vollkommen leer
- In der dritten Spalte, sind immer abwechselnd drei Reihen gefüllt und zwei Reihen leer
- Die vierte Spalte ist vollkommen gefüllt
Was zu diesem Ergebnis führt:
Abb. 4: Ein Bucket, bearbeitet[2:7]
Zusätzlich benötigen wir für die spätere Vollständigkeit und Korrektheit unseres Tetris Ziels eine sogenannte Lock. Diese ist Blöcke hoch und Blöcke breit, jedoch verwenden wir nur eine. Für die Lock gilt:
- Die erste Spalte ist gefüllt, bis auf die oberste Reihe
- Die zweite Spalte ist gefüllt, bis auf die obersten zwei Reihen
- Die dritte Spalte ist leer, bis auf die zweitoberste Reihe
Abb. 5: Die Lock, bearbeitet[2:8]
Wie bereits erwähnt repräsentieren unsere Buckets die Dreiermengen, weshalb wir Buckets benötigen, welche allesamt jeweils Blöcke breit sind. Zusätzlich haben wir unsere Block breite Lock, was zu einer Spielfeldbreite von führt. Da die Buckets und die Lock beide Blöcke hoch sind, muss unser Spielfeld ebenfalls mindestens so hoch sein. Um aber der spielenden Person die Möglichkeit zu geben die Spielsteine zu bewegen und um später zu ermöglichen gewisse Einschränkungen einzuführen, wie bpsw. die Begrenzung an maximalen Drehungen oder Verschiebungen, fügen wir ein paar zusätzliche Reihen hinzu auf die später näher eingegangen wird. Unser gesamtes Spielfeld sieht dann also wie folgt aus:
Abb. 6: Das Spielfeld[2:9]
¶ Idee und Ablauf
Um nun von unserer Instanz auf unser Problem zu reduzieren, erhalten wir abhängig von unseren Zahlen eine unterschiedliche Anzahl an Spielsteinen. Wir gehen nach und nach unsere Menge an Zahlen durch und erhalten für jede Zahl :
- Den sog. Initiator, welcher aus einem -Stein besteht
- Den Filler, wo wir mal die Sequenz erhalten
- Den Terminator, welcher aus einem -Stein und einem -Stein besteht.
Sei z.B. unsere erste Zahl die wir abarbeiten , wir erhalten dann somit der Reihe nach die Sequenz:
Abb. 7: Füllen eines Buckets mit (eigene Darstellung)
Das Ziel der spielenden Person ist es, alle Buckets auf die gleiche Höhe zu füllen. Intuitiv finden wir dabei die Dreiermengen, repräsentiert durch die Buckets, in die die Zahlen gehören. Genau dann wenn wir eine "Ja"-Instanz unseres -Problems haben und die Steine richtig zusammensetzen sieht unser Spielfeld so aus:
(Abb. 8: Alle Buckets gefüllt[2:10])
Nun erhalten wir zum Abschluss noch folgende Spielsteine:
- -mal ein -Stein
- Ein -Stein
- -mal ein -Stein
Wir benötigen die -Steine, um unsere Buckets vollständig zu füllen. Nachdem alle Buckets gefüllt sind, öffnen wir unsere Lock mit dem , da dies nun die oberen Reihen räumt. Dies ermöglicht uns, unsere letzte Spalte mit -Steinen zu füllen und die Reihen zu räumen. Da wir in unserer Partitionsinstanz nur ein erlauben, welches durch teilbar ist, erhalten wir eine ganze Zahl an -Steinen.
¶ Vollständigkeit und Korrektheit
Breukelaar et al beginnen hierbei zuerst mit der Annahme, dass wir eine "Ja"-Instanz unseres Problems haben[2:11].
Da wir eine "Ja"-Instanz vor uns haben, können unsere Zahlen in die Dreiermengen so aufgeteilt werden, dass . Um zu zeigen, dass alle Buckets somit gefüllt werden können, betrachte . Für jede Zahl gilt nach unserem vorher beschlossenen Spielablauf, dass wir zuerst unseren Initiator erhalten, dann mal unsere Filler-Sequenz und zuletzt einmal unseren Terminator. Füllen wir unseren leeren Bucket nach dem Muster, welches zuvor genannt wurde, füllen wir mit dem Initiator die ersten Reihen. Mit dem wiederholenden Muster unseres Fillers füllen wir Reihen -mal. Mit unserem Terminator füllen wir weitere Reihen vollständig. D.h. nachdem wir bearbeitet haben, sind Reihen gefüllt, was bedeutet nach unserer gesamten Dreiermenge haben wir Reihen vollständig gefüllt.
Danach folgt unsere "Abschlusssequenz". Mit unseren -Steinen füllen wir unsere Buckets bis zu . Öffnen die Lock mit unserem -Stein, was Reihen und freiräumt und füllen den Rest mit unseren -Steinen. D.h. das gesamte Spielfeld wird geräumt und somit die Anzahl an freigeräumten Reihen maximiert, falls wir eine "Ja"-Instanz besitzen.
Um zu sehen, dass der genannte Ablauf der einzig valide ist, genügt es die Kombinationen zu betrachten, welche der spielenden Person zur Verfügung stehen.
Abb. 9: Initiator Stellung, alle nicht-Initiator Spielsteine[2:12]
Betrachten wir einen Bucket der einen Initiator erwartet, führen die und -Steine immer dazu, dass bestimmte Bereiche unseres Spielfelds für zukünftige Teile blockiert sind. Dies läuft für die anderen Möglichkeiten analog ab. Es ist auch leicht zu sehen, warum wir keinen Spielstein über der Reihe platzieren sollten, um die Anzahl an freigeräumten Reihen zu maximieren. Wir bekommen nämlich genau so viele Steine, um die Felder die in den teilsgefüllten Reihen bis sind, zu füllen. Um also Reihen zu räumen, müssen wir unsere Spielsteine genau in diese Felder der teilsgefüllten Reihen legen.
Haben wir eine "Nein"-Instanz, können wir keine Dreiermengen bilden, wo alle Elemente immer zu auf summieren. Intuitiv, können wir also nicht alle Buckets zur gleichen Höhe füllen. Um die Anzahl an freigeräumten Reihen zu maximieren müssen wir aber, wie man sieht, der Sequenz folgen, aber dürfen ebenso keinen Spielstein über der Reihe platzieren. Somit können wir also nicht die Anzahl an freigeräumten Reihen maximieren.
¶ Andere Ziele und Begrenzungen
Für andere Ziele wird der Ablauf der Reduktion von Breukelaar et al lediglich leicht angepasst.
¶ Maximieren der Anzahl an platzierten Spielsteinen bevor das Spiel zu Ende geht
Die Idee hinter der Modifikation des Spielfelds für das Ziel der Maximierung der Anzahl bevor das Spiel zu Ende geht ist, dass wir eine Niederlage für eine "Nein"-Instanz erzwingen wollen. Wir erweitern unser Spielfeld um Spalten, wobei die obersten Reihen gefüllt sind. Außerdem fügen wir Reihen unter unserem Spielfeld hinzu. Zuerst zwei gefüllte Reihen, welche aber eine -förmige Lock besitzt in den letzten 3 Spalten, ähnlich wie unser originales Feld. Die restlichen Reihen sind leer bis auf die erste Spalte.
Abb. 10: Das Spielfeld für das Maximieren der Anzahl an platzierten Spielsteinen[2:13], bearbeitet
Zusätzlichlich erhalten wir nach unser originalen Spielsteinsequenz noch ein und -mal ein , wobei . Wenn unser groß genug ist, heißt so dass , erzwingen wir eine Niederlage für eine "Nein"-Instanz, da unser Spielfeld mit Spalten ungerade ist und somit nur mit -Steinen keine Reihe geräumt werden kann. Nur genau dann wenn, wir eine "Ja"-Instanz besitzen, können die Reihen wie gewohnt geräumt werden und wir können somit den unteren Bereich problemlos mit unseren -Steinen füllen.
¶ Maximieren der Anzahl an Tetrisen
Hierfür wird unser Spielfeld nur leicht angepasst. Wir fügen einfach weitere Reihen unterhalb unseres Spielfelds hinzu, welche komplett gefüllt sind bis auf die vierte Spalte und erhalten am Ende unsere bisherigen Spielsteinesequenz noch einen weiteren -Stein. Der Grund dafür ist, da zwar mit einer "Nein"-Instanz nicht Reihen geräumt werden können, kann dennoch die Anzahl an Tetrisen bei dem vorherigen Spielfeld gleich sein, da wenn die spielende Person Reihen freiräumt somit trotzdem Tetrise erzielen könnte. Das neue Feld sorgt dafür, dass somit das letzte Tetris nur erzielt werden kann, falls alle Reihen geräumt wurden, was nur bei einer "Ja"-Instanz geschieht.
Abb. 11: Modifiziertes Feld für das Maximieren der Anzahl an Tetrisen[2:14], bearbeitet
¶ Oberer Bereich unseres Spielfelds
Der Grund warum wir unser originales Spielfeld so definierten, dass die Höhe beträgt, hängt mit der Einschränkung zusammen wie wir unsere spielende Person in Tetris die Spielsteine bewegen lassen. In herkömmlichen Versionen von Tetris, kann bspw. nur eine begrenzte Anzahl von Verschiebungen und Rotationen vollendet werden, bevor der Spielstein um eine Reihe sinkt. Die Reduktion von Breukelaar et al. erfordert lediglich, dass im Spiel nur eine Verschiebung gemacht werden muss, bevor unser Spielstein um eine Reihe fällt oder fixiert wird. Da ein Spielstein um höchstens Spalten verschoben und -mal rotiert werden muss, besitzen wir zusätzliche Reihen für die Verschiebungen und Rotationen, da letzteres eine freie -Nachbarschaft benötigt[2:15].
¶ Referenzen
History of Tetris: https://tetris.com/history-of-tetris ↩︎
Breukelaar, R., Demaine, E. D., Hohenberger, S., Hoogeboom, H. J., Kosters, W. A., & Liben-Nowell, D. (2004). Tetris is hard, even to approximate. International Journal of Computational Geometry & Applications, 14(01n02), 41-68. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Garey, Michael R. and David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5. Pages 96–105 and 224. ↩︎
Demaine, E. D., Hohenberger, S., & Liben-Nowell, D. (2003). Tetris is hard, even to approximate. In Computing and Combinatorics: 9th Annual International Conference, COCOON 2003 Big Sky, MT, USA, July 25–28, 2003 Proceedings 9 (pp. 351-363). Springer Berlin Heidelberg. ↩︎