¶ Geschichte
Tetris (russisch Тетрис) ist ein Puzzle-Spiel. Es wurde von dem russischen Programmierer Alexey Pajitnov entwickelt. Die erste Version wurde im Jahr 1984 auf einem Elektronika-60-Rechner fertiggestellt. Das Spiel wurde über 425 Millionen Mal verkauft und ist für mehr als 65 Computerplattformen erschienen. Tetris gilt auch als eines der einflussreichsten Spiele im Genre der Puzzle-Spiele und in der Popkultur. Es war Gegenstand akademischer Forschung, einschließlich Untersuchungen zu seinen psychologischen Auswirkungen.[1]
¶ Rekordzahlen
-
Tetris ist eines der meistverkauften Spiele aller Zeiten: Bis Oktober 2023 wurden 502 Millionen Exemplare verkauft.[2]
Das Spiel erlangte große Bekanntheit, was dazu führte, dass das Spiel psychologisch untersucht wurde, unter anderem hinsichtlich des sogenannten „Tetris-Effekts“. -
Tetris hält den Guinness-Weltrekord als das am häufigsten auf verschiedene Plattformen portierte Spiel (70 Mal).
¶ Spielprinzip
¶ Tetromino
Tetromino ist eine Kombination aus dem Präfix tetra- (aus dem Altgriechischen τετρα-), welches vier bedeutet, und „Domino“. Der Begriff wurde 1953 von Solomon W. Golomb eingeführt, zusammen mit anderen Bezeichnungen im Zusammenhang mit Polyominos.[3]
Die Tetrominos sind als I, J, L, O, S, T, Z benannt, und in Abb.2 genau dieser Reihenfolge dargestellt.
¶ Spielfeld
Das Spielfeld, auf dem die Tetrominos platziert werden, ist wie ein Raster aufgebaut. Dieses Raster wird oft als „Brunnen“ bezeichnet, insbesondere in älteren Versionen des Spiels. In neueren Tetris-Marken-Spielen wird dafür häufiger der Begriff „Matrix“ verwendet. Das Spielfeld ist von einem Rahmen umgeben, der als Tetrion bekannt ist. Dieses Tetrion spielt eine entscheidende Rolle, da es die Bewegung der Tetrominos sowie deren Verhalten auf dem Spielfeld reguliert und somit die grundlegende Mechanik des Spiels unterstützt.[4]
Die Breite des Spielfelds beträgt mindestens vier Felder, wobei die Höhe theoretisch unendlich sein kann.[5] Dennoch wird in den meisten Fällen eine standardisierte Größe genutzt. In der Regel haben die Spielfelder in Tetris-Spielen eine Breite von zehn Zellen. Die Höhe hingegen variiert typischerweise zwischen 16 und 24 Zellen. In Spielen, die dem Tetris-Richtlinienstandard folgen, wird oft eine sichtbare Höhe von genau 20 Zellen festgelegt. Diese Standardmaße bieten sowohl Herausforderungen als auch strategische Möglichkeiten für die Spieler.[4:1]
¶ Rotationssystem
Das Super Rotation System (SRS) ist der aktuelle Tetris-Richtlinienstandard für die Drehung von Tetrominos und deren sogenannte "Wall Kicks"[6]
Startorientierung und -position:
- Tetrominos erscheinen horizontal, wobei S, Z und I oben ausgerichtet sind.
- I und O starten zentral, während andere Tetrominos leicht nach links verschoben sind.
Grundlegende Rotation:
- Alle Tetrominos rotieren mathematisch um einen festen Punkt (wie in Abb. 4 dargestellt).
- S, Z und I haben zwei vertikale und zwei horizontale Zustände, wodurch präzisere Bewegungen möglich sind.
Wall Kicks:
- Wenn ein Tetromino nicht direkt rotieren kann, wird es in bis zu 5 benachbarten Positionen getestet, bevor die Drehung fehlschlägt.
- Jedes Tetromino (außer O) besitzt eigene Wall-Kick-Daten, die die Verschiebungen bei Drehungen definieren.
¶ Regeln
| Zeilenlöschung | Punkte |
|---|---|
| 1 (Single) | 40 |
| 2 (Double) | 100 |
| 3 (Triple) | 300 |
| 4 (Tetris) | 1200 |
Das Spiel wird auf einem rechteckigen Spielfeld mit fester Breite gespielt. Die sieben genannten Spielfiguren (Tetrominos), die jeweils vier Felder abdecken, fallen von oben und können während des Falls auf folgende Weise positioniert werden:
- Durch Rotation (SRS)
- Durch horizontales Bewegen (links, rechts).
Sobald eine Reihe vollständig besetzt ist, wird sie gelöscht, und alle darüber liegenden Blöcke fallen nach unten. Das Ziel des Spiels ist es, so viele Reihen wie möglich zu löschen, ohne das Spielfeld vertikal zu überfüllen.[5:1]
Punktevergabe:
Jede gelöschte Zeile bringt dem Spieler Punkte, und je mehr Zeilen gleichzeitig gelöscht werden, desto höher fällt die Belohnung aus (dies variiert je nach Spiel).
Ein Beispiel ist das original BPS (Blocks Per Second) Punktesystem[7] in Tabelle 1.
Randomizer
Die Reihenfolge der fallenden Tetrominos beeinflusst das Spielerlebnis und das Engagement im Spiel, und Tetris verwendet verschiedene Zufallsgeneratoren, um diese Reihenfolge festzulegen. Hier sind vier gängige Randomizer-Algorithmen:
Blackjack ist eine Sprache zur Spezifikation von Randomizern. Ziel ist es, sowohl für Menschen lesbar als auch von Computern interpretierbar zu sein. Blackjack ermöglicht die Definition von Zufallsgeneratoren mit unterschiedlichen Algorithmen und speichert dabei oft den Verlauf der letzten Tetrominos, um Wiederholungen zu vermeiden.
Dieser Algorithmus wird in den offiziellen Tetris-Richtlinienstandard-Spielen verwendet. Es wird ein Beutel mit allen sieben Tetrominos (I, J, L, O, S, T, Z) gemischt, und sie werden nacheinander ausgegeben. Sobald der Beutel leer ist, wird ein neuer erstellt. Dieser Ansatz reduziert die Wahrscheinlichkeit von langen Dürreperioden ohne eine bestimmte Figur.
Besonderheiten
- Höchstens 12 Figuren zwischen zwei I-Tetrominos.
- Maximal vier aufeinanderfolgende S- oder Z-Tetrominos.
Sega's Randomizer generiert beim Spielstart eine Sequenz von 1000 Tetrominos basierend auf einem Startwert (Seed), der aus dem NVRAM geladen wird. Ein festgelegter Startwert sorgt für wiederholbare Sequenzen beim Einschalten.
Die TGM-Serie verwendet einen Algorithmus, der gleiche aufeinanderfolgende Tetrominos minimiert. Dies passiert durch die Speicherung der letzten vier ausgegebenen Tetrominos,um neue zufällige Figuren zu wählen, die nicht in diesem Verlauf vorkommen. Wenn alle Versuche fehlschlagen, wird dennoch eine der jüngsten Tetrominos ausgegeben.
Besonderheiten
- Der Algorithmus verhindert, dass S-, Z- oder O-Tetrominos als erste Figur ausgegeben werden.
- TGM3 verwendet eine modifizierte Version mit einem Beutel von 35 Tetrominos, um sowohl "Fluten" als auch "Dürreperioden" zu vermeiden.
¶ Komplexität
Gegeben ein initiales Spielfeld und eine bekannte Sequenz von Tetrominos, wird durch die Reduktion gezeigt, dass Tetris NP-Hard ist.[12]
¶ Reduktion
Es lässt sich zeigen, dass jede Instanz des 3-Partition-Problems in polynomialer Zeit in eine entsprechende Tetris-Instanz transformiert werden kann. Damit wird bewiesen, dass die Komplexität von Tetris der von 3-Partition entspricht und somit NP-Hard ist.[13]
¶ Tetris problem
Gegeben
Ein initiales Spielfeld und eine endliche Sequenz von Tetrominos.
Frage
Können die Tetrominos, in der vorgegebenen Reihenfolge, so platziert werden, dass das Spielfeld mit diesen Steinen vollständig geleert wird, wobei das letzte Stück der Sequenz die finale Lücke füllt?
¶ 3-Partition problem
Gegeben
sei eine Sequenz von positiven Ganzzahlen und eine positive Ganzzahl , wobei gilt:Frage
Kann in disjunkte Teilmengen aufgeteilt werden, sodass für alle gilt:Das Problem bleibt NP-vollständig, selbst wenn die Zahlen in der Eingabeinstanz im Unärsystem dargestellt werden. Das bedeutet, dass 3-Partition in starkem Sinne NP-vollständig ist (stark NP-vollständig).[14]
¶ Initiales Tetris-Spielfeld
Das anfängliche Tetris-Spielfeld, das in der Reduktion verwendet wird, hat folgende Eigenschaften:
Abmessungen:
- Es wird angenommen, dass der obere Bereich des Spielfelds während des gesamten Spiels immer ausreichend groß ist, um Tetriminos in beliebigen Positionen und Richtungen zu platzieren.
- Die Breite des Spielfelds ist definiert als .
- Die Höhe des unteren Spielfeldteils, der abgeräumt werden muss, ist definiert als .
Dieses Spielfeld ist in polynomialer Zeit konstruierbar und hat die folgende Struktur:
- Leere Spalten als „Bucket“ genannt (Jedes „Bucket“ hat genau „Notches“ an seiner rechten Seite), und jedes „Bucket“ repräsentiert eine Teilmenge im 3-Partition-Problem, wobei es „Buckets“ gibt, entsprechend den Teilmengen.
- Der rechteckige Bereich rechts ist der „Fill-Area“.
- Der kleine T-förmige Bereich oben rechts ist das „Lock“, das dafür sorgt, dass keine der Reihen des Spielfelds gelöscht wird, bevor das „Lock“ selbst gefüllt ist.
- Die „Notches in Buckets“ stellen sicher, dass es nur eine Möglichkeit gibt, die „Buckets“ korrekt zu füllen.
¶ Tetrominos Sequenz
Die Sequenz der Tetrominos wird aus einer Instanz des 3-Partition-Problems in folgenden Schritten konstruiert:
-
Für jedes :
Die Sequenz besteht aus „Anfang“(
) und dann -mal „Mittel“: ( 
, 
, ), danach einmal „End“ ( , 
)
-
Alle Buckets komplett füllen:
-mal:
-
Freischalten des T-förmigen „Locks“:
einmal
-
Lösche des gesamten Spielfelds durch Füllen des „Fill-Area“:
-mal:
¶ Beweis[12:1]
¶ Ja-Instanz: ()
- Um einen Wert in einen „Bucket“ einzufügen, wird er entsprechend der Sequenz verarbeitet:
- Ein „Anfang“-Teil wird eingefügt,
- Ein „Mittel“-Teil repräsentiert den Wert ,
- Ein „End“-Teil schließt den Vorgang ab.
Mehrere Werte können auf diese Weise in denselben Bucket eingefügt werden, da die Form des Buckets nach jedem Einfügen gleich bleibt.
Höhe eines Buckets
Achtung: es gibt eine Überlappung zwischen „Anfang“ und „End“, die bereits in der Höhe des „Anfangs“ berücksichtigt ist.
Da für eine „Ja“-Instanz gilt:
ergibt sich die Höhe eines Buckets zu:
Der letzte „End“-Teil ragt jedoch zwei Einheiten über den Bucket hinaus, weshalb die endgültige benötigte Höhe beträgt. Da , ist die Höhe des Buckets ausreichend.
-
Nachdem alle Buckets gefüllt wurden, wird die verbleibende Struktur mithilfe der Teilmengenfüller vollständig aufgefüllt.
-
Nun sind nur noch der „Lock“-Bereich und die „Fill-Area“ übrig:
- Der „Lock“-Stein wird in den vorgesehenen Bereich (oben rechts) eingefügt, wodurch die obersten zwei Reihen geleert werden.
- Die verbleibende -"Fill-Area" wird mit geraden Tetris-Steinen horizontal gestapelt, sodass das gesamte Spielbrett geleert wird.
¶ Nein-Instanz: ()
-
Wenn ein Tetromino oberhalb der untersten Linien platziert wird, kann das Spielfeld nicht geleert werden.
- Beweis: Es müssten mehr als Linien abgeräumt werden, was unmöglich ist.
-
Nur der „Lock“ T-Tetrimino darf in den „Lock“ platziert werden.
- Beweis: Kein anderer Tetrimino passt vollständig in den „Lock“-Bereich.
-
Wenn ein Tetromino vor dem „Lock“-Stein Räume in einem Bucket einen unereichbaren Platz verursacht, kann das Spielfeld nicht geleert werden.
- Beweis: Solche Räume erzeugen unerreichbare Volumen, und deswege expandiert das Instanz oberhalb von Linien.
-
Wenn ein Teil eines Werts in einen anderen Bucket als seinen Anfangs-Bucket platziert wird, kann das Spielfeld nicht geleert werden.
- Beweis: Dies führt zu unerreichbaren Räumen in allen anderen Buckets.
-
Ein Wert muss exakt in einen Bucket eingesetzt werden.
- Beweis: Alle anderen Möglichkeiten erzeugen unerreichbare Räume.
-
Ein Bucket muss genau drei Werte enthalten, und die Summe dieser Werte muss exakt betragen, damit das Spielfeld geleert werden kann.
- Beweis: und , da andere Kombinationen unmöglich sind.
Die vorgeschlagene Reduktion führt dazu, dass eine „Nein“-Instanz des 3-Partition-Problems zu einer Tetris-Instanz wird, deren Spielfeld nicht geleert werden kann.
- Beweis: Um das Spielfeld zu leeren, müssen die ss „Buckets“ genau drei Werte enthalten (Punkt 6), und die Summe aller „Werte“ in einem „Bucket“ muss genau betragen (punkt 6). Dies ist nur möglich, wenn eine „Ja“-Instanz ist. Daher kann das Spielfeld nicht geleert werden, wenn eine „Nein“-Instanz ist.
¶ Lösungsansätze
Tetris ist NP-Hard, weshalb es keine deterministische Lösung dafür gibt. Es ist auch schwierig, das Problem zu approximieren.[13:1] Allerdings bieten metaheuristische Methoden wie Evolutionäre Algorithmen einen Lösungsansatz, der erfolgreich eine gute Anzahl von Reihen löschen konnte.[15]
¶ Bewertungsfunktionen:[15:1]
Um den besten Tetris-Zug zu finden, wird für jedes mögliche Spielfeld , das mit den zwei bekannten Tetrominos erreicht werden kann, eine Bewertung berechnet (2-Ebenen-Suche). Der Zug, der zum besten Spielfeld führt, wird gewählt. Dafür braucht man eine gute Bewertungsfunktion.
Eine Bewertungsfunktion würde auch zukünftige Tetrominos berücksichtigen. Da die Berechnung des perfekten Zugs selbst bei bekannten zukünftigen Tetrominos NP-Hard ist, nutzen wir eine Heuristik, um effizient zu berechnen.
besteht aus einigen einfachen Funktionen , die das Spielfeld nach bestimmten Kriterien bewerten:
-
Stapelhöhe: Höhe der höchstgelegenen besetzten Zelle.
-
Löcher: Anzahl der leeren Zellen mit mindestens einer besetzten Zelle darüber.
-
Verbundene Löcher: Wie "Löcher", aber vertikal verbundene unbelegte Löcher zählen nur als eins.
-
Gelöschte Linien: Anzahl der Linien, die im letzten Zug entfernt wurden.
-
Höhenunterschied: Differenz zwischen der höchsten besetzten und der niedrigsten freien Zelle, die von oben erreichbar ist.
-
Tiefe von Brunnen: Tiefe der Lücken, die von benachbarten besetzten Spalten umgeben sind.
-
Summe aller Brunnen: Gesamttiefe aller Brunnen auf dem Brett.
-
Landehöhe: Höhe, auf der das zuletzt platzierte Tetromino gelandet ist.
-
Blockanzahl: Anzahl der besetzten Zellen auf dem Brett.
-
Gewichtete Blockanzahl: Wie "Blockanzahl", aber Zellen in höheren Reihen zählen mehr.
-
Vertikale Übergänge: Wechsel zwischen besetzten und unbesetzten Zellen in Spalten.
-
Horizontale Übergänge: Wechsel zwischen besetzten und unbesetzten Zellen in Reihen.
¶ 1. linear rating-function:
(Skalarprodukt)
¶ 2. exponential rating-function:
¶ 3. exponential rating-function with displacement:
Die Gewichte der Bewertungsfunktionen werden mittels evolutionärer Algorithmen optimiert:
Genotyp: Besteht aus den Gewichten, Exponenten und optionalen Verschiebungswerten der Kriterien.
Fitness: Gemessen anhand der durchschnittlichen Anzahl gelöschter Linien in mehreren Spielen.
Reproduktion: Erfolgt durch Selektion, Kreuzung und Mutation. Eliten-Selektion sorgt dafür, dass die besten Individuen erhalten bleiben.
Ergebnisse:[15:2]
1.Lineare Bewertungsfunktion () mit Kriterien 1- 6 auf 10x20 Brett:
- Beste Leistung: 859.520 gelöschte Reihen.
- Durchschnitt (Top-Individuen, 5 Spiele): 170.000 gelöschte Reihen.
- Populationsgröße: 100.
- Läufe wurden meist nach 20–30 Generationen beendet.
2.Lineare Bewertungsfunktion () auf 6x12 Brett (Beispiel in Abb. 6 links)
- Kürzere Spiele ermöglichen mehr Generationen.
- Beste Leistung: 24.311 gelöschte Reihen.
- Durchschnitt (12 Läufe): 4007 gelöschte Reihen.
3.Exponentielle Bewertungsfunktion () auf 10x20 Brett (Abb. 6 rechts)
- Nur ein Lauf durchgeführt (30 Generationen in 3 Monaten).
- Beste Leistung: 5.498.703 gelöschte Reihen.
- Durchschnitt: 1.359.184 gelöschte Reihen.
¶ Schlussfolgerung
-
Exponentielle Bewertungsfunktion () erzielte deutlich höhere Ergebnisse als die lineare Bewertungsfunktion () auf dem 6x12-Spielbrett:
-
Es gibtt dominante Kriterien:
- Stapelhöhe (1)
- Löcher (2)
- Verbundene Löcher (3)
- Tiefe von Brunnen (6)
Diese Kriterien dominieren die Bewertung des Spielbretts und stimmen mit den menschlichen Spielerbeobachtungen überein, dass das Vermeiden von Löchern und das Halten des Haufens niedrig vorteilhaft ist.
¶ Referenzen
¶ Abbildungsverzeichnis
Abb. 1: Laroche, Simon. Tetris collection. TetrisWiki, URL.
Abb. 4: Article Super Rotation System. (2025, Jan. 16). In Tetris-Wiki. URL
Abb. 5: Breukelaar, Ron, Hendrik Jan Hoogeboom, and Walter A. Kosters. "Tetris is Hard, Made Easy." Leiden Institute of Advanced Computer Science, Universiteit Leiden, 2003. URL
Abb. 6: Bohm, Niko, Gabriella Kokai, and Stefan Mandl. “An Evolutionary Approach to Tetris.” 2005. URL
Abb. 2, 3, 4 und 5: mit TetVis erstellt. GitHub
¶ Literaturverzeichnis
IGN. "All-time Best-selling Console Games Based on Global Unit Sales as of October 2023 (in Million Units)." Statista, Statista Inc., 16 Oct 2023. URL ↩︎
Golomb, Solomon W. (1994). Polyominoes (2nd ed.). Princeton, New Jersey: Princeton University Press. ISBN 0-691-02444-8. URL ↩︎
Article Playfield. (2025, Jan. 16). In Tetris-Wiki. URL ↩︎ ↩︎
Hoogeboom, Hendrik Jan, and Walter A. Kosters. "The theory of tetris." Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica 9 (2005): 14-21. URL ↩︎ ↩︎
Article Super Rotation System. (2025, Jan. 16). In Tetris-Wiki. URL ↩︎
Article Random Generator. (2025, Jan. 18). In Tetris-Wiki. URL ↩︎
Article Sega Randomizer. (2025, Jan. 18). In Tetris-Wiki. URL ↩︎
Article TGM randomizer. (2025, Jan. 18). In Tetris-Wiki. URL ↩︎
Breukelaar, Breukelaar, Ron, Hendrik Jan Hoogeboom, and Walter A. Kosters. "Tetris is hard, made easy." Leiden Institute of Advanced Computer Science, Universiteit Leiden (2003). URL ↩︎ ↩︎
E.D. Demaine, S. Hohenberger and D. Liben-Nowell, Tetris is Hard, Even to Approximate, Technical Report MIT-LCS-TR-865 (to appear in COCOON 2003), Laboratory of Computer Science, Massachusetts Institute of Technology, 2002. URL ↩︎ ↩︎
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, 1979. URL ↩︎
Bohm, Niko, Gabriella Kokai, and Stefan Mandl. “An Evolutionary Approach to Tetris,” 2005. URL ↩︎ ↩︎ ↩︎