Der erste Teil (Code-Analyse) ist hier: https://habr.com/post/420725/ .

Algorithmus

Beschreibung

Der Algorithmus führt kontinuierlich die folgenden Schritte aus:

1. Er wartet, bis ein neues Tetrimino entsteht.
2. Überprüft den Typ des neu erstellten Tetriminos, den Typ des nächsten Tetriminos (Abbildung im Vorschaufeld) und den Inhalt des Spielfelds.
3. Untersucht alle möglichen Möglichkeiten, um dem Spielfeld zwei Tetriminos hinzuzufügen, und bewertet jede Wahrscheinlichkeit.
4. Verschiebt das neu erstellte Tetrimino so, dass es mit dem Ort der am besten erkannten Wahrscheinlichkeit übereinstimmt.

Jeder dieser Schritte wird nachstehend ausführlich beschrieben.

Suche sperren

Stellen Sie sich eine vereinfachte Version von Tetris vor, bei der die Formen nicht automatisch fallen. Die einzige Möglichkeit, die Figur zu senken, besteht darin, sie vorsichtig abzusenken. Nachdem wir das Timing aus dem Spiel entfernt haben, können wir den Zustand des aktiven Tetriminos anhand seiner Position und Ausrichtung vollständig beschreiben. Die Figur hat einen bekannten Ort der anfänglichen Erstellung, und die folgenden Operationen werden verwendet, um von einem Zustand in einen anderen zu konvertieren:

• Einen Schritt zurück
• Ein Schritt nach links
• Bewegen Sie sich einen Schritt nach rechts
• Drehen Sie einen Schritt gegen den Uhrzeigersinn
• Drehung im Uhrzeigersinn

Diese Operationen sind nur anwendbar, wenn die Quadrate des resultierenden Tetriminos leeren Zellen des Spielfelds entsprechen. Wenn es unmöglich ist, einen Schritt nach unten zu gehen, wird der Status als blockiert betrachtet. Da wir jedoch Tetris vereinfacht haben und das Warten auf das Sperren im Wesentlichen unendlich ist, kann der gesperrte Zustand durch Schieben und Scrollen durch andere Operationen weiter transformiert werden.

Viele blockierte Zustände mit einer minimalen Folge von Operationen, die sie erstellen, können mithilfe der Breitensuche (BFS) gefunden werden. Wie unten angegeben, wird eine Warteschlange zum Speichern von Zwischenergebnissen verwendet.

1. Wir stellen den Status bei der Erstellung in die Warteschlange.
2. Wir leiten den Status aus der Warteschlange ab.
3. Mit der Konvertierungsoperation erhalten wir die folgenden Zustände.
4. Wenn sich zwischen ihnen keine Abwärtsbewegung befindet, wird der aus der Warteschlange entfernte Status blockiert.
5. Wir stellen nachfolgende Zustände in die Warteschlange, die wir noch nicht besucht haben.
6. Wenn die Warteschlange nicht leer ist, wiederholen Sie ab Schritt 2.

Das Programm repräsentiert jeden Zustand als Objekt mit den folgenden Feldern:

{ x, y, rotation, visited, predecessor }

Während der Vorbereitung erstellt das Programm ein dreidimensionales Array von Zustandsobjekten (20 Zeilen × 10 Spalten × 4 Umdrehungen), wobei x , y und rotation entsprechend initialisiert werden.

Das visited Feld wird markiert, wenn sich der Status in der Warteschlange befindet. In BFS ist dies gültig, da jeder nachfolgende Status die Gesamtpfadlänge um 1 erhöht. Das heißt, durch Erhöhen der Pfadlänge ist es unmöglich, einen nachfolgenden Status zu erstellen, der an einer anderen Stelle als dem Ende der Warteschlange eingefügt werden muss, um die Reihenfolge aufrechtzuerhalten.

Das predecessor gibt das Statusobjekt an, von dem der aktuelle Status abgeleitet wird. Es wird festgelegt, wenn der Status in die Warteschlange gestellt wird. Der Erstellungsstatus hat keine vorherigen Status.

Die Menge der während der Suche erkannten Sperrzustände wird durch die Art des Tetriminos und die gefüllten Blöcke auf dem Spielfeld bestimmt. Die Reihenfolge der Bewegungen, die sie generiert haben, kann (in umgekehrter Reihenfolge) geklärt werden, indem Sie den predecessor zum Erstellungsstatus folgen. Wenn die Konstante PLAY_FAST zu Beginn des Programms auf true PLAY_FAST ist, werden die vorherigen Zustände vollständig übersprungen, indem Tetrimino direkt auf das Feld gesetzt und blockiert wird.

Ein dreidimensionales Array von Statusobjekten, eine Warteschlange und BFS werden in eine Klasse gepackt. Er hat eine Suchmethode, die das Spielfeld (zweidimensionales Array), die Art des Tetriminos und den Hörer empfängt. Jedes Mal, wenn ein gesperrter Zustand erkannt wird, wird das Spielfeld aktualisiert, indem Tetrimino an der entsprechenden Stelle hinzugefügt wird. Dann wird das geänderte Spielfeld zusammen mit Informationen über die Änderungen zur Verarbeitung an den Hörer übertragen. Nachdem der Listener die Rückkehr abgeschlossen hat, wird das Spielfeld wiederhergestellt.

Der Listener wird verwendet, um mehrere Suchvorgänge in einer Kette zu kombinieren, wodurch alle möglichen Möglichkeiten gefunden werden, zwei (oder mehr) Tetriminos zum Spielfeld hinzuzufügen. Die erste Suchmaschine in der Kette führt BFS nur einmal aus. Die zweite Suchmaschine führt jedoch jedes Mal BFS aus, wenn die erste Suche einen gesperrten Zustand erkennt. Und so weiter, wenn es andere Suchmaschinen in der Kette gibt.

Der Listener der letzten Suchmaschine wertet das geänderte Spielfeld aus. Wenn er das Spielfeld besser findet als zuvor untersucht, schreibt er das verwendete Objekt des gesperrten Zustands auf, das zu diesem Zeitpunkt die erste Suchmaschine in der Kette verwendet. Da die erste Suchmaschine BFS nur einmal ausführt, bleiben die predecessor ihrer Statusobjekte bis zum Abschluss des gesamten Suchvorgangs gültig. Das heißt, der letzte Zuhörer zeichnet im Wesentlichen den Weg auf, den das erste Tetrimino gehen sollte, um als Ergebnis die beste Konfiguration des Spielfelds zu erreichen.

Bewertungsfunktion

Die Bewertungsfunktion weist dem veränderten Spielfeld einen Wert zu - eine gewichtete Summe verschiedener Einflussparameter. Die in diesem Fall verwendete Bewertungsfunktion basiert auf der vom Islam Al-Ashi entwickelten Funktion. Es werden die folgenden Parameter verwendet:

• Gesamtzahl der gelöschten Zeilen : Dies ist die Gesamtzahl der Zeilen, die durch Hinzufügen von zwei Tetriminos gelöscht werden.
• Gesamte Blockierhöhe : Die Blockierhöhe ist die Höhe über dem Boden des Spielfelds, auf dem die Figur gesperrt ist. Dies ist der vertikale Abstand, um den eine gesperrte Figur fallen würde, wenn Sie alle anderen belegten Felder des Spielfelds entfernen und die Ausrichtung der Figur beibehalten. Die gesamte Blockierhöhe ist die Summe der Blockierhöhen der beiden Tetriminos.
• Die Gesamtzahl der "Well" -Zellen : Eine Well-Zelle ist eine leere Zelle, die sich über allen besetzten Zellen in einer Spalte befindet, sodass ihre linken und rechten Nachbarn besetzte Zellen sind. Bei der Bestimmung von Brunnen werden die Wände des Spielfelds als besetzte Zellen betrachtet. Die Idee ist, dass ein Brunnen eine Struktur ist, die oben offen, unten geschlossen und auf beiden Seiten von Wänden umgeben ist. Die Wahrscheinlichkeit intermittierender Lücken in den Wänden des Bohrlochs bedeutet, dass Bohrlochzellen nicht unbedingt in einem kontinuierlichen Haufen innerhalb einer Säule auftreten.
• Gesamtzahl der Löcher in den Spalten : Das Loch in der Spalte ist eine leere Zelle, die sich unmittelbar unter der belegten Zelle befindet. Das Geschlecht des Spielfeldes wird nicht mit der darüber liegenden Zelle verglichen. Es gibt keine Löcher in den leeren Spalten.
• Gesamtzahl der Übergänge in Spalten : Ein Übergang in Spalten ist eine leere Zelle neben einer belegten Zelle (oder umgekehrt) innerhalb einer einzelnen Spalte. Die Kombination des obersten belegten Spaltenblocks mit dem leeren Raum darüber wird nicht als Übergang betrachtet. In ähnlicher Weise wird auch der Boden des Spielfelds nicht mit der darüber liegenden Zelle verglichen. Daher gibt es in einer vollständig leeren Spalte keine Übergänge.
• Gesamtzahl der Übergänge in Zeilen : Ein Übergang in Zeilen ist eine leere Zelle neben einer belegten Zelle (oder umgekehrt) innerhalb derselben Zeile. Leere Zellen in der Nähe der Wände des Spielfelds gelten als Übergänge. Der Gesamtbetrag wird für alle Linien des Spielfelds berechnet. Bei der Gesamtzahl der Übergänge werden jedoch vollständig leere Zeilen nicht berücksichtigt.

El-Ashi schlug vor, dass nützliche Gewichte unter Verwendung des Particle Swarm Optimization (PSO) -Algorithmus gefunden werden können, der den Satz von Lösungen iterativ verbessert, indem das in der Natur beobachtete Schwarmverhalten simuliert wird. In unserem Fall ist jede Lösung ein Gewichtsvektor, und die Eignung der Option wird durch das Spiel in Tetris bestimmt. Dies ist die Gesamtzahl der Tetriminos, in denen er bis zum Ende des Spiels überlebt hat.

Diese Ideen werden in der unten beschriebenen Java-Version angewendet. Es läuft außerhalb von FCEUX und kann für ein nicht grafisches In-Memory-Spiel konfiguriert werden, das mit einer viel höheren Geschwindigkeit ausgeführt wird. Nach der Vorbereitung des PSO war ich überrascht zu sehen, dass sich der Algorithmus nach der ersten Iteration nicht weiter bewegt. Nach dieser Iteration spielten mehrere zufällig generierte Lösungsvarianten bereits recht gut. Für mehrere Tage nahm die Größe dieses Satzes ab, bis nur noch eine Option übrig blieb. Hier sind die Werte für diese Lösung:

Parameter	Gewicht
Gesamtzahl der gelöschten Zeilen	1.000000000000000
Gesamte Blockierhöhe	12.885008263218383
Gesamtzahl der Wellzellen	15.842707182438396
Die Gesamtzahl der Löcher in den Spalten	26.894496507795950
Die Gesamtzahl der Übergänge in Spalten	27.616914062397015
Total Line Jumps	30.185110719279040

Das Spielfeld wurde geschätzt, indem die Parameter mit ihren jeweiligen Gewichten multipliziert und die Ergebnisse addiert wurden. Je niedriger der Wert, desto besser die Lösung. Da alle Parameter und Gewichte positive Werte haben, beeinträchtigen alle Parameter die Gesamtbewertung. Jeder von ihnen muss minimiert werden. Dies bedeutet auch, dass die beste Punktzahl 0 ist.

Da diese Gewichte zufällig ausgewählt wurden, kann der Bereich geeigneter Werte sehr breit sein. Dieser bestimmte Satz von Zahlen und die geschätzte relative Bedeutung jedes Parameters sind möglicherweise nicht relevant. Trotzdem wird es interessant sein, sie genau zu beobachten.

Der am wenigsten schädliche Parameter ist die Gesamtzahl der gelöschten Zeilen. Die Tatsache, dass diese Option schädlich ist, ist nicht intuitiv. Aber das Hauptziel der KI ist das Überleben. Er strebt nicht nach den meisten Punkten. Stattdessen spielt er konservativ und räumt normalerweise die Ränge nacheinander ab. Um Double, Triple oder Tetris zu erhalten, muss man einen Haufen wachsen lassen, der gegen das langfristige Ziel verstößt.

Als nächstes in der Liste steht die gesamte Blockierungshöhe. Dies kann minimiert werden, indem das Tetrimino so nahe wie möglich am Boden abgesenkt wird. Dies ist eine einfache Strategie, die langfristig zum Überleben und kurzfristig zur hochwertigen Verpackung von Teilen beiträgt.

Das Gewicht, das der Gesamtzahl der Well-Zellen zugeordnet ist, scheint ein wenig überraschend, da erfahrene Spieler normalerweise absichtlich tiefe Wells bauen, um mehrere Tetris (vierzeilige Kombinationen) hintereinander zu sammeln. Aber wie oben erwähnt, ist dies ein riskantes Spiel, das dem Hauptziel - dem Überleben - widerspricht. Darüber hinaus ist die Anzahl der Vertiefungen ein Indikator für die „Rauheit“ des Pfahls. Ein gewisses Maß an Unebenheiten ist beim Platzieren bestimmter Figuren oder Figurenkombinationen von Vorteil. Eine hohe Rauheit führt jedoch zu einer Beschädigung der dichten Verpackung.

Die Gesamtzahl der Löcher in den Spalten beträgt ungefähr die Hälfte der Gesamtzahl der Übergänge in den Spalten. Diese Parameter können kombiniert und zu einem gemeinsamen verwandten Parameter zusammengefasst werden, wodurch ein umfangreicherer und schädlicherer Parameter erhalten wird: die Gesamtzahl der Übergänge.

Die dicht gepackten Bereiche weisen eine geringe Anzahl von Übergängen in alle Richtungen auf. Daher kann die Hauptstrategie, die von künstlicher Intelligenz angetrieben wird, kurz wie folgt beschrieben werden: Packen Sie die Teile so nah wie möglich aneinander.

Andere Optionen

Hier ist eine Liste einiger weiterer Parameter, mit denen ich während der Entwicklung der KI experimentiert habe:

• Haufenhöhe : Besetzte Blöcke können über leeren Zellen hängen und Vorsprünge und Löcher erzeugen. Es ist jedoch nicht möglich, belegte Blöcke über vollständig leere Zeilen zu sperren. Daher ist die Heap-Höhe die Anzahl der Zeilen, die mindestens einen belegten Block enthalten.
• Gesamtzahl der belegten Spalten : Dies ist die Anzahl der Spalten, die mindestens eine belegte Zelle enthalten.
• Gesamtzahl der belegten Zellen : Die Anzahl der belegten Zellen auf dem Spielfeld.
• Gesamtzahl der verbundenen Bereiche : Der Füllalgorithmus wird hier verwendet, um die Anzahl der kontinuierlich verbundenen Bereiche zu berechnen. Er findet nicht nur besetzte "Inseln", sondern entdeckt auch Löcher, die sich entlang beider Achsen erstrecken.
• Säulenhöhenstreuung: Dies ist ein statistisches Maß für die Variation der Säulenhöhen. Es ist ein Indikator für die Oberflächenrauheit.
• Gesamtanpassungswert : Berechnet den Anpassungswert des Heaps für die nächste unbekannte Zahl. Es zählt die Gesamtzahl der Möglichkeiten, wie 7 Arten von Formen zum Spielfeld hinzugefügt werden können, ohne dass neue Löcher auftreten. Für eine genaue Zählung ist die wiederholte Verwendung von BFS erforderlich. Für eine ungefähre Berechnung kann der Suchbaum jedoch stark abgeschnitten werden.
• Durchschnittliche Bewertung für die nächste Figur : Dieser Parameter vertieft die Suche, indem er alle Möglichkeiten für die nächste unbekannte Figur analysiert. Es verwendet andere Parameter, um die Position jedes Figurentyps zu trennen, und gibt dann den Durchschnitt für 7 Bewertungen zurück. Für jede Platzierung der Figur ist BFS erforderlich.
• Gemitteltes simuliertes Spiel : Der Parameter simuliert eine Reihe von Spielen in Tetris, wählt Teile mit einem eigenen Pseudozufallszahlengenerator aus und verwendet KI, um mit ihnen zu arbeiten. Am Ende jedes Spiels wird das Spielfeld anhand anderer Parameter bewertet. Der Durchschnittswert für alle Chargen wird zurückgegeben.

Alle Parameter können durch Hinzufügen von benutzerdefinierten Faktoren angepasst werden. Anstatt einfach die gelöschten Zeilen zu berechnen, können Sie beispielsweise Ihre eigenen Gewichte für Single, Double, Triple und Tetris zuweisen und so ein Punktesystem simulieren. Wenn die gleichzeitige Reinigung mehrerer Reihen das langfristige Überlebensziel beeinträchtigt, können einzelnen Reihen ein negatives Gewicht zugewiesen werden, während andere positiv werden können.

Ein weiterer nützlicher Faktor ist der Offsetwert. Zum Beispiel hat eine perfekt flache Oberfläche eines Haufens eine Streuung der Säulenhöhen von 0. Eine perfekt flache Oberfläche passt sich jedoch nicht an S und Z sowie an andere Formkombinationen an. Daher muss durch Subtrahieren der Konstante die Varianz um die optimale Rauheit zentriert werden.

Die angepassten und vorgespannten Parameter können bis zu einem gewissen Grad angehoben werden, so dass sie vor der Berechnung der gewichteten Summe logarithmisch oder exponentiell skaliert werden können. Alle diese Wahrscheinlichkeiten können als zusätzliche Gewichte betrachtet werden, die möglicherweise durch Methoden wie PSO optimiert werden können.

Viele der Parameter geben Aufschluss darüber, wie gut der Haufen mit zusätzlichen Stücken umgehen kann, z. B. solchen, die sich mit der Rauheit der Oberfläche befassen. Der „Gesamtbetrag der Anpassung“, die „durchschnittliche Bewertung der nächsten Figur“ und das „durchschnittliche simulierte Spiel“ bewerten jedoch das veränderte Spielfeld Einfügen von Zahlen, die nicht in den beiden bekannten enthalten sind. Bei der Untersuchung nachfolgender Figuren nimmt aufgrund der schnellen Eliminierung der Reihe die Menge an zusätzlichem Wissen mit der Tiefe ab. Dies bedeutet, dass der lange Verlauf der Partei in der Vergangenheit nicht so wichtig ist und der Verlauf der Partei in ferner Zukunft ebenfalls nicht sehr wichtig ist. Wenn eine kurze Folge von Figuren zufällig falsch eingestellt ist, stellt die KI das Spiel schnell wieder her und verwendet die folgenden Zahlen, um die betroffenen Reihen zu löschen. Die Bestimmung des optimalen Wertes für die Analyse nachfolgender Zahlen erfordert weitere Untersuchungen.

Ein weiterer Aspekt der Nützlichkeit eines Parameters sind die Rechenkosten. Die Kosten sind stark erhöht, da die Bewertungsfunktion für jede mögliche Platzierung von zwei Figuren aufgerufen wird. Da AI in der Lage sein muss, Tetris in Echtzeit zu spielen, können die Kostenfaktoren, die wertvolle Informationen liefern, gegen nähere Techniken ausgetauscht werden, die schneller laufen.

KI-Training

Es gibt pathologische Sequenzen, die unabhängig von der Strategie zu Game Over führen können. Das einfachste Beispiel ist die endlose Folge von Tetrimino S und Z, die, wie in der Animation gezeigt, schnell dazu führt, dass die KI verliert.


Da es Tage dauert, bis die AI-Variante ausgeführt ist, bevor mehrere Chargen abgeschlossen und der Durchschnitt berechnet wurden, ist es völlig unpraktisch, die durchschnittliche Chargendauer als PSO-Kontrollmetrik zu verwenden. Stattdessen können Sie die Komplexität des Spiels mit einer kontrollierten Geschwindigkeit erhöhen, indem Sie die Frequenz von S und Z erhöhen, was im Laufe der Zeit dazu führt, dass nur dieses Figurenpaar alternativ erstellt wird.

Ich habe versucht, diese Lehrmethode zu verwenden, aber festgestellt, dass das Unterrichten von KI für das Arbeiten mit häufigem S und Z tatsächlich die Fähigkeit beeinträchtigt, mit gleichmäßig verteilten zufälligen Formen umzugehen.

Bei einer alternativen Methode, die vom B-Type-Spiel inspiriert ist, steuert die PSO-Metrik die Häufigkeit der Zeilenreinigung. Das Spielfeld ist ein 10-Zeilen-Diagramm mit zufälligen Müllblöcken. Jedes Mal, wenn die Linie gelöscht wird, wird unten eine neue Mülllinie angezeigt, die die Höhe des Haufens wiederherstellt. Da das Spielfeld eine Breite von 10 Spalten hat und jedes Tetrimino im Durchschnitt aus 4 Quadraten besteht, sollte die KI alle 2,5 Tetrimino eine Zeile löschen. Und um den Müll loszuwerden, muss er es noch schneller machen.

Leider hat diese Technik auch die Leistung nicht verbessert. Ein wahrscheinlicher Grund ist, dass zufällige Mülllöcher nicht genau mit den Zeichenfolgen übereinstimmen, mit denen sich die KI im realen Spiel befasst. Darüber hinaus ist die Reinigung der Reihe ein kurzfristiges Ziel. Eine gierige Reihenreinigung verbessert nicht unbedingt das langfristige Überleben. Von Zeit zu Zeit sollten die Zeilen nicht berührt werden, um bestimmte Kombinationen nachfolgender Figuren zu verarbeiten.

Colin Fei schlug auf seiner Webseite einen anderen Ansatz vor. Er erstellte Histogramme, die den Prozentsatz der Formen anzeigen, die in jeder Reihe während der Versuchslose blockiert sind. Interessanterweise sehen alle Histogramme unabhängig von der Anzahl der erstellten Figuren nahezu identisch aus. Auf dieser Grundlage schlug er vor, dass Sie ein ungefähres Bild der Funktion für jeden Teststapel verwenden können, wenn Sie die statistische Erwartung bewerten, eine Figur in der Erstellungslinie zu blockieren, um so die Zeit zu erhalten, in der die KI bis zum Ende des Spiels spielt. Ich beschloss, diese Möglichkeit zu prüfen.

Unten finden Sie eine Wärmekarte vieler Testchargen mit insgesamt 2.039.900.000 Tetrimino. Jede Zelle wird basierend auf dem Prozentsatz der darin gesperrten Formen gefärbt. Um den visuellen Kontrast zu verbessern, wird eine nichtlineare Palette ausgewählt. Die Karte wurde erstellt, indem die Zellwerte normalisiert wurden, indem durch den maximalen Prozentsatz der Zellen dividiert und dann die Potenz von 0,19 angegeben wurde (siehe "Gammakorrektur" ).

Farbe Prozentsatz ■ 0.00000000 ■ 0.00000315 ■ 0.00024227 ■ 0.00307038 ■ 0.01860818 ■ 0.07527774 ■ 0.23582574 ■ 0.61928352 ■ 1.42923040 ■ 2.98867416 ■ 5.78182519

Die dunkelorangen und roten Streifen in den Zeilen 17 und 18 bedeuten, dass die überwiegende Mehrheit der Figuren dort landet. Der hellgrüne Farbton von unten ist eine Folge der Geometrie der Figuren: Nur 4 der 7 Tetrimino-Arten können in der unteren Zeile erscheinen. Die unteren Ecken sind schwarz, weil es unmöglich ist, dorthin zu gelangen.

Die Farbe entlang jeder Linie ist nahezu gleichmäßig, was darauf hindeutet, dass die Formen horizontal gleichmäßig verteilt sind. Leichte Lücken lassen sich anhand der Histogramme einzelner Formtypen erklären:

T.

J.

Z.

O.

S.

L.

Ich

T stellt sich als der universellste Typ heraus: Sein Histogramm ist einheitlicher als alle anderen. Anomalien im Histogramm J - das Ergebnis des Einflusses der Wände; Nur Jr und Jl können sich in den Seitenspalten befinden, wodurch AI die Spalten 1 und 9 häufiger zum Kompensieren verwendet. Gleiches gilt für L. Die Histogramme Z und S sehen ungefähr gleich aus, was das Ungleichgewicht aufgrund der Tatsache betont, dass Zv und Sv sind keine perfekten Spiegelbilder voneinander. Typ O ist auf ein 19 × 9-Spielfeld beschränkt, und es sieht so aus, als würde AI O eher an den Seiten als in der Mitte verwenden. Tetrimino I ist nach rechts verschoben, weil sich dort sein Startpunkt befindet; Daher ist das Sperren in Spalte 1 selten.

Die Tabelle zeigt den Prozentsatz der Zahlen, die in jeder Zeile blockiert sind.

String	Prozentsatz
0	0,0000000000
1	0,0000000000
2	0,0000004902
3	0,0000026472
4	0,0000066180
5	0,0000172557
6	0,0000512280
7	0,0001759400
8	0,0006681210
9	0,0023187901
10	0,0077928820
11	0,0259672043
12	0,0866187068
13	0,2901315751
14	0,9771663807
15	3.3000408353
16	10.6989059268
17	28.5687976371
18	50.0335706162
19	6.0077671454

Hier ist eine Grafik der Werte:


Wenn Linie 19 nicht berücksichtigt wird, zeigt die Grafik ein exponentielles Wachstum.

Das Folgende ist eine Liste der Verhältnisse der Anzahl gesperrter Formen in benachbarten Zeilen.

String A / String B.	Verhältnis (%)
1/2	0,00
2/3	18.52
3/4	40.00
4/5	38,35
5/6	33,68
6/7	29.12
7/8	26.33
8/9	28,81
9/10	29,76
10/11	30.01
11/12	29,98
12/13	29,85
13/14	29,69
14/15	29,61
15/16	30,84
16/17	37,45
17/18	57.10
18/19	832,81

Die Linien 16–19berücksichtigen die Figuren, die mit dem Boden des Spielfelds interagieren, so dass sie verworfen werden können. In Zeilen ist die 0–5Auswahl zu klein, um sinnvoll zu sein. Die übrigen Verhältnisse, Paare 6 / 7–14 / 15, sind nahezu identisch; ihr Durchschnittswert beträgt 29,24%. Dies bedeutet, dass die Wahrscheinlichkeit, dass der Heap um eine Zeile wächst, unabhängig von der Höhe des Heaps ungefähr gleich ist. Dies ist logisch, da Tetris-Regeln die Interaktion am oberen Rand des Heaps einschränken, wenn dieser dicht gepackt ist.

Die folgende Grafik zeigt das Protokoll von ₁₀ Prozent der Zahlen in den Zeilen 6–15.


Es liegt nahe an einer vollkommen geraden Linie mit einem Bestimmungskoeffizienten nahe 1 . Die aus der oben gezeigten linearen Regression abgeleitete Formel gibt den Schnittpunkt mit der Y-Achse an, vorausgesetzt, der Prozentsatz der Formen in Zeile 0 beträgt ungefähr 10 ^–7,459 %. Die Umkehrung dieses Wertes ergibt eine statistische Erwartung von 2.877.688.349 Tetrimino oder 1.151.175.340 Zeilen bis zum Ende des Spiels.

Dies macht uns das Protokoll ₁₀ verständlichDer Prozentsatz der Zahlen in jeder Zeile bleibt bis zur Zeile 0 linear. Wenn der Haufen jedoch fast die Decke des Spielfelds erreicht, ist die Bewegungsfreiheit so eingeschränkt, dass diese Eigenschaft verletzt wird. Darüber hinaus bedeutet das Blockieren eines Stücks in Zeile 0 nicht unbedingt, dass das Spiel beendet ist. Sie können weiterhin gespeichert werden, wenn ein Ort zum Erstellen neuer Figuren vorhanden ist.

Eine andere Möglichkeit, die Stärke der KI zu bewerten, besteht darin, die durchschnittliche Anzahl der erstellten Formen zwischen der vollständigen Reinigung des Spielfelds zu messen. Eine vollständige Reinigung kann mit nur 5 Tetriminos erreicht werden. Dies kann unter anderem durch fünf O-Figuren erreicht werden, die auf dem Boden des Spielfelds angeordnet sind. Da jedes Tetrimino aus 4 Quadraten besteht und die Breite des Spielfelds 10 Quadrate beträgt, sollte die Anzahl der zwischen der vollständigen Reinigung erstellten Figuren ein Vielfaches von 5 sein ( als4 × 5n = 2 × 10n ).

Meine KI hat eine durchschnittliche Anzahl von Formen, die zwischen vollständigen Feldreinigungen von 1.181 erstellt wurden - eine relativ kleine Anzahl. Da eine vollständige Bereinigung dem Neustart eines Spiels gleicht, kann ein vollständiger Stapel als extrem lange Serie von Neustarts des Spiels angesehen werden, gefolgt von einem schnellen Fortschritt zum Ende des Spiels. Wie die oben beschriebene Folge von Alternativen SZsind pathologische Sequenzen, die zum Ende des Spiels führen, normalerweise sehr kurz.

Das folgende Histogramm zeigt die Wahrscheinlichkeit (in Prozent), dass die KI nach der angegebenen Anzahl erstellter Figuren eine vollständige Löschung des Feldes erreicht.


Die Gradreihenfolge in der obigen Formel bestimmt die Abnahmerate und vermutlich die Stärke der KI. Nach dieser Formel enden ungefähr 0,4% oder ungefähr 1 von 253 Spielen, die mit einem leeren Spielfeld beginnen, mit einer vollständigen Bereinigung nach nur 5 Tetriminos.

Im Gegensatz zu dem, was Faye vorgeschlagen hat, erfordern die Konstanten in den linearen und exponentiellen Näherungen eine sehr große Stichprobengröße, so dass R ²näherte sich 1, daher ist diese Methode für PSO nicht anwendbar. Die mit langen Chargen erhaltenen Konstanten können jedoch verwendet werden, um die Approximationsfunktion zu optimieren, die mögliche konstante Werte für kurze Chargen erzeugt. In einer Art Entwicklungsrückkopplungsschleife kann die optimierte Approximationsfunktion im PSO verwendet werden, wodurch die AI verbessert wird, die wiederum zur Berechnung neuer Konstanten verwendet werden kann, die als Referenzkriterien für die Approximationsfunktion dienen.

Java-Version

Über das Programm

Für Entwickler, die mit Lua nicht vertraut sind, habe ich der Quell-Zip-Datei einen Java AI-Port hinzugefügt . Klassen sind fast zeilenweise Übersetzungen von Lua-Objekten basierend auf Abschlüssen .

Pakete

Der Code ist in zwei Pakete unterteilt:

• tetris.ai enthält AI-Klassen und Schnittstellen.
• tetris.gui erstellt ein grafisches Modell des Spielfelds.

KI-Klassen und Schnittstellen

Eine Klasse mit dem entsprechenden Namen Tetriminosbeschreibt Tetrimino. Es wird ähnlich verwendet enumund enthält Konstanten für alle Arten von Tetrimino:

 public static final int NONE = -1; public static final int T = 0; public static final int J = 1; public static final int Z = 2; public static final int O = 3; public static final int S = 4; public static final int L = 5; public static final int I = 6; 

NONEbedeutet nicht zugewiesener Wert. Es wird für leere Zellen des Spielfelds verwendet.

Auch Tetriminosenthält zwei Orientierungen des Tischmodell. PATTERNS- Dies ist ein 4-dimensionales ganzzahliges Array (Typ × Drehung × Quadrat × Koordinaten), das die relativen Koordinaten der Quadrate enthält. Die Linien sind so angeordnet, dass bei jedem Typ die Ausrichtung der Formerstellung an erster Stelle steht. ORIENTATIONSIst ein anderes Modell, ein zweidimensionales Array (Typ × Drehung) von Objekten Orientation. Jedes Orientationenthält die Koordinaten des Quadrats als Array von Objekten Point. Es enthält auch Felder, die den Bereich der zulässigen Positionen für die entsprechende Ausrichtung beschreiben.

 public class Orientation { public Point[] squares = new Point[4]; public int minX; public int maxX; public int maxY; ... } 

 public class Point { public int x; public int y; ... } 

Die Tetrimino-Rotation (der zweite Index in beiden Ausrichtungstabellen) wird in Objekten verwendet State, die von BFS bearbeitet werden.

 public class State { public int x; public int y; public int rotation; public int visited; public State predecessor; public State next; ... } 

x, yUnd rotationzusammen , um die Position und Orientierung der Figur beschreiben. Da der Tetrimino-Typ vom Moment der Erstellung bis zur Blockierung konstant bleibt, ist ein Feld dafür optional.

Die Klasse Searcher, die den BFS-Algorithmus enthält, erstellt beim Erstellen einen vollständigen Satz aller möglichen Objekte State:

 private void createStates() { states = new State[AI.PLAYFIELD_HEIGHT][AI.PLAYFIELD_WIDTH][4]; for(int y = 0; y < AI.PLAYFIELD_HEIGHT; y++) { for(int x = 0; x < AI.PLAYFIELD_WIDTH; x++) { for(int rotation = 0; rotation < 4; rotation++) { states[y][x][rotation] = new State(x, y, rotation); } } } } 

Obwohl Java über eine umfangreiche Sammlungs-API verfügt, Searcherenthält es eine eigene Implementierung der Warteschlange. Die Klasse Queueverwendet State.nextObjekte zu verbinden , Statein der verknüpften Liste. Da alle Objekte Statevordefiniert sind und jedes Objekt nur Stateeinmal zur Warteschlange hinzugefügt werden kann, kann die Warteschlange an Ort und Stelle arbeiten, sodass keine unnötigen temporären Containerobjekte erforderlich sind, die in allgemeinen Warteschlangenimplementierungen verwendet werden.

Das „Herz“ von BFS ist die unten gezeigte Methode search.

 public boolean search(int[][] playfield, int tetriminoType, int id) { int maxRotation = Tetriminos.ORIENTATIONS[tetriminoType].length - 1; int mark = globalMark++; if (!addChild(playfield, tetriminoType, mark, null, 5, 0, 0)) { return false; } while(queue.isNotEmpty()) { State state = queue.dequeue(); if (maxRotation != 0) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == 0 ? maxRotation : state.rotation - 1); if (maxRotation != 1) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == maxRotation ? 0 : state.rotation + 1); } } addChild(playfield, tetriminoType, mark, state, state.x - 1, state.y, state.rotation); addChild(playfield, tetriminoType, mark, state, state.x + 1, state.y, state.rotation); if (!addChild(playfield, tetriminoType, mark, state, state.x, state.y + 1, state.rotation)) { lockTetrimino(playfield, tetriminoType, id, state); } } return true; } 

Es erzeugt eine Warteschlange mit dem Status des erstellten Tetriminos und ruft dann nacheinander die untergeordneten Elemente aus den Status ab, die aus der Warteschlange entfernt wurden, und fügt sie der Warteschlange wieder hinzu, wenn sie auf dem Spielfeld angezeigt werden.

Ein searchSpielfeld, das eine Kombination aus besetzten und leeren Zellen, den erstellten Tetrimino-Typ und eine beliebige Kennung enthält, wird an die Methode übergeben . Während der Ausführung des BFS wird ein Listener aufgerufen, wenn eine Sperrposition erkannt wird.

 public interface ISearchListener { public void handleResult(int[][] playfield, int tetriminoType, int id, State state); } 

Der Hörer erhält ein geändertes Spielfeld, das ein festes Tetrimino enthält. Der Typ des erstellten Tetrimino und eine beliebige Kennung werden ebenfalls übertragen. Der letzte Parameter ist, Statein dem Tetrimino blockiert ist. Wenn Sie der Kette von Gliedern folgen State.predecessor, können Sie die StateForm wiederherstellen .

State.visitedkönnte implementiert werden als boolean; In diesem Fall müssten jedoch vor der Suche alle Objekte sortiert werden, Stateauf die zurückgesetzt werden visitedsoll false. Stattdessen habe ich einen visitedWert im intVergleich zu einem Zähler erstellt, der mit jedem Aufruf erhöht wird.

MethodeaddChildstellt nachfolgende Zustände in die Warteschlange. Der nachfolgende Zustand muss sich innerhalb des Feldes befinden und sich auf 4 leeren Zellen des Spielfelds befinden. Außerdem muss der nachfolgende Zustand nicht besucht werden State. Wenn die Position gültig ist, wird addChildzurückgegeben, trueauch wenn der nachfolgende Status nicht in die Warteschlange gestellt werden konnte, da er bereits besucht wurde.

Die Methode searchverwendet den Rückgabewert addChild, um zu bestimmen, ob eine Form erstellt werden kann. Wenn die Figur nicht erstellt werden kann, hat der Heap den oberen Rand erreicht und die Suche kann nicht mehr durchgeführt werden. deshalb kehrt es zurück false.

MehrwegaddChildEs wird auch die Bedeutung für die Möglichkeit untersucht, einen weiteren Schritt nach unten zu gehen. Wenn dies nicht möglich ist, ist der aktuelle Status die Sperrposition und der Anruf beginnt lockTetrimino. Die Methode lockTetriminoändert das Spielfeld, ruft den Listener auf und stellt dann das Spielfeld wieder her.

Jede Zeile des Arrays playfieldenthält 1 zusätzliches Element, in dem die Anzahl der belegten Zellen in der Zeile gespeichert ist. Das Inkrementieren eines Elements wird von der Methode ausgeführt, lockTetriminoda die Zellen als beschäftigt markiert werden.

Wenn der Hörer ein modifiziertes Spielfeld erhält, ruft er anPlayfieldUtil.clearRowsGefüllte Zeilen löschen Die Methode erkennt sie, indem sie den Wert im zusätzlichen Element des Arrays überprüft. Um eine Zeichenfolge zu entfernen, nutzt der Code die Tatsache, dass zweidimensionale Arrays in Java im Wesentlichen Arrays von Arrays sind. Es werden nur Links zu Zeichenfolgen gedrückt. PlayfieldUtilenthält freie Zeilen; Er schließt den Reinigungsprozess ab, indem er einen Link zu einem von ihnen einfügt. Vor dem Durchführen der Verschiebung wird der Index der zu löschenden Zeile in einem zusätzlichen Zeilenelement gespeichert. Dann wird die Verbindung zur Linie auf den Stapel geschoben.

Dann ruft der Hörer anPlayfieldUtil.restoreRowsÄnderungen am Spielfeld zu verwerfen. Schritte werden in umgekehrter Reihenfolge abgebrochen. Zuerst bekommen wir eine freie Reihe von oben. Dann wird die gefüllte Zeile vom Stapel abgerufen und der Index vom zusätzlichen Element wird wiederhergestellt. Es wird verwendet, um Zeilenreferenzen zu verschieben und an die Stelle der gelöschten Zeile zurückzukehren. Schließlich wird ein zusätzliches Element wiederhergestellt, dem der Wert der Breite des Spielfelds zugewiesen wird - die Anzahl der belegten Zellen in der gefüllten Zeile.

Es gibt PlayfieldUtilauch eine Methode evaluatePlayfield, die 4 Bewertungsparameter berechnet und in die unten gezeigte Containerklasse schreibt.

 public class PlayfieldEvaluation { public int holes; public int columnTransitions; public int rowTransitions; public int wells; } 

Die Klasse schafft das alles AI. Es enthält zwei Objekte, Searcherdie durch den unten gezeigten Listener miteinander verbunden sind.

 public void handleResult( int[][] playfield, int tetriminoType, int id, State state) { if (id == 0) { result0 = state; } Orientation orientation = Tetriminos.ORIENTATIONS[tetriminoType][state.rotation]; int rows = playfieldUtil.clearRows(playfield, state.y); int originalTotalRows = totalRows; int originalTotalDropHeight = totalDropHeight; totalRows += rows; totalDropHeight += orientation.maxY - state.y; int nextID = id + 1; if (nextID == tetriminoIndices.length) { playfieldUtil.evaluatePlayfield(playfield, e); double fitness = computeFitness(); if (fitness < bestFitness) { bestFitness = fitness; bestResult = result0; } } else { searchers[nextID].search(playfield, tetriminoIndices[nextID], nextID); } totalDropHeight = originalTotalDropHeight; totalRows = originalTotalRows; playfieldUtil.restoreRows(playfield, rows); } 

Eine Klasse AIkann mit einer beliebigen Anzahl von Objekten umgehen Searcher, Nintendo Tetris zeigt jedoch nur eine Form im Voraus an. Objekte Searcherwerden in einem Array gespeichert, und der oben gezeigte Code dient als gemeinsamer Listener. Die zufällige Kennung, die an die Methode übergeben wird, Searcher.searchist tatsächlich der Index des Arrays, der auch die Tiefe der Suche darstellt. Wenn der Listener aufgerufen wird, leitet der Bezeichner den Anruf zum nächsten Searcherin der Kette. Wenn er das Ende des Arrays erreicht, wertet er das Spielfeld aus. Und wenn er ein Spielfeld mit einem höheren Fitness-Score findet, schreibt er das blockierte Statevom ersten Searcherin der Kette auf.

AIenthält eine Methode search, die das Spielfeld empfängt, und ein Array, das die Typen des erstellten und des nächsten Tetriminos enthält. Er kehrt zurückStateenthält die Position und Drehung, in der das erste Tetrimino blockiert werden soll. Er konzentriert sich nicht auf das zweite Tetrimino; Beim nächsten Aufruf wird die Punktzahl neu berechnet. Wenn der Haufen zu hoch ist und die Kette Searchernicht beide Tetriminos platzieren kann, kehrt sie AI.searchzurück null.

 public State search(int[][] playfield, int[] tetriminoIndices) { this.tetriminoIndices = tetriminoIndices; bestResult = null; bestFitness = Double.MAX_VALUE; searchers[0].search(playfield, tetriminoIndices[0], 0); return bestResult; } 

KI-Herausforderung

Da die Java-Version nicht an FCEUX gebunden ist, kann sie möglicherweise für andere Projekte verwendet werden. Für diejenigen, die daran interessiert sind, KI an einem anderen Ort zu integrieren, beschreibt dieser Abschnitt alles, was Sie brauchen.

Erstellen Sie zunächst eine Instanz AI, eine Instanz PlayfieldUtilund ein Array für alle bekannten Tetrimino-Typen. Erstellen Sie außerdem eine PlayfieldUtil.createPlayfieldInstanz des Spielfelds, indem Sie aufrufen . Es gibt ein zweidimensionales Array mit einer zusätzlichen Spalte zurück, die wir oben untersucht haben. Sie benötigen wahrscheinlich auch einen Zufallsgenerator.

 AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random(); 

Anfangs ist das Spielfeld leer und alle Zellen sind relevant Tetriminos.NONE. Wenn Sie die Zellen programmgesteuert ausfüllen, vergessen Sie nicht, die playfield[rowIndex][AI.PLAYFIELD_WIDTH]Anzahl der belegten Zellen in jeder Zeile aufzuschreiben .

Füllen Sie das Array der Tetrimino-Typen mit den Typen der ursprünglich erstellten Form und der nächsten Form, die normalerweise manuell ausgewählt werden.

 tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7); 

Dann übergeben wir das Spielfeld und das Array von Typen an die Methode AI.search. Er wird zurückkehren, Statein dem Sie das erste Tetrimino blockieren müssen. Wenn er zurückkommt null, ist ein Spielende unvermeidlich.

 State state = ai.search(playfield, tetriminos); 

Wenn Sie einen Weg vom Erstellen einer Figur zum Sperren benötigen, übergeben Sie ihn an die StateMethode AI.buildStateList.

 State[] states = ai.buildStatesList(state); 

Um das Spielfeld zu aktualisieren, geben wir es PlayfieldUtil.lockTetriminozusammen mit seinem Typ und Objekt weiter State. Diese Methode löscht automatisch die gefüllten Zeilen.

 playfieldUtil.lockTetrimino(playfield, tetriminos[0], state); 

Bevor Sie erneut anrufen, AI.searchmüssen Sie das nächste Tetrimino zufällig auswählen.

 tetriminos[0] = tetriminos[1]; tetriminos[1] = random.nextInt(7); 

Zusammen sieht es so aus:

 AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random(); tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7); while(true) { // ... print playfield ... State state = ai.search(playfield, tetriminos); if (state == null) { break; // game over } playfieldUtil.lockTetrimino(playfield, tetriminos[0], state); tetriminos[0] = tetriminos[1]; tetriminos[1] = random.nextInt(7); } 

Anstatt das Spielfeld in Textform anzuzeigen, können Sie auf interessantere Weise anzeigen, was gerade passiert ...

Spielfeldanzeige

Die Klasse TetrisFrameimitiert Nintendo Tetris-Grafiken, einschließlich der im vorherigen Teil des Artikels beschriebenen Verhaltensfunktionen.


Führen Sie es aus, um es in Aktion zu sehen tetris.gui.Main. Wie bei der Lua-Version können wir die Spielgeschwindigkeit anpassen, indem wir den konstanten Wert am Anfang der Datei ändern.

 public static final boolean PLAY_FAST = true; 

TetrisFramehat 4 Methoden zur Manipulation des Bildschirms. Die Methode displayTetriminorendert aktives Tetrimino in den angegebenen Koordinaten. Es erhält einen Verzögerungsparameter, der die Methode warten lässt, bevor die angegebene Anzahl von Animationsframes zurückgegeben wird.

 public void displayTetrimino(int type, int rotation, int x, int y, int delay) 

Die Methode lockTetriminoverriegelt die Figur. Der Zeilenzähler, die Punkte, die Ebene und die Tetrimino-Farben werden entsprechend aktualisiert und zeigen das erwartete merkwürdige Verhalten, wenn die Werte die zulässigen Werte überschreiten. Das Zuweisen eines animateWerts zu einem Parameter trueumfasst Zeilenbereinigungsanimationen und Bildschirmflackern beim Empfang von Tetris. Die Methode wird blockiert, bis die Animation beendet ist.

 public void lockTetrimino(int type, int rotation, int x, int y, boolean animate) 

updateStatisticsAndNext Führt ein Inkrement des Statistikzählers für das neu erstellte Tetrimino durch und aktualisiert die Anzeige der nächsten Abbildung.

 public void updateStatisticsAndNext(int activeTetrimino, int nextTetrimino) 

Die Methode dropTetriminoerzeugt eine Form und ermöglicht es ihr, unter dem Einfluss der "Schwerkraft" abzusteigen, ohne zu versuchen, sie zu drehen oder zu bewegen. Mainverwendet es für die letzten beiden Ziffern, wenn es AI.searchzurückkehrt null. Wenn der Parameter animatewichtig trueist und es unmöglich ist, eine Figur zu erstellen, fällt der Vorhang zum Ende des Spiels. Wie bei allen anderen Methoden wird diese Methode blockiert, bis die Animation beendet ist. Es wird truenur zurückgegeben, wenn eine Figur auf einem geschäftigen Spielfeld erstellt werden kann.

 public boolean dropTetrimino(int type, boolean animate) 

Diese 4 Methoden müssen vom Workflow aufgerufen, aber TetrisFrameim Event Dispatch Thread selbst erstellt werden. Informationen dazu finden Sie in der Klasse Main.

Aus Gründen des Interesses Mainverwendet er eine Klasse Randomizer, die einen voreingenommenen Pseudozufallszahlengenerator von Nintendo Tetris simuliert.

Das Paket tetris.gui.imagesenthält anzeigebezogene Dateien. tiles.png- Dies ist eine Mustertabelle, die alle Kachelgrafiken enthält. background.datspeichert die Kennungen der Kacheln, aus denen der Hintergrund besteht; Daten extrahiert aus $BF3F. Und es colors.datenthält Bytes, die ungewöhnliche quadratische Farben erzeugen, die ab Ebene 138 erscheinen. Es

ImageLoaderenthält eine Tabelle mit NES-Paletten, und der ImagePanevollständige Satz der angezeigten Ebenenwerte wird gespeichert.

Andere Projekte

Möglicherweise kann der Code verwendet werden, anstatt für den Demo-Modus zu schreiben. Tatsächlich kann eine solche Demo für immer gerendert werden, wobei ausgenutzt wird, wie schnell die KI das gesamte Spielfeld räumen kann. Um dies zu erreichen, müssen Sie im Pseudozufallszahlengenerator eine beliebige Konstante als Startwert verwenden, wodurch wir eine deterministische Tetrimino-Sequenz erhalten. Die ersten beiden Tetrimino-Sequenzen werden aufgezeichnet. Wenn die KI die vollständige Feldbereinigung erreicht, werden die nächsten beiden Tetriminos mit den ersten beiden der Sequenz verglichen. Wenn sie übereinstimmen (dieses Ereignis wird alle 49 vollständigen Feldreinigungen erwartet), kann dem Pseudozufallszahlengenerator dieselbe Konstante wie Seed übergeben werden, wodurch eine Endlosschleife erstellt wird. Die Dauer des Zyklus kann sehr lang sein, um die Tatsache zu verbergen, dass es sich um einen Zyklus handelt. Außerdem,Die Demo kann an einem zufälligen Punkt in der Schleife beginnen und jedes Mal eine neue Demo erstellen.

Eine andere Möglichkeit, KI zu verwenden, besteht darin, einen "Player versus Computer" -Modus zu erstellen. Während im Mehrspieler-Tetris mehrere Linien gleichzeitig gelöscht werden, erscheinen im unteren Teil des gegnerischen Feldes Mülllinien, die das Spielfeld erhöhen. Die KI muss in der Lage sein, sich aus dem gleichen Grund vor Schmutz zu schützen, aus dem sie B-Type-Spiele spielen kann. Wie bereits erwähnt, spielt AI jedoch konservativ und versucht normalerweise, jeweils eine Zeile zu löschen. Das heißt, er wird sich gegen Angriffe verteidigen können, aber er kann nicht angreifen. Um sein Verhalten ändern zu können, habe ich eine Schnittstelle namens erstellt IChildFilter.

 public interface IChildFilter { public boolean validate(int[][] playfield, int tetriminoType, int x, int y, int rotation); } 

AIhat einen alternativen Konstruktor, der eine Implementierung erhält IChildFilter. Falls verfügbar, IChildFilter.validatedient es als zusätzliche Überprüfung für die Erlaubnis des untergeordneten Staates. Wenn es zurückkehrt false, wird der untergeordnete Status nicht in die Warteschlange gestellt.

WellFilterIst eine ImplementierungIChildFilterzielte darauf ab, vier Reihen (Tetris) aufzunehmen. Wie lebende Spieler baut sie nach und nach einen Brunnen in der rechten Spalte des Spielfelds und steigt Zeile für Zeile von unten nach oben an. Da es zeilenweise arbeitet, lehnt es untergeordnete Zustände ab, die der Spalte ganz rechts ein Quadrat hinzufügen. Wenn die gesamte Zeile mit Ausnahme der Bohrlochspalte vollständig gefüllt ist, fährt die KI mit der nächsten Zeile fort. Wenn 4 oder mehr dieser Leitungen fertig sind, kann der "Stock" in den Brunnen fallen und Tetris erhalten. Außerdem wird die Höhe des Haufens verfolgt. Wenn es zu groß wird, wirkt es sich WellFilternicht mehr auf die KI aus.


Nehmen Sie die Mainfolgenden Änderungen vor , um den Betrieb zu testen :

 AI ai = new AI(new WellFilter()); 

WellFilterfunktioniert, aber nicht besonders effektiv. Es enthält eine einfache Heuristik, die das Konzept demonstrieren soll. Um Tetris häufiger zu erhalten, müssen Sie eine ausgefeiltere Strategie verwenden, die möglicherweise mithilfe von PSO optimiert werden kann.

Darüber hinaus können Sie die Filterung des untergeordneten Status verwenden, um Muster zu generieren. Unten ist ein Beispiel dafür, wozu er fähig ist PatternFilter.


PatternFilterErstellt Bilder Zeile für Zeile von unten nach oben, ähnlich wie es funktioniert WellFilter. Anstatt die Spalte ganz rechts beizubehalten, werden jedoch PatternFilternur untergeordnete Zustände genehmigt, die einem bestimmten Muster entsprechen.

Der Konstruktor PatternFiltererhält den Namen eines der Bilder im Paket tetris.gui.patterns, das er als Vorlage verwendet. Jedes 20 × 10-Bild enthält Schwarz-Weiß-Pixel, die den Zellen im Spielfeld entsprechen.

 AI ai = new AI(new PatternFilter("tetriminos")); 

Die oben gezeigte Codezeile erzeugt die Silhouetten von sieben Arten von Tetrimino.


Ein weiteres Beispiel mit einem großen Tetrimino T, das in einem Winkel gedreht wurde.


Ein weiteres Beispiel. Wenn Sie genau hinschauen, sehen Sie den Namen des Spiels.


Wie WellFilter, PatternFilteres ist nichts anderes als ein Proof of Concept. Die Muster, die er verarbeitet, beschränken sich auf den unteren Rand des Spielfelds, da Versuche, sie zu erhalten, normalerweise mit dem Ende des Spiels enden. Dies ist jedoch eine interessante Idee, die es wert ist, weiter untersucht zu werden.

Gamepad-Version

Das Lua-Skript und das Java-Programm ignorieren die Schwerkraft. Für sie ist die Abstiegsgeschwindigkeit nicht wichtig, da sie je nach Konfiguration die Figuren entweder sofort an den gewünschten Ort teleportieren oder auf einem beliebigen Pfad ziehen. In gewisser Weise ahmen sie nur Tetris nach und spielen es nicht. In der Zip-Datei mit den Quellen befindet sich jedoch ein weiteres Lua-Skript, das die Signale der Gamepad-Schaltflächen generiert, sodass das Spiel die Bewegung von Figuren, die Schwerkraft und alles andere steuern kann.

Das Hinzufügen von Schwerkraft erweitert den Suchraum erheblich und zwingt die KI, die listigen Regeln für die Manipulation von Formen zu berücksichtigen. Details dieser Regeln werden im ersten Teil des Artikels beschrieben und können durch eine direkte Untersuchung des Codes vollständig erkannt werden. Hier sind die wichtigsten:

• : , .
• «» .
• «» «» .
• .
• .
• .
• .
• , .
• A B .
• «» «» 6 16 . «» «» , .
• «» 3 .
• 96 . , — .

Um all diese Regeln zu berücksichtigen, müssen historische Informationen in die Suchzustände eingebettet werden. Sie benötigen Felder, in denen die Anzahl der Haltebilder für jede Schaltfläche und die Anzahl der Bilder nach der letzten automatischen Freigabe gespeichert werden. Jeder eindeutige Satz von Werten, einschließlich Koordinaten x, yund die Tetrimino-Rotation kennzeichnen einen separaten und eindeutigen Zustand. Leider ist die Anzahl der Möglichkeiten so groß, dass eine vollständige Suche in diesem Raum unpraktisch ist. Die KI-Version für das Gamepad untersucht nur einen Teil davon.

AI verwendet ein Objekt Statemit den folgenden Feldern:

 { x, y, rotation, Left, Right, Down, A, B, fallTimer, visited, predecessor } 

Anstatt die automatische KI-Verschiebung in alternativen Frames zu verwenden, drücken Sie kurz die Umschalttaste. Daher muss er nur dann überwachen, ob die Taste gedrückt wird und nicht wie lange sie gedrückt wird. Da keine automatische Drehung gilt die gleiche Idee zu den Tasten A und B. Daher Bereich Left, Right, Aund Bkann als die Auflistung , die eine der folgenden Werte interpretiert werden:

 { RELEASED, PRESSED } 

Auf der anderen Seite müssen Sie für einen sanften Abstieg zunächst die Taste „Ab“ für drei Frames gedrückt halten, was die Existenz von 4 Zuständen erfordert:

 { RELEASED, PRESSED_FOR_1_FRAME, PRESSED_FOR_2_FRAMES, PRESSED_FOR_3_FRAMES } 

Downerhöht sich schrittweise von dem Wert RELEASEDauf PRESSED_FOR_3_FRAMES, bei dem ein weicher Abstieg auftritt. Danach kann es einen Wert empfangen RELEASEDoder zu zurückkehren PRESSED_FOR_2_FRAMES, was jeden zweiten Frame nach der anfänglichen Verzögerung einen weichen Abstieg verursacht. Es kann nicht RELEASEDvon PRESSED_FOR_1_FRAMEoder von sein PRESSED_FOR_2_FRAMES.

Eigentlich verwendet der Lua-Code eine Ganzzahlkonstante, aber das Prinzip ist dasselbe. In

ähnlicher Weise visitedund predecessor, fallTimerwird der erhaltene Wert zugewiesen wird, wenn in der Hilfswarteschlangenstatus zu schreiben; Es fallTimerist eins mehr als der Wert des übergeordneten Status. Bedingung enthaltendfallTimer, gleich der Abstiegsgeschwindigkeit, impliziert, dass in diesem Rahmen ein automatischer Abstieg stattfindet, und für nachfolgende Zustände dieses Zustands ist der Wert fallTimer0.

Jeder Searcherdefiniert ein 8-Array vor, das alle möglichen Zustände enthält ( 20 × 10 × 4 × 2 × 2 × 4 × 2 A × 2 B), und BFS wird ähnlich der für das Array gezeigten Methode ausgeführt . Der unten gezeigte Pseudocode beschreibt, wie nachfolgende Zustände aus den Ruhezuständen erhalten werden.

 Slide = (Left == PRESSED) or (Right == PRESSED) Rotate = (A == PRESSED) or (B == PRESSED) if Down == RELEASED or Down == PRESSED_FOR_3_FRAMES then if Down == RELEASED then nextDown = PRESSED_FOR_1_FRAME else nextDown = PRESSED_FOR_2_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end if Slide then addChild() if not Rotate then addChild(A = PRESSED) addChild(B = PRESSED) end else addChild(Left = PRESSED) addChild(Right = PRESSED) if not Rotate then addChild(Left = PRESSED, A = PRESSED) addChild(Left = PRESSED, B = PRESSED) addChild(Right = PRESSED, A = PRESSED) addChild(Right = PRESSED, B = PRESSED) end end else if Down == PRESSED_FOR_1_FRAME then nextDown = PRESSED_FOR_2_FRAMES else nextDown = PRESSED_FOR_3_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end end 

Wie im folgenden Pseudocode gezeigt, addChildberücksichtigt die Funktion die Reihenfolge der Ereignisse, die in jedem Frame auftreten (z. B. Verschiebung, Drehung und Abstieg).

 nextFallTimer = fallTimer + 1 if Left == PRESSED and testPosition(x - 1, y, rotation) then x = x - 1 elseif Right == PRESSED and testPosition(x + 1, y, rotation) then x = x + 1 end if A == PRESSED and testPosition(x, y, nextClockwiseRotation) then rotation = nextClockwiseRotation elseif B == PRESSED and testPosition(x, y, nextCounterclockwiseRotation) then rotation = nextCounterclockwiseRotation end if Down == PRESSED_FOR_3_FRAMES or nextFallTimer >= dropSpeed then if testPosition(x, y + 1, rotation) then y = y + 1 nextFallTimer = 0 else lockTetrimino() return end end childState = states[y][x][rotation][Left][Right][Down][A][B] if not childState.visited then childState.visited = mark childState.predecessor = state childState.fallTimer = nextFallTimer queue.enqueue(childState) end 

Wie in der vorherigen Version wird AI.searcheine Kette von Objekten zurückgegeben State. In diesem Fall Stateenthält jede jedoch viele Schaltflächen, die in jedem Frame gedrückt werden müssen. Feld x, yund rotationist für die Manipulation der Zahlen nicht verwendet, sondern kann verwendet werden , um die Richtigkeit der Zahlen bewegen zu überprüfen.

Obwohl der Suchraum aufgrund der oben beschriebenen Einschränkungen erheblich reduziert wurde, dauert es 1-3 Sekunden, um die Suche abzuschließen. Wenn Sie es ausführen, werden Sie nach dem Erstellen jedes Tetriminos eine Pause bemerken. Außerdem sehen die Bewegungen sehr unnatürlich aus; Normalerweise wird eine Drehung unmittelbar vor dem Verriegeln durchgeführt. Diese KI spielt sich jedoch fast genauso ab wie die Version, bei der die Schwerkraft selbst bei maximaler Geschwindigkeit ignoriert wurde.

Um es zu überprüfen, führen Sie es aus lua/NintendoTetrisAIGamepadVersion.lua, das sich in der Zip-Datei mit den Quellen befindet .

Eine einfachere Möglichkeit, die Schwerkraft zu berücksichtigen, besteht darin, die Bewegung der Figuren nur durch Drehen, gefolgt von einer Verschiebung und anschließendem Abstieg nach unten zu begrenzen. Die Idee ist, dass die vertikale Geschwindigkeit der Figuren wenig Einfluss auf die KI hat, wenn Sie das Gleiten und Scrollen loswerden. Alles, was er tun muss, ist, die Figur an die gewünschte Säule zu liefern, und die Schwerkraft erledigt den Rest. Ein weiterer Vorteil dieser Technik besteht darin, dass der Suchraum sehr klein ist, sodass Sie ohne Verzögerung für Berechnungen in Echtzeit spielen können. Der Nachteil dieses Ansatzes ist jedoch, dass die KI ohne Gleiten und Scrollen viel schlechter spielt. Die Tetris-KI, die nicht in Echtzeit spielen kann, ist jedoch praktisch wertlos.

Ergänzung

Zuvor habe ich ein Plugin geschrieben, das einen Spieler in Tetris prozedural simuliert. Mein Projekt hatte jedoch einige Nachteile:

1. Der Bot hat die Schwerkraft ausgeschaltet, sodass Sie Folien und Scrollen ausführen können, die die Fähigkeiten des Players auf der niedrigstmöglichen Stufe von Nintendo Tetris übertreffen. Er hebt die Figuren nie an, aber der einzige Weg, die Zahlen zu senken, ist ein kontrollierter sanfter Abstieg. Das heißt, er spielt in einer theoretischen, idealisierten Welt. Um es ganz klar auszudrücken, er betrügt.
2. . — , . Double, Triple Tetris, — , . 90. , , 29 - .
3. . . . , Tetris .

In diesem Abschnitt werde ich über einen fortgeschrittenen Bot sprechen, der Nintendo Tetris spielt, ohne die Schwerkraft zu deaktivieren. Er bewertet das Risiko und verwaltet es, wobei er aggressiv versucht, die maximale Punktzahl zu erreichen, bevor er eine hohe Abstiegsgeschwindigkeit erreicht.

---

Video

Beobachten Sie, wie der Bot in allen unten gezeigten Videos ab Stufe 19 die maximale Anzahl an Nintendo Tetris-Punkten erreicht.

---

Herunterladen

TetrisAI_2018-01-28.zip

Die Datei .zipenthält:

• src - Quellcodebaum.
• TetrisAI.jar - kompilierte Binärdatei.
• lgpl-2.1.txt - Lizenz für freie Software.

---

Starten

Voraussetzungen

• Nintaco ist ein NES / Famicom-Emulator.
• Tetris (U) [!].nes - Nintendo Tetris ROM-Datei.

Plugin starten

1. Starten Sie Nintaco und öffnen Sie Tetris (U) [!].nes.
2. Auszug TetrisAI.jaraus dem heruntergeladenen .zip.
3. Öffnen Sie das Fenster Programm ausführen, indem Sie Extras | wählen Programm ausführen ...
4. JAR Find JAR… .
5. Load JAR, .
6. Run.
7. , GAME TYPE MUSIC TYPE . D-pad ( ) A-TYPE . Start (Enter), .
8. A-TYPE D-pad ( ) LEVEL 9 . , A Start ( X Enter), 19, .

Es ist zu beachten, dass der Bot nur für Level 19 und höher ausgelegt ist. In niedrigeren Levels kann er die Teile nicht kontrollieren.

Geschwindigkeitsreferenz

Um das Spiel schneller zu machen, wählen Sie Maschine | Geschwindigkeit | Max

---

Details

Hochebene

Unterhalb von Stufe 10 ist die Abstiegsgeschwindigkeit in jeder Stufe etwas höher als in der vorherigen. Ab Stufe 10 gibt es jedoch mehrere Plateaus, bei denen die Geschwindigkeit für mehrere Stufen konstant bleibt. Dies ist eine Folge der Funktionsweise des Auslösemechanismus. Die Geschwindigkeit wird als Anzahl der Frames pro Abstieg dargestellt, was ein ganzzahliger Wert ist. Das heißt, für höhere Ebenen gibt es nicht mehr viele Optionen: 10–12, 13–15, 16–18, 19–28 und 29+ sind 5, 4, 3, 2 und 1 Rahmen für den Abstieg.

Der Bot wurde nur unter Berücksichtigung des Plateaus 19–28 entwickelt. In geraden Frames klickt er auf das Gamepad "Links", "Rechts", A, B oder nichts. Und in ungeraden Bildern ermöglicht es den automatischen Abstieg ohne Drücken von Tasten. Es scheint, dass das Spiel die horizontale Bewegung, die mit der Rotation zusammenfällt, nicht wahrnimmt; Daher wird jede Taste unabhängig in geraden Bildern gedrückt.

Im Gegensatz zu Meistern, die auf hohem Niveau spielen, nutzt der Bot Delayed Auto Shift (DAS), auch als Auto-Repeat bezeichnet, und verwandte Techniken nicht. Seine Arbeit erinnert eher an die vibrierende Daumentechnik von Thor Akerlund . Es erhöht jedoch die Schwingungsfrequenz auf das theoretische Maximum, das das Spiel zulässt.

Spieler werden mit 40, 100, 300 und 1200 Punkten für Einzel, Doppel, Dreifach und Tetris belohnt. Und die Punkte werden mit der Levelnummer plus 1 multipliziert. Mit anderen Worten, um die maximale Punktzahl zu erreichen, muss der Spieler die maximale Anzahl von Tetris anstreben und so lange wie möglich auf hohen Levels spielen.

Level 19 ist das höchste Level, das als erstes ausgewählt werden kann, wodurch der Bot direkt zum Plateau 19–28 springen kann. Aufgrund eines Fehlers im Level-Berechnungsmechanismus, den ich im vorherigen Teil erwähnt habe, geht das Spiel nach dem Löschen von 140 Zeilen auf Level 20 anstatt auf die erwarteten 200. Danach wechselt das Spiel alle 10 Zeilen das Level. Nach Erreichen von 230 Reihen steigt der Bot jedoch vom Plateau auf und gibt schnell auf. Das heißt, er muss so viele Tetris wie möglich wählen, bevor er 230 Zeilen säubert.

Sanfter Abstieg

Ein sanfter Abstieg kann auch die Anzahl der Punkte erhöhen. Um Punkte zu erhalten, muss die Figur vorsichtig abgesenkt werden, um das Spielfeld zu fixieren. Ein kurzfristiger sanfter Abstieg, der beim Positionieren einer Figur auftritt, hat keinen Einfluss auf die Punktzahl. Wenn der Abstieg erfolgreich ist, erhält der Spieler einen Punkt für jede Linie, die während des weichen Abstiegs gekreuzt wurde. Und der resultierende Wert wird nicht mit der Ebenennummer multipliziert, selbst wenn ein sanfter Abstieg zum Löschen der Zeilen führt.

Ein sanfter Abstieg hat wenig Einfluss auf die Gesamtpunktzahl. Wenn möglich, vervollständigt der Bot die Platzierung der Figur, indem er auf „Nach unten“ klickt, um diese Punkte zu erhalten. In seltenen Fällen kann die Differenz zwischen einer sehr hohen Punktzahl und einer Überschreitung der Maximalpunktzahl gemittelt werden.

AI-Algorithmus

Beim Erstellen einer Form untersucht der Bot jede mögliche Platzierung der aktuellen und nächsten Form. Zulässige Platzierung ist die Position, in der die Figur entweder auf besetzten Zellen oder auf dem Boden des Spielfeldes ruht. Vom Erstellungsort der Figur aus kann diese Position durch eine Abfolge horizontaler Bewegungen, Drehungen und Abfahrten erreicht werden. Gültige Orte und Pfadsequenzen werden mit BSF gefunden.

Das Platzieren eines Stücks auf dem Spielfeld hat Konsequenzen: 4 leere Zellen werden besetzt, und alle gefüllten Reihen werden gelöscht, wodurch die Reihen nach unten gehen. Für jede zulässige Platzierung der aktuellen Figur und die damit verbundenen Konsequenzen überprüft der Bot jede gültige Platzierung der nächsten Figur und bewertet die Kombination der Konsequenzen. Eine solche Suchkette wird vorgestellt SearchChain.

Jede der kombinierten Konsequenzen wird auf eine Bewertungsfunktion übertragen, die den Inhalt des Spielfelds berechnet. Die Kombination mit der niedrigsten Punktzahl gewinnt und das aktuelle Stück wird entsprechend platziert. Suchkettenergebnisse wirken sich nur auf die aktuelle Form aus. Beim Erstellen der nächsten Abbildung wird diese in Kombination mit der darauf folgenden Abbildung usw. ausgewertet.

Bewertungsfunktion

Die Bewertungsfunktion ist eine gewichtete Summe der folgenden Parameter:

• Die Gesamtzahl der gelöschten Zeilen ist die Anzahl der Zeilen, die durch Hinzufügen beider Tetriminos gelöscht wurden.
• – , . — , , .
• - – .
• – , -.
• – , . . .
• – . , 1. , , .
• – , . — , — .
• – . , (20).
• – . , 0.
• – , ( ) .
• : — , ( ) . . . .
• – . , 1 , 1, — 0.
• – .
• – .
• – .
• – . .
• – .

Maschinelles Lernen

Um die Gewichte der Bewertungsfunktion zu ermitteln, verwendeten wir eine Variante der in Fußnote [1] beschriebenen Methode der Partikelschwarmoptimierung (PSO). Um ein gutes Konvergenzverhalten zu erhalten, werden die vorgeschlagenen Trägheits- und Beschleunigungskoeffizienten angewendet. Und die maximalen Größen von Partikelschritten werden durch die Begrenzung ihrer Geschwindigkeitswerte bestimmt.

Während jeder Iteration wurden Partikel parallel ausgewertet, um die verfügbaren Rechenressourcen voll auszunutzen. Nachdem Konvergenz festgestellt wurde (keine Verbesserung nach einer bestimmten Anzahl von Iterationen), wurde das PSO so eingestellt, dass es automatisch mit zufällig ausgewählten Gewichten neu gestartet wird, sodass wir den Suchraum weiter untersuchen konnten.

Jeder Partikelpositionsvektor wurde bewertet, indem die Fertigstellung von 100 Chargen auf einem Plateau der Ebenen 19–28 simuliert wurde. Bei einer vollständigen Charge werden 230 Zeilen gereinigt, aber viele endeten mit einem Überlauf des Feldes. Die Chargenbewertungen wurden sortiert und die Partikelbewertungen wurden als Durchschnitt von 33 von 100 Chargen bestimmt. Die Idee war, basierend auf Aggressivität zu wählen. Die Partikel im oberen Drittel gewöhnen sich nur an die gewünschten Zahlenfolgen, was die Notwendigkeit eines konservativen Spiels einschränkt. Infolgedessen neigen sie dazu, das übliche Spiel an den Rand zu drängen und auf den nächsten "Stock" zu warten.

Mustersequenzen für 100 Chargen wurden vor dem PSO erzeugt und die gleichen Sequenzen wurden immer wieder verwendet. Dies war notwendig, um den Suchraum zu reparieren, damit die Lösungsoptionen miteinander verglichen werden konnten. Sequenzen wurden mit der Logik eines echten PRNG Nintendo Tetris erstellt, mit dem die Wahrscheinlichkeit verringert werden soll, dass Duplikate aufeinander folgen. PRNG weist jedoch auch Schwächen auf (siehe Abschnitt „Auswahl von Tetrimino“ aus einem früheren Artikel): Die Zahlen werden nicht gleichmäßig ausgewählt.

Erste Versuche führten dazu, dass Bots zu aggressiv agierten. Wenn sie das Plateau 19-28 überwunden haben, haben sie normalerweise die maximale Punktzahl erreicht. Leider führten sie oft zu früh zu Feldüberläufen. Als Reaktion darauf wurden vier Schritte unternommen, um die Bots zu „beruhigen“:

1. : Tetris, . «» . . ; 230 . , Tetris . Single, Double Triple. ; .
2. . , , 7 . .
3. , , . , 7 .
4. , , . , . , .

Nachdem alle diese Regeln angewendet wurden, um die Bots zu „beruhigen“, ergab die PSO-Methode die folgenden Gewichte:

Parameter	Gewicht
Gesamtzahl der gelöschten Zeilen	0,286127095297893900
Gesamte Blockierhöhe	1.701233676909959200
Gesamtzahl der Wellzellen	0,711304230768307700
Gesamtzahl der Tiefbrunnen	0,910665415998680400
Die Gesamtzahl der Löcher in den Spalten	1.879338064244357000
Gesamtgewichtete Säulenlöcher	2.168463848297177000
Gesamtzahl der Lochtiefen in Säulen	−0.265587111961757270
Minimale Tiefe des Säulenlochs	0,289886584949610500
Maximale Tiefe des Säulenlochs	0,362361055261181730
Die Gesamtzahl der Übergänge in Spalten	−0.028668795795469625
Total Line Jumps	0,874179981113233100
Gesamtsäulenhöhen	−0.507409683144361900
Haufenhöhe	−2.148676202831281000
Spaltenhöhenstreuung	−1.187558540281141700
Gesamtzahl der besetzten Zellen	−2.645656132241128000
Gesamtgewichtete Anzahl besetzter Zellen	0,242043416268706620
Säulenhöhen-Dispersion	0,287838126164431440

Da die Kette eine Kombination anstrebt, die die Bewertungsfunktion minimiert, können Parameter mit positivem Gewicht als Boni und die Reststrafen betrachtet werden. Die Gewichte zeigen jedoch nicht unbedingt die Bedeutung der entsprechenden Parameter; Sie sind nicht normalisiert und können daher nicht verglichen werden.

KI-Stärke

Um die Stärke der KI zu beurteilen, wurden ungefähr 1,7 Millionen Ergebnisse (in Punkten) von simulierten Spielen auf einem Plateau von 19 bis 28 gesammelt. Die Punktzahl spiegelt nicht das Spiel auf Stufe 29 oder höher wider und berücksichtigt keine Punkte, die durch sanften Abstieg erzielt wurden. Es enthält jedoch Spiele, die aufgrund von Feldüberläufen vorzeitig abgeschlossen wurden. Die Nintendo Tetris PRNG-Logik wurde verwendet, um die Tetrimino-Sequenzen zu erzeugen.

Unter diesen Ergebnissen ist die größte Punktzahl 1.313.600. Die minimale Punktzahl ist 0. Der

Durchschnitt liegt bei 816.379 und scheint klein zu sein. Wie unten erwähnt, sind die Daten jedoch verzerrt, sodass der Medianwert von 989.200 Punkten eine bessere Vorstellung vom typischen Wert gibt.

Wie oben angegeben, optimierte PSO die Gewichte basierend auf dem Durchschnitt des besten Drittels der Chargen. In diesem Fall beträgt die durchschnittliche Punktzahl des besten Drittels 1 108 860. Tatsächlich beträgt die durchschnittliche Punktzahl der besten 75% 1.000.000. Der

Bot hat eine Wahrscheinlichkeit von 47%, die Punktgrenze auf Stufe 29 zu erreichen. Es besteht eine Wahrscheinlichkeit von 61%, 900.000 Punkte auf die Stufe zu bringen 29. Die folgende Grafik zeigt die Wahrscheinlichkeiten für die Bewertung bis Stufe 29.


Es scheint, dass die Wahrscheinlichkeit linear auf etwa 900.000 Punkte abnimmt. Dann geht es in eine invertierte Sigmoidkurve.

Unten finden Sie ein geglättetes Histogramm mit der Anzahl der Parteien für jeden der erzielten Punkte. Seine Form wird durch die Ableitung des oben gezeigten Graphen bestimmt.


Wenn Sie die Schwankungen ignorieren, ist es bis zu ungefähr 900.000 flach und geht dann in eine Normalverteilung mit dem Zentrum um ungefähr 1.050.000 Punkte über. Die Gründe für die Schwankungen sind nicht klar. Es scheint, dass die Anzahl der Punkte es bevorzugt, in Schritten von 20.000 Punkten zu springen. Vielleicht liegt das am Haufenbauzyklus und am Erhalten von Tetris.

RAM- und ROM-Zuordnung

Um den CPU-Speicher zu manipulieren, Tastenklicks zu senden und Frame-Rendering-Ereignisse zu empfangen, verwendet das Plugin die Nintaco-API . Alle Speicheradressen wurden mit den Nintaco-Debugging-Tools ermittelt und Informationen zum Data Crystal ROMhacking.net-Wiki hinzugefügt . Im Quellcode sehen sie wie Konstanten in der Schnittstelle aus Addresses.

---

Referenzen

1. van den Bergh, F.; Engelbrecht, AP (2006)
   A study of particle swarm optimization particle trajectories
   In: Information Sciences 176 (2006) (pp. 937–971)
   Retrieved from http://researchspace.csir.co.za/dspace/bitstream/handle/10204/1155/van%20den%20bergh_2006_D.pdf