¶ Einführung
Der Tengen-Tetris-Konflikt
Wegen eines verlorenen Rechtsstreits gegen Nintendo musste Atari 1989 hunderttausende Exemplare seiner inoffiziellen Tengen-Version vernichten lassen. Die wenigen überlebenden Kopien gelten heute als wertvolle Sammlerstücke.
¶ Spielregeln
¶ Spielbrett
Das Spielgeschehen findet auf einem rechteckigen Spielfeld statt, auch Matrix oder Well genannt. Die Standardgröße beträgt 10 Blöcke in der Breite und 20 Blöcke in der Höhe.
Über dem sichtbaren Bereich existieren oft noch verdeckte Reihen (die „Skyline“), in denen die Steine generiert werden. Das Spiel endet, wenn sich die Steine so hoch stapeln, dass ein neu erscheinendes Tetromino keinen Platz mehr hat oder wenn ein Stein über den oberen Rand der sichtbaren Matrix hinausragt.
¶ Tetromino
Die Spielsteine werden als Tetrominos bezeichnet. Jedes Tetromino ist ein Polyomino, das aus exakt vier quadratischen Blöcken besteht. Es gibt sieben verschiedene geometrische Formen, die meist mit Buchstaben assoziiert werden, denen sie ähneln.
In modernen Varianten (nach der Tetris Guideline) hat jedes Teil eine feste Farbe:
- I-Block: Hellblau (Cyan)
- O-Block: Gelb
- T-Block: Lila (Magenta)
- S-Block: Grün
- Z-Block: Rot
- J-Block: Blau
- L-Block: Orange
Die Steine fallen zufällig vom oberen Rand herab. Der Spieler kann sie horizontal verschieben und in 90-Grad-Schritten rotieren. Zusätzlich gibt es meist die Möglichkeit den Fall zu beschleunigen.
¶ Score
Das Ziel ist es, die Steine so zu platzieren, dass lückenlose horizontale Reihen entstehen. Sobald eine Reihe komplett gefüllt ist, wird sie vom Spielfeld entfernt, und die darüberliegenden Steine rutschen nach unten.
Die Punktzahl hängt davon ab, wie viele Reihen gleichzeitig aufgelöst werden. Dieses Ereignis nennt man einen Line Clear. Die Punkte verteilen sich (nach dem Standard-Nintendo-Scoring) wie folgt:
| Bezeichnung | Reihen | Punkte |
|---|---|---|
| Single | 1 | 100 x Level |
| Double | 2 | 300 x Level |
| Triple | 3 | 500 x Level |
| Tetris | 4 | 800 x Level |
Ein „Tetris“ (vier Reihen gleichzeitig) kann nur mit dem länglichen I-Block erzielt werden. Zusätzlich steigt mit der Anzahl der aufgelösten Reihen oft das Level, wodurch sich die Fallgeschwindigkeit der Steine permanent erhöht.
¶ Strategien
Die Entwicklung von Lösungsstrategien von Tetris ist ein bekanntes Problem in der Informatik. Da das Spiel aufgrund der zufälligen Steinfolge und der enormen Anzahl möglicher Zustände (ca. ) nicht vollständig vorausberechenbar ist, scheitern Brute-Force-Methoden. Es wurde sogar mathematisch bewiesen, dass das optimale Spielen von Tetris (selbst wenn man die kommenden Steine kennen würde) ein NP-vollständiges Problem[1] ist. Daher greifen algorithmische Ansätze auf Näherungsverfahren und Lernalgorithmen zurück.
¶ Strategie mit Genetischen Algorithmen
Exkurs: Grundlagen Genetischer Algorithmen
Genetische Algorithmen (GA) sind eine Klasse von stochastischen Optimierungsverfahren, die von den Prinzipien der biologischen Evolution und der natürlichen Selektion inspiriert sind. Sie eignen sich besonders gut für komplexe Suchräume, in denen klassische Verfahren scheitern, weil der Zusammenhang zwischen den Parametern und der Qualität der Lösung nicht linear oder schwer verständlich ist.
¶ 1. Zentrale Begriffe
Population
Die Menge aller aktuell betrachteten Lösungsansätze wird als Population bezeichnet. Im Gegensatz zu Verfahren, die nur eine einzige Lösung iterativ verbessern, arbeitet der GA mit vielen Kandidaten gleichzeitig. Dies verringert die Gefahr, in lokalen Optima stecken zu bleiben.
Individuum (Kandidat)
Ein einzelnes Element der Population. Im Kontext von Optimierungsproblemen stellt jedes Individuum eine vollständige, potenzielle Lösung für das Problem dar.
- Der Genotyp ist die genetische Repräsentation der Lösung im Computer. Meist handelt es sich um eine Zeichenkette (String), einen Bitvektor (
01011...) oder um einen Vektor von Zahlen, wie auch der Fall ist in der Tetris-Anwendung. - Der Phänotyp ist die ausgeprägte Eigenschaft des Individuums, also wie es sich in der Umwelt verhält. Der GA manipuliert den Genotyp, bewertet aber den Phänotyp.
Chromosom
Der Datenträger des Genotyps. Bei komplexen Problemen kann ein Individuum aus mehreren Chromosomen bestehen, oft wird der Begriff jedoch synonym für den gesamten Parametervektor eines Individuums verwendet.
Gen
Die kleinste, atomare Einheit auf einem Chromosom. Ein Gen kodiert einen einzelnen Parameter der Lösung. Durch die Veränderung eines Gens ändern sich die Eigenschaften des Phänotyps.
Fitness
Ein Maß dafür, wie gut sich ein Phänotyp in seiner "Umwelt" schlägt. Die Fitnessfunktion weist jedem Individuum einen numerischen Wert zu. Dieser Wert bestimmt die Wahrscheinlichkeit, mit der das Individuum seine Gene an die nächste Generation weitergeben darf ("Survival of the Fittest").
¶ Algorithmische Bestandteile
-
Selection (Selektion):
Dieser Schritt bestimmt, welche Individuen (Gewichtungsvektoren) ihre Erbinformationen an die nächste Generation weitergeben dürfen. Das Prinzip ist stochastisch, aber nimmt auch die Leistungen der Individuen in Betracht: Je höher die Fitness (z. B. Score oder gelöschte Reihen), desto höher ist die Wahrscheinlichkeit der Fortpflanzung. -
Gängige Methoden:
- Roulette-Wheel-Selection: Die Wahrscheinlichkeit ist direkt proportional zur relativen Fitness.
- Turnier-Selektion: Eine kleine Gruppe wird aus der Population zufällig gewählt, und nur der Beste dieser Gruppe darf sich paaren. Dies verhindert, dass ein einzelnes "Super-Individuum" sofort die gesamte Population dominiert.
- Elitismus: Die besten Individuen der Population werden unverändert direkt in die nächste Generation übernommen, um die bisher beste Leistung zu sichern.
-
Crossover (Rekombination):
Hier werden die Eigenschaften zweier Eltern-Individuen vermischt, um neue Lösungen zu erzeugen. Da die Chromosomen in dieser Anwendung aus Vektoren reeller Zahlen (Gewichte , Exponenten ) bestehen, unterscheidet sich dies von binären Algorithmen:- Methoden:
- Arithmetischer Crossover: Das Kind entsteht durch den gewichteten Mittelwert der Elternwerte ().
- Uniform Crossover: Für jedes Gen wird per Münzwurf entschieden, ob er von Vater oder Mutter geerbt wird.
- Methoden:
-
Mutation:
Dient dazu, die genetische Vielfalt zu erhalten und zu verhindern, dass der Algorithmus in einem lokalen Optimum ("Sackgasse") stecken bleibt. Mit einer sehr geringen Wahrscheinlichkeit (z. B. ) wird ein Gen im Genotyp zufällig verändert.
Betrachtet man Tetris als ein mathematisches Optimierungsproblem, lassen sich verschiedene Methoden anwenden, um computergesteuerte Spieler zu generieren, die das Spiel effizient beherrschen. Ein Ansatz, der häufig als Forschungsgegenstand dient, ist der Einsatz Genetischer Algorithmen, welche den Prozess der natürlichen Evolution simulieren.
Wie andere Optimierungsverfahren versuchen auch genetische Algorithmen, Eingabewerte in einem Suchraum zu finden, die das Ergebnis einer Funktion maximieren/minimieren. Diese Funktion wird als Fitnessfunktion bezeichnet und dient dazu, die Qualität eines Kandidaten zu bewerten.
Der Algorithmus verwaltet hierfür eine Population von Kandidaten, wobei die Größe von typischerweise zwischen Hunderten und Tausenden von Individuen variiert.
In diesem Fall sind die einzelnen Kandidaten Bewertungsfunktionen (Heuristiken), welche die optimale Position und die Rotation der Platzierung eines Spielsteins berechnen.
¶ Funktionsweise der Heuristik
Vom genetischen Algorithmus wird daher eine Bewertungsfunktion erstellt, nicht der Einzelzug geführt. Die Fitness kann somit definiert werden, entweder als die Anzahl der entfernten Zeilen oder als der Gesamtscore bis zum Ende des Spieles. Diese Werte sind im allgemeinen proportional.
Die Heuristik bestimmt anhand mehrerer Kriterien, welches der möglichen Spielbretter als das beste zu bewerten ist. Hierbei wird ein Look-ahead von zwei Tetrominos verwendet, sodass nicht nur der aktuelle, sondern auch der potenziell folgende Spielzug in die Bewertung mit reinbetrachtet wird. Das heißt, von einem festen Zeitpunkt aus werden alle möglichen Spielbretter ausgewertet, die man nach dem Platzieren des jetzigen Tetrominos und des nächsten erreichen kann, und der Zustand mit dem besten Score wird ausgewählt.
¶ Kriterien einer guten Heuristik
Es gibt mehrere Faktoren, die man in Betracht nehmen kann, welche die Bewertungsfunktion beeinflussen können. Eine Möglichkeit, betrachtet im Artikel von Böhm, Kokai und Mandl [2] wäre die folgende:
Stapelhöhe (Pile Height):
Die Zeilennummer der höchsten belegten Zelle auf dem Spielfeld.Löcher (Holes):
Die Anzahl aller leeren Zellen, die mindestens eine belegte Zelle über sich haben (d. h. sie sind "begraben").Verbundene Löcher (Connected Holes):
Ähnlich wie Kriterium zwei, jedoch zählen vertikal direkt miteinander verbundene leere Zellen zusammen nur als ein einziges Loch.Entfernte Reihen (Removed Lines):
Die Anzahl der Reihen, die durch den letzten Zug aufgelöst wurden, um den aktuellen Zustand zu erreichen.Höhendifferenz (Altitude Difference):
Die Differenz zwischen der höchsten belegten und der niedrigsten freien Zelle, die direkt von oben erreichbar ist.Maximale Schachttiefe (Maximum Well Depth):
Die Tiefe des tiefsten Schachts (mit einer Breite von einem Block) auf dem Spielfeld.Summe aller Schächte (Sum of all Wells):
Die aufsummierte Tiefe aller Schächte auf dem Spielfeld.Landehöhe (Landing Height):
Die Höhe (Zeilennummer), auf der das letzte Tetromino platziert wurde.Gewichtete Blöcke (Weighted Blocks):
Ähnlich wie Blöcke, jedoch werden die Zellen abhängig von ihrer Höhe gewichtet: Ein Block in Reihe zählt -mal so viel wie ein Block in Reihe 1 (wobei von unten nach oben gezählt wird).Zeilenübergänge (Row Transitions):
Die Summe aller horizontalen Übergänge von einer belegten zu einer leeren Zelle (und umgekehrt) auf dem Spielfeld. Die Ränder links und rechts des Spielfelds gelten dabei als belegt. (Ein niedriges Ergebnis bedeutet, dass die Zeilen gut gefüllt sind).Spaltenübergänge (Column Transitions):
Analog zu den Zeilenübergängen, jedoch werden hier die vertikalen Übergänge gezählt. Der > Boden unterhalb des Spielfelds wird als belegt betrachtet.
Jedes dieser Kriterien kann als eine einzelne Funktion betrachtet werden, sodass die Bewertungsfunktion aus deren Kombination erstellt wird.
-
Lineare Bewertungsfunktion (Skalarprodukt):
Hierbei wird jedes Kriterium mit einem Gewicht multipliziert und aufsummiert: -
Exponentielle Bewertungsfunktion:
Zusätzlich zur Gewichtung wird das Kriterium mit einem Exponenten versehen, um nicht-lineare Zusammenhänge abzubilden: -
Exponentielle Bewertungsfunktion mit Verschiebung (Displacement):
Hier wird zusätzlich eine Zielgröße (Displacement) eingeführt, von der das Kriterium abweichen darf:
Das Genotyp wird daher bei jeder Bewertungsfunktion aus drei Vektoren (Chromosomen) bestehen, die auf der i-ten Position jeweils die drei Faktoren enthalten und im Laufe der Simulation optimiert werden.
¶ Simulation
Die Population hat anfangs 30 Individuen, mit zufälligen Genen .
Der Prozess beginnt mit der Initialisierung einer Startpopulation von 30 Individuen, die jeweils über zufällig generierte Gene verfügen. Zur Evaluierung der Leistungsfähigkeit (Fitness) wird parallel eine definierte Anzahl an Spielen für jedes Individuum simuliert. Dieser Vorgang wird in jeder neuen Generation wiederholt, um die besten Strategien zu selektieren.
Die Simulation auf 30 Generationen der exponentialen Funktion auf dem standard Feld (10x20) hat in der Studie von ,Böhm, Kokai und Mandl[3] Monate gedauert und wurde daher nur ein Mal simuliert.
¶ Ergebnisse
In fast jeder durchgeführten Simulation stagnierte der Leistungszuwachs (die Lernkurve) deutlich zwischen der 20. und 30. Generation. Nachdem die anfänglichen, schnellen Verbesserungen erreicht waren, blieben die Leistungen höherer Generationen marginal konstant. (siehe Abb. _)
Abbildung 3 veranschaulicht den Verlauf der Evolution in der Arbeit von Böhm, Kókai und Mandl [3:1], während Abbildung 4 die Fitness-Entwicklung bei Jason Lewis [4] darstellt.
¶ Analyse der Gewichtungen
Die Kriterien, die sich im Laufe der Optimierung als am wichtigsten herausstellten sind ähnlich zu den typischen Strategien menschlicher Spieler [5]. Somit waren die Kriterien mit höchster Gewichtung:
- Stapelhöhe
- Löcher
- Verbundene Löcher
- Maximale Schachttiefe
Interessanterweise tendierten Gewichte mehrerer Kriterien gegen 0. Dies könnte daran liegen, dass manche Kriterien redundante Informationen liefern.
¶ Analyse der Funktionen
Die Wahl der Bewertungsfunktion hatte einen massiven Einfluss auf die erreichte Spielstärke, somit lag der Schnitt der entfernten Linien bei circa 170.000 und das Rekordspiel bei 859.520, wobei bei der Exponentialfunktion der Schnitt bei über 1.3 Millionen Reihen lag und das beste Einzelspiel erst nach 5.498.703 entfernten Reihen endete.
¶ Kann man "gewinnen?"
Unter „Gewinnen“ wird hierbei das Finden einer Strategie verstanden, die es erlaubt, zeitlich unbegrenzt zu spielen, unabhängig davon, welche Spielsteine folgen. In diesem Sinne lautet die Antwort nein. Brzustowski zeigte, dass ein Spieler zwangsläufig verlieren muss, sofern der „Gegner“ – in diesem Fall der Zufallsgenerator der Tetrominos – Kenntnis von den vom Spieler gewählten Positionen hat und daraufhin gezielt die ungünstigsten möglichen Spielsteine bereitstellt[6].
Darauf aufbauend hat Heidi Burgiel bewiesen, dass es Spielstein Sequenzen gibt, so dass ein Verlust unvermeidbar ist, selbst wenn der Computer diese Information nicht hat. [2:1]
In diesem Abschnitt wird eine von der üblichen Namenskonvention abweichende Bezeichnung der Tetrominos verwendet. Insbesondere werden die Z-Tetrominos nicht als S und Z, sondern als links- bzw. rechtsorientierte Z-Tetrominos unterschieden.
Abb. 5: Links orientiertes Tetromino
Abb. 6: Rechts orientiertes Tetromino
Um dies zu demonstrieren, betrachtet man ein vereinfachtes Szenario, in dem ausschließlich Z-Tetrominos (in alternierender Orientierung) vorkommen. Hierbei spielt die Drehung eine Rolle:
- Ein horizontales Z-Tetromino belegt Zellen in drei Spalten.
- Ein vertikales Z-Tetromino belegt Zellen in nur zwei Spalten.
Dazu wurde als erstes folgendes Hilfs- Lemma aufgestellt, das als Basis für den Beweis der Unlösbarkeit (Theorem 1) dient:
¶ Lemma
In einem Tetris-Spiel, in dem dem Spieler ausschließlich Z-Tetrominos präsentiert werden, können maximal 120 Z-Tetrominos platziert werden, die entweder:
- horizontal liegen (in einer beliebigen Spalte), oder
- vertikal so platziert sind, dass ihre linke Zelle in einer geradzahligen Spalte liegt,
ohne dass das Spiel verloren geht.
¶ Beweis:
Die Spalten des Tetris Spielfeldes werden von 1 bis 10 nummeriert. Folgende Variablen werden definiert:
- : Die gesamtzahl an Blöcken (einzelnen, besetzten Zellen), die im Laufe des Spieles platziert worden sind.
- : Die Gesamtanzahl der horizontalen Z-Tetrominos, die im Laufe des Spiels mit ihrem Zentrum in Spalte landeten (sie belegten also Spalten ).
- : Die Gesamtanzahl der vertikalen Z-Tetrominos, die im Laufe des Spiels in den Spalten und platziert wurden. (Der Linke Block liegt somit in Spalte )
Die Gesamtanzahl der einzelnen Blöcke (Zellen), die jemals in der Spalte platziert worden sind, lässt sich folgendermaßen durch die Summe der umliegenden Steine darstellen:
Sei nun die Anzahl an aktuell platzierten Steine in Spalte . Wenn eine Reihe gelöscht wird, so verringert sich die Höhe aller Spalten gleichermaßen. Das bedeutet, dass die Differenz zwischen zwei Spaltenhöhen () nach der Löschung einer Reihe gleich bleibt und daher auch die Differenz der Gesamtzahl an platzierten Blöcken sich mit dem Löschen einer Reihe nicht ändert, somit zu dem Zeitpunkt gilt: .
Da das Spiel verloren ist, sobald eine Spalte die Höhe 20 überschreitet, muss die Höhendifferenz zwischen zwei beliebigen Spalten stets kleiner oder gleich 20 sein (solange das Spiel läuft). Daraus folgt:
Da Steine nicht die Grenzen des Spielfeldes überschreiten können, wissen wir, dass es keine horizontalen Steine geben kann mit dem Zentrum auf einer Randspalte:
().
Betrachten wir nun die Differenz zwischen benachbarten Spalten, zum Beispiel Spalte 2 und 1:
Analog gilt dies für das andere Ende des Spielfelds (Spalte 8 und 9):
Allgemein gilt für die Differenz benachbarter Spalten:
Daraus folgt durch Umstellung der Ungleichung:
Setzt man nun in die Gleichung ein, so erhält man, aus (1)
Mit dem gleichen Ansatz, nun vom rechten Rand ausgehend, betrachtet man die Differenz zwischen Spalte 9 und 10. Da auch hier die Höhendifferenz nicht größer als 20 sein darf, gilt:
Setzt man hier die Definitionen für ein (und beachtet, dass am Rand gilt), erhält man die Ungleichung:
Führt man diese Berechnung weiter in Richtung der Spielfeldmitte fort (analog zum Schritt, der links zu führte), ergibt sich für den Index :
Daraus kann man schließen, dass
und implizit, da die Anzahl an Steinen positiv ist:
Das bedeutet dass man zwingend nicht unendlich viele dieser spezifischen Z-Stein-Platzierungen vornehmen kann. Sobald die Summe 120 überschreitet, muss die Höhendifferenz auf dem Brett so groß geworden sein, dass das Spielfeld keinen Platz mehr bietet (innerhalb der Höhe 20) und daher das Spiel endet.
Basierend auf dem bewiesenen Lemma lässt sich nun das folgende Theorem zeigen:
¶ Theorem 1
Ein Tetris-Spiel, das ausschließlich aus Z-Tetrominos in alternierender Orientierungen besteht, wird zwangsläufig enden, bevor 70.000 Tetrominos gespielt wurden.
¶ Beweis:
Der Beweis von Burgiel wird in 4 Hauptteile aufgeteilt:
¶ 1. Die Bildung isolierter Spuren (Lanes)
Da das Lemma gezeigt hat, dass horizontale Platzierungen oder vertikale Platzierungen (mit dem linksseitigen Block in geraden Spalten) stark limitiert sind (max. 120 Stück), ist der Spieler gezwungen, fast ausschließlich vertikal (in festen Bahnen) zu spielen (Siehe Abb 4).
Abb. 7: Bahn linksorientierter Tetrominos
Der Spieler ist nicht strikt an die Bahnen gebunden, doch jede Abweichung verbraucht eines der limitierten 120 Züge aus dem Lemma. Was geschieht wenn ein rechts- orientierter Stein auf einer links-orientierten Bahn platziert wird, und umgekehrt wird im folgenden noch besprochen.
Das 10 Spalten breite Spielfeld zerfällt effektiv in 5 isolierte, vertikale Spuren, die jeweils zwei Spalten breit sind. Horizontale Verbindungen werden anfangs als "verboten" betrachtet (gemäß Lemma darf man nur endlich viele platzieren).
¶ 2. Das Paritäts-Problem (3 gegen 2)
Betrachtet man die obersten Steine in diesen 5 Spuren, so hat jeder eine Orientierung (Links-Z oder Rechts-Z).
Da 5 eine ungerade Zahl ist, kann es nicht gleich viele Spueren geben die Links-orientiert sind, wie Rechts-orientiert sind. Es muss zwangsläufig eine Mehrheit geben.
- Beispiel: 3 Spuren benötigen einen rechtsgerichteten Z-Stein, aber nur 2 Spuren benötigen einen linksgerichteten.
Ohne Beschränkung der Allgemeinheit wird im Beweis angenommen, dass die Mehrheit der Spuren Rechts-orientiert ist.
¶ 3. Disproportionales Wachstum
Entscheidend ist, dass angenommen wird, dass die Orientierung der Steine alterniert.
- Der Zufallsgenerator liefert alternierend Steine (50% Links, 50% Rechts).
Die Konsequenz ist, dass die "Minderheiten-Spuren" (hier die Spuren für Links-Steine) überproportional schnell wachsen. Sie müssen die Hälfte aller ankommenden Steine aufnehmen, obwohl sie weniger als die Hälfte der Spuren ausmachen. Mathematisch lässt sich zeigen, dass spätestens alle 240 Steine eine dieser Spuren so hoch gewachsen ist, dass der Spieler verlieren würde, würde er weiterhin die "Spuren- Strategie" anwenden.
Sobald eine Spur den oberen Rand erreicht (oder kurz davor ist), muss der Spieler einen Stein der einen Orientierung in eine Spur der anderen Orientierung legen (z. B. ein Links-Z in eine Rechts-Spur), um nicht sofort zu verlieren.
Aufgrund der Zick-Zack-Form entsteht dabei unter dem Stein ein Hohlraum (Loch), der:
- Zwei Zellen hoch und eine Zelle breit ist.
- Von oben durch den neuen Stein wie mit einem Deckel abgekapselt ist.
- Von der Seite nicht gefüllt werden kann (wegen des Verbots horizontaler Züge).
Abb. 8: Entstehung eines abgekapselten Lochs
Da eine Tetris-Reihe nur dann entfernt wird, wenn sie lückenlos gefüllt ist, sorgt dieses einzelne unzugängliche Feld dafür, dass die betroffenen Reihen niemals aufgelöst werden können.
¶ 4. Endergebnis
Nun wird berechnet wie lange das Spiel unter diesen Bedingungen laufen kann:
- Physisches Limit: Auf dem Spielfeld können maximal ca. 50 solcher unlöschbaren Löcher existieren, bevor der Platz komplett ausgeht.
- Spezielle Spielsteine Limit: Das Lemma erlaubt uns 120 "Ausnahme-Züge". Im Beweis nimmt man an, jeder dieser Züge kann die Bildung von 2 Löchern verhindern oder kompensieren. Das entspricht einem Puffer von Löchern.
Insgesamt verkraftet das Spiel also maximal solcher Fehlerereignisse.
Da, wie in Punkt 3 gezeigt, spätestens alle 240 Steine ein solcher Fehler erzwungen wird, ergibt sich die maximale Anzahl an Zügen:
Damit ist bewiesen, dass spätestens nach 69.600 Steinen das Spiel zwangsläufig endet, unabhängig von der Spielstrategie des Spielers/des Algorithmus.
¶ Fazit und offene Fragen
Die Untersuchung hat gezeigt, dass Genetische Algorithmen eine extrem leistungsfähige Methode sind, um Strategien für Tetris zu entwickeln. Durch die evolutionäre Optimierung der Gewichtungen (wie Löcher, Stapelhöhe oder Höhendifferenz) lernt die KI selbstständig, menschliche Intuitionen zu quantifizieren: Sie erkennt, dass eine flache Oberfläche und das Vermeiden von Löchern essenziell für das fortsetzen des Spieles sind.
Jedoch bildet der mathematische Beweis rund um die alternierenden Z- und S-Tetrominos (siehe Abb. 7) eine harte theoretische Grenze. Er demonstriert, dass keine noch so perfekt optimierte Heuristik unendlich lange überleben kann, wenn die Sequenz der Spielsteine ungünstig genug ist.
Eine weitere mögliche Richtung der Forschung wäre zu prüfen wie man gegen einem Computer spielen kann, der gezielt die schlechtesten Steine wählt. Desweiteren kann man sich noch fragen welche Sequenzen es sonst noch geben kann und eine kleinere Obergrenze finden, gegen welche der Spieler gezwungen ist zu verlieren.
¶ Referenzen
¶ Abbildungsverzeichnis
Abb. 1: Cover von Tengen Tetris (St. Basil's Cathedral).
Quelle: Live Science, "The Strange History of Tetris".
Link
Abb. 2: Die Standard-Benennungskonvention der sieben Tetrominos.
Quelle: ResearchGate.
Link
Abb. 3: Verlauf der Fitness-Werte in der Evolution (Böhm, Kókai, Mandl).
Quelle: "Tetris by GAs", Universität Erlangen-Nürnberg.
Link
Abb. 4: Fitness-Verlauf und Lernkurve (Jason Lewis).
Quelle: Stanford CS229 Project Report.
Link
Abb. 5 & 6: Orientierung und Bahnen der Tetrominos.
Quelle: Arthur O'Dwyer, "Tetromino Names and Orientations".
Link
Abb. 7 & 8: Entstehung unlösbarer Löcher und Spielabbruch ("How to lose at Tetris").
Quelle: Heidi Burgiel, The Mathematical Gazette (Cambridge University Press).
Link
¶ Literatur
Demaine, Erik D., et al.: "Tetris is Hard, Even to Approximate". International Journal of Computational Geometry & Applications, 2003. PDF öffnen ↩︎
Böhm, Kókai, Mandl: "An Evolutionary Approach to Tetris". University of Erlangen-Nuremberg. PDF öffnen ↩︎ ↩︎
Burgiel, Heidi: "How to lose at Tetris". The Mathematical Gazette, Vol. 81, 1997. Abstract ansehen ↩︎ ↩︎
Jason Lewis: "Playing Tetris with Genetic Algorithms"., 2015. PDF öffnen ↩︎
Somnuk Phon-Amnuaisuk: Evolving and discovering Tetris gameplay strategies ↩︎
Brzustowski, John "Can you win at TETRIS?". UBC Theses and Dissertations, 1992. Link zur Bibliothek ↩︎