Mit künstlicher Intelligenz das 2048-Spiel lösen (JAVA-Code)

• 7. April 2014
• Vasilis Vryniotis
• . 6 Kommentare

Inzwischen haben die meisten von Ihnen das gehört / gespielt 2048 Spiel von Gabriele Cirulli. Es ist ein einfaches, aber sehr süchtig machendes Brettspiel, bei dem Sie die Anzahl der Zellen kombinieren müssen, um die Zahl 2048 zu erreichen. Wie erwartet steigt die Schwierigkeit des Spiels, wenn mehr Zellen mit hohen Werten gefüllt werden. Persönlich konnte ich, obwohl ich ziemlich viel Zeit mit dem Spielen des Spiels verbracht habe, 2048 nie erreichen. Daher ist es naheliegend, in JAVA einen KI-Löser zu entwickeln, um das Spiel 2048 zu schlagen. 🙂

In diesem Artikel werde ich kurz auf meinen Ansatz zum Erstellen des künstlichen Intelligenzlösers von Spiel 2048 eingehen, die von mir verwendeten Heuristiken beschreiben und den vollständigen Code bereitstellen, der in JAVA geschrieben ist. Der Code ist Open-Source unter der GPL v3-Lizenz und kann von heruntergeladen werden Github.

Entwicklung des 2048-Spiels in JAVA

Das ursprüngliche Spiel ist in JavaScript geschrieben, daher musste ich es von Grund auf in JAVA neu schreiben. Die Hauptidee des Spiels ist, dass Sie ein 4 × 4-Gitter mit ganzzahligen Werten haben, die alle Potenzen von 2 sind. Zellen mit dem Wert Null werden als leer betrachtet. Zu jedem Zeitpunkt während des Spiels können Sie die Werte in 4 Richtungen nach oben, unten, rechts oder links verschieben. Wenn Sie eine Bewegung ausführen, bewegen sich alle Werte des Gitters in diese Richtung und sie hören entweder auf, wenn sie die Grenzen des Gitters erreichen, oder wenn sie eine andere Zelle mit einem Wert ungleich Null erreichen. Wenn diese vorherige Zelle denselben Wert hat, werden die beiden Zellen zu einer Zelle mit doppeltem Wert zusammengeführt. Am Ende jeder Bewegung wird in einer der leeren Zellen ein zufälliger Wert in die Tafel eingefügt, dessen Wert entweder 2 mit einer Wahrscheinlichkeit von 0.9 oder 4 mit einer Wahrscheinlichkeit von 0.1 ist. Das Spiel endet, wenn es dem Spieler gelingt, eine Zelle mit dem Wert 2048 (Gewinn) zu erstellen, oder wenn keine anderen Züge zu machen sind (Verlust).

In der ursprünglichen Implementierung des Spiels ist der Move-Merge-Algorithmus etwas kompliziert, da er alle Richtungen berücksichtigt. Eine schöne Vereinfachung des Algorithmus kann durchgeführt werden, wenn wir die Richtung festlegen, in die wir die Teile kombinieren und das Brett entsprechend drehen können, um die Bewegung auszuführen. Maurits van der Schee hat kürzlich einen Artikel darüber geschrieben, der meiner Meinung nach einen Blick wert ist.

Alle Klassen sind mit Javadoc-Kommentaren dokumentiert. Im Folgenden finden Sie eine allgemeine Beschreibung der Architektur der Implementierung:

1. Board-Klasse

Die Brettklasse enthält den Hauptcode des Spiels, der für das Verschieben der Teile, das Berechnen der Punktzahl, das Überprüfen, ob das Spiel beendet ist usw. verantwortlich ist.

2. ActionStatus und Direction Enum

Der ActionStatus und die Richtung sind zwei wesentliche Aufzählungen, in denen das Ergebnis einer Bewegung und ihre Richtung entsprechend gespeichert werden.

3. ConsoleGame-Klasse

Das ConsoleGame ist die Hauptklasse, mit der wir das Spiel spielen und die Genauigkeit des AI Solver testen können.

4. AIsolver-Klasse

Der AIsolver ist die Hauptklasse des Moduls für künstliche Intelligenz, das für die Bewertung des nächstbesten Zugs bei einem bestimmten Board verantwortlich ist.

Techniken der künstlichen Intelligenz: Minimax vs. Alpha-Beta-Schnitt

Es wurden verschiedene Ansätze veröffentlicht, um dieses Spiel automatisch zu lösen. Am bemerkenswertesten ist das von Matt Overlan. Um das Problem zu lösen, habe ich zwei verschiedene Ansätze ausprobiert, den Minimax-Algorithmus und den Alpha-Beta-Schnitt.

Minimax-Algorithmus

Das Minimax ist ein rekursiver Algorithmus, der zum Lösen von Nullsummenspielen für zwei Spieler verwendet werden kann. In jedem Zustand des Spiels ordnen wir einen Wert zu. Der Minimax-Algorithmus durchsucht den Raum möglicher Spielzustände und erstellt einen Baum, der erweitert wird, bis er eine bestimmte vordefinierte Tiefe erreicht. Sobald diese Blattzustände erreicht sind, werden ihre Werte verwendet, um diejenigen der Zwischenknoten zu schätzen.

Die interessante Idee dieses Algorithmus ist, dass jedes Level den Zug eines der beiden Spieler darstellt. Um zu gewinnen, muss jeder Spieler den Zug auswählen, der die maximale Auszahlung des Gegners minimiert. Hier ist eine schöne Videopräsentation des Minimax-Algorithmus:

[Eingebetteten Inhalt]

Unten sehen Sie den Pseudocode des Minimax-Algorithmus:

Funktion Minimax (Knoten, Tiefe, Maximierung der Ebene)
    if Tiefe = 0 or Knoten ist ein Endknoten
        Rückkehr der heuristische Wert des Knotens
    if maximizingPlayer bestValue: = -∞
        für jede Kind des Knotens val: = minimax (Kind, Tiefe - 1, FALSE)) bestValue: = max (bestValue, val);
        Rückkehr Bestwert
    sonst
        bestValue: = + ∞
        für jede Kind des Knotens val: = minimax (Kind, Tiefe - 1, WAHR)) bestValue: = min (bestValue, val);
        Rückkehr Bestwert
(* Erster Aufruf zur Maximierung des Spielers *)
Minimax (Ursprung, Tiefe, WAHR)

Alpha-Beta-Schnitt

Das Alpha-Beta-Bereinigungsalgorithmus ist eine Erweiterung von minimax, die die Anzahl der Knoten, die ausgewertet / erweitert werden müssen, stark verringert (beschneidet). Um dies zu erreichen, schätzt der Algorithmus zwei Werte, den Alpha und den Beta. Wenn in einem bestimmten Knoten das Beta kleiner als das Alpha ist, können die restlichen Teilbäume beschnitten werden. Hier ist eine schöne Videopräsentation des Alphabet-Algorithmus:

[Eingebetteten Inhalt]

Unten sehen Sie den Pseudocode des Alpha-Beta-Bereinigungsalgorithmus:

Funktion Alphabet (Knoten, Tiefe, α, β, maximierende Schicht)
    if Tiefe = 0 or Knoten ist ein Endknoten
        Rückkehr der heuristische Wert des Knotens
    if Maximierung des Spielers
        für jede Kind des Knotens α: = max (α, Alphabet (Kind, Tiefe - 1, α, β, FALSE))
            if β ≤ α
                brechen (* β-Cut-Off *)
        Rückkehr α
    sonst
        für jede Kind des Knotens β: = min (β, Alphabet (Kind, Tiefe - 1, α, β, WAHR))
            if β ≤ α
                brechen (* α Cut-Off *)
        Rückkehr β
(* Erstanruf *)
Alphabet (Ursprung, Tiefe, -∞, + ∞, WAHR)

Wie wird KI verwendet, um das Spiel 2048 zu lösen?

Um die obigen Algorithmen verwenden zu können, müssen wir zuerst die beiden Spieler identifizieren. Der erste Spieler ist die Person, die das Spiel spielt. Der zweite Spieler ist der Computer, der zufällig Werte in die Zellen des Bretts einfügt. Offensichtlich versucht der erste Spieler, seine Punktzahl zu maximieren und die Zusammenführung von 2048 zu erreichen. Andererseits ist der Computer im ursprünglichen Spiel nicht speziell so programmiert, dass er den Benutzer blockiert, indem er den für ihn schlechtesten Zug auswählt, sondern fügt zufällig Werte in die leeren Zellen ein.

Warum verwenden wir also KI-Techniken, die Nullsummenspiele lösen und die speziell davon ausgehen, dass beide Spieler den bestmöglichen Zug für sie auswählen? Die Antwort ist einfach; Trotz der Tatsache, dass nur der erste Spieler versucht, seine Punktzahl zu maximieren, kann die Auswahl des Computers den Fortschritt blockieren und den Benutzer daran hindern, das Spiel zu beenden. Indem wir das Verhalten des Computers als orthologischer, nicht zufälliger Spieler modellieren, stellen wir sicher, dass unsere Wahl unabhängig von dem, was der Computer spielt, solide ist.

Der zweite wichtige Teil besteht darin, den Zuständen des Spiels Werte zuzuweisen. Dieses Problem ist relativ einfach, da das Spiel selbst uns eine Punktzahl gibt. Leider ist es kein guter Ansatz, die Punktzahl alleine zu maximieren. Ein Grund dafür ist, dass die Position der Werte und die Anzahl der leeren Zellen sehr wichtig sind, um das Spiel zu gewinnen. Wenn wir beispielsweise die großen Werte in entfernte Zellen streuen, ist es für uns sehr schwierig, sie zu kombinieren. Wenn wir keine leeren Zellen zur Verfügung haben, riskieren wir außerdem, das Spiel jeden Moment zu verlieren.

Aus all den oben genannten Gründen mehrere Heuristiken wurden vorgeschlagen wie die Monotizität, die Glätte und die freien Kacheln des Bretts. Die Hauptidee besteht nicht darin, die Punktzahl allein zur Bewertung jedes Spielzustands zu verwenden, sondern stattdessen eine heuristische zusammengesetzte Punktzahl zu erstellen, die die oben genannten Punkte enthält.

Schließlich sollten wir beachten, dass, obwohl ich eine Implementierung des Minimax-Algorithmus entwickelt habe, die große Anzahl möglicher Zustände den Algorithmus sehr langsam macht und daher ein Beschneiden erforderlich ist. Als Ergebnis der JAVA-Implementierung verwende ich die Erweiterung des Alpha-Beta-Bereinigungsalgorithmus. Außerdem beschneide ich im Gegensatz zu anderen Implementierungen die Auswahl des Computers nicht aggressiv mit willkürlichen Regeln, sondern berücksichtige sie alle, um den bestmöglichen Zug des Spielers zu finden.

Entwicklung einer heuristischen Score-Funktion

Um das Spiel zu schlagen, habe ich verschiedene heuristische Funktionen ausprobiert. Das, was ich am nützlichsten fand, ist das Folgende:

private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
     int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore);
     return Math.max(score, Math.min(actualScore, 1));
}

Die obige Funktion kombiniert die tatsächliche Punktzahl der Tafel, die Anzahl der leeren Zellen / Kacheln und eine Metrik namens Clustering-Punktzahl, die wir später diskutieren werden. Sehen wir uns jede Komponente genauer an:

1. Tatsächliche Punktzahl: Aus offensichtlichen Gründen müssen wir bei der Berechnung des Werts eines Boards dessen Punktzahl berücksichtigen. Boards mit höheren Punktzahlen werden im Allgemeinen im Vergleich zu Boards mit niedrigeren Punktzahlen bevorzugt.
2. Anzahl der leeren Zellen: Wie bereits erwähnt, ist es wichtig, nur wenige leere Zellen zu behalten, um sicherzustellen, dass wir das Spiel in den nächsten Zügen nicht verlieren. Board-Zustände mit mehr leeren Zellen werden im Allgemeinen im Vergleich zu anderen mit weniger Zellen bevorzugt. Es stellt sich die Frage, wie wir diese leeren Zellen bewerten würden. In meiner Lösung gewichte ich sie mit dem Logarithmus der tatsächlichen Punktzahl. Dies hat folgenden Effekt: Je niedriger die Punktzahl, desto weniger wichtig ist es, viele leere Zellen zu haben (dies liegt daran, dass das Kombinieren der Zellen zu Beginn des Spiels ziemlich einfach ist). Je höher die Punktzahl, desto wichtiger ist es sicherzustellen, dass wir leere Zellen in unserem Spiel haben (Dies liegt daran, dass es am Ende des Spiels wahrscheinlicher ist, dass wir verlieren, weil keine leeren Zellen vorhanden sind.
3. Clustering-Score: Wir verwenden den Clustering-Score, der misst, wie verstreut die Werte unseres Boards sind. Wenn Zellen mit ähnlichen Werten nahe beieinander liegen, lassen sie sich leichter kombinieren, was bedeutet, dass es schwieriger ist, das Spiel zu verlieren. In diesem Fall hat der Clustering-Score einen niedrigen Wert. Wenn die Werte der Tafel verstreut sind, erhält diese Punktzahl einen sehr großen Wert. Diese Punktzahl wird von den beiden vorherigen Punktzahlen abgezogen und wirkt wie eine Strafe, die sicherstellt, dass Clustered Boards bevorzugt werden.

In der letzten Zeile der Funktion stellen wir sicher, dass die Punktzahl nicht negativ ist. Die Punktzahl sollte streng positiv sein, wenn die Punktzahl der Tafel positiv ist, und nur dann Null, wenn die Tafel der Punktzahl Null ist. Die Funktionen max und min sind so aufgebaut, dass wir diesen Effekt erhalten.

Schließlich sollten wir beachten, dass wir, wenn der Spieler einen Endspielstatus erreicht und keine Züge mehr erlaubt sind, die obige Punktzahl nicht verwenden, um den Wert des Status zu schätzen. Wenn das Spiel gewonnen ist, weisen wir den höchstmöglichen ganzzahligen Wert zu, während wir bei Verlust des Spiels den niedrigsten nicht negativen Wert zuweisen (0 oder 1 mit ähnlicher Logik wie im vorherigen Absatz).

Mehr zum Clustering Score

Wie bereits erwähnt, misst der Clustering-Score, wie stark die Werte des Boards verstreut sind, und wirkt wie eine Strafe. Ich habe diese Partitur so konstruiert, dass sie Tipps / Regeln von Benutzern enthält, die das Spiel „gemeistert“ haben. Die erste vorgeschlagene Regel lautet, dass Sie versuchen, die Zellen mit ähnlichen Werten nahe beieinander zu halten, um sie einfacher zu kombinieren. Die zweite Regel lautet, dass Zellen mit hohem Wert nahe beieinander liegen und nicht in der Mitte des Bretts, sondern an den Seiten oder Ecken erscheinen sollten.

Mal sehen, wie der Clustering-Score geschätzt wird. Für jede Zelle der Tafel schätzen wir die Summe der absoluten Unterschiede zu ihren Nachbarn (ohne die leeren Zellen) und nehmen die durchschnittliche Differenz. Der Grund, warum wir die Durchschnittswerte verwenden, besteht darin, zu vermeiden, dass die Wirkung zweier Nachbarzellen mehr als einmal gezählt wird. Die Gesamt-Clustering-Punktzahl ist die Summe aller dieser Durchschnittswerte.

Der Clustering Score weist die folgenden Attribute auf:

1. Es erhält einen hohen Wert, wenn die Werte der Platine verstreut sind, und einen niedrigen Wert, wenn Zellen mit ähnlichen Werten nahe beieinander liegen.
2. Es überwiegt nicht die Wirkung von zwei Nachbarzellen.
3. Zellen an den Rändern oder Ecken haben weniger Nachbarn und damit niedrigere Werte. Wenn die hohen Werte in der Nähe der Ränder oder Ecken platziert werden, haben sie daher geringere Punktzahlen und daher ist die Strafe geringer.

Die Genauigkeit des Algorithmus

Wie erwartet hängt die Genauigkeit (auch bekannt als Prozentsatz der gewonnenen Spiele) des Algorithmus stark von der von uns verwendeten Suchtiefe ab. Je höher die Suchtiefe, desto genauer und desto länger dauert die Ausführung. In meinen Tests dauert eine Suche mit einer Tiefe von 3 weniger als 0.05 Sekunden, ergibt jedoch eine Gewinnchance von 20%, eine Tiefe von 5 dauert etwa 1 Sekunde, bietet jedoch eine Gewinnchance von 40% und eine Tiefe von 7 dauert 27 bis 28 Sekunden und gibt ungefähr 70-80% Gewinnchance.

Zukünftige Erweiterungen

Für diejenigen unter Ihnen, die daran interessiert sind, den Code hier zu verbessern, gibt es einige Dinge, die Sie untersuchen können:

1. Geschwindigkeit verbessern: Wenn Sie die Geschwindigkeit des Algorithmus verbessern, können Sie eine größere Tiefe verwenden und so eine bessere Genauigkeit erzielen.
2. Grafiken erstellen: Es gibt einen guten Grund, warum die Implementierung von Gabriele Cirulli so berühmt wurde. Es sieht gut aus! Ich habe mir nicht die Mühe gemacht, eine GUI zu entwickeln, sondern die Ergebnisse auf der Konsole auszudrucken, was es schwieriger macht, dem Spiel zu folgen und es zu spielen. Das Erstellen einer schönen GUI ist ein Muss.
3. Tune-Heuristiken: Wie bereits erwähnt, haben mehrere Benutzer unterschiedliche Heuristiken vorgeschlagen. Man kann mit der Art und Weise experimentieren, wie die Punktzahlen berechnet werden, die Gewichte und die Brettmerkmale, die berücksichtigt werden. Mein Ansatz zur Messung des Cluster-Scores soll andere Vorschläge wie Monotonie und Glätte kombinieren, aber es gibt noch Raum für Verbesserungen.
4. Einstellen der Tiefe: Man kann auch versuchen, die Suchtiefe je nach Spielstatus einzustellen / anzupassen. Auch können Sie die verwenden Iterative Vertiefung der Tiefensuche Algorithmus, von dem bekannt ist, dass er den Alpha-Beta-Bereinigungsalgorithmus verbessert.

Vergessen Sie nicht, den JAVA-Code von herunterzuladen Github und experimentieren. Ich hoffe dir hat dieser Beitrag gefallen! Wenn Sie dies getan haben, nehmen Sie sich bitte einen Moment Zeit, um den Artikel auf Facebook und Twitter zu teilen. 🙂