Was ist der Optimale Algorithmus für das Spiel 2048?
Einführung
2048 ist ein aufregendes Kachelverschiebungsspiel, bei dem wir Kacheln verschieben, um sie zu kombinieren, um immer größere Kachelwerte zu erzielen.
In diesem Tutorial werden wir einen Algorithmus zum Spielen von 2048 untersuchen, der bei der Entscheidung über die besten Züge bei jedem Schritt hilft, um die beste Punktzahl zu erzielen.
Spielanleitung 2048
Ein Spiel von 2048 wird auf einem 4×4-Brett gespielt., Jede Position auf dem Brett kann leer sein oder eine Kachel enthalten, und auf jeder Kachel befindet sich eine Nummer.
Wenn wir anfangen, hat das Brett zwei Kacheln an zufälligen Stellen, von denen jedes entweder eine „2“ oder eine „4“ hat – jeder hat eine unabhängige 10% ige Chance, eine „4“ zu sein, oder sonst a ist eine „2“.
Bewegungen werden ausgeführt, indem alle Kacheln zu einer Kante verschoben werden – nach oben, unten, links oder rechts., Wenn Sie dies tun, werden alle Kacheln mit demselben Wert, die nebeneinander liegen und sich zusammen bewegen, zusammengeführt und erhalten eine neue Kachel, die der Summe der beiden vorherigen entspricht:
Nachdem wir einen Zug gemacht haben, wird eine neue Kachel auf das Brett gelegt. Dies wird an einer zufälligen Stelle platziert und ist eine „2“ oder eine „4“ auf die gleiche Weise wie die anfänglichen Kacheln – „2“ 90% der Zeit und „4“ 10% der Zeit.
Das Spiel geht dann weiter, bis keine Züge mehr möglich sind.
Im Allgemeinen besteht das Ziel des Spiels darin, eine einzelne Kachel mit dem Wert „2048“zu erreichen., Das Spiel hört hier jedoch nicht auf und wir können so weit wie möglich weiterspielen, um das größtmögliche Plättchen zu erreichen. Theoretisch ist dies eine Kachel mit dem Wert „131,072“.
Problem Erklärung
Das Lösen dieses Spiels ist ein interessantes Problem, da es eine zufällige Komponente hat. Es ist unmöglich, nicht nur richtig vorherzusagen, wo jede neue Kachel platziert wird, sondern auch, ob es sich um eine „2“ oder eine „4“handelt.
Als solches ist es unmöglich, einen Algorithmus zu haben, der das Rätsel jedes Mal korrekt löst., Das Beste, was wir tun können, ist zu bestimmen, was wahrscheinlich in jeder Phase der beste Zug ist, und das Wahrscheinlichkeitsspiel zu spielen.
An jedem Punkt gibt es nur vier mögliche Züge, die wir machen können. Manchmal haben einige dieser Züge keinen Einfluss auf das Brett und sind daher nicht wert – zum Beispiel hat ein Zug von „Down“ in dem obigen Brett keinen Einfluss, da sich alle Kacheln bereits am unteren Rand befinden.
Die Herausforderung besteht dann darin zu bestimmen, welcher dieser vier Züge derjenige sein wird, der das beste langfristige Ergebnis hat.,
Unser Algorithmus basiert auf dem Expectimax-Algorithmus, der selbst eine Variation des Minimax-Algorithmus ist, bei dem die möglichen Routen durch unseren Baum jedoch mit der Wahrscheinlichkeit gewichtet werden, dass sie auftreten.
Im Wesentlichen behandeln wir das Spiel als Zwei-Spieler-Spiel:
- Spieler Eins – der menschliche Spieler-kann das Brett in eine von vier Richtungen verschieben
- Spieler Zwei – der Computerspieler-kann eine Kachel an einer leeren Stelle auf dem Brett platzieren
Auf dieser Grundlage können wir aus jedem Zug einen Baum von Ergebnissen generieren, gewichtet durch die Wahrscheinlichkeit, dass jeder Zug stattfindet., Dies kann uns dann die Details geben, die erforderlich sind, um festzustellen, welche menschliche Bewegung wahrscheinlich das beste Ergebnis liefert.
3.1. Flussdiagramm des Gameplays
Der allgemeine Ablauf der Funktionsweise des Gameplays:
Wir können den zufälligen Aspekt des Spiels sofort im Prozess „Zufällige Kachel hinzufügen“ sehen – sowohl in der Tatsache, dass wir ein zufälliges Quadrat zum Hinzufügen der Kachel finden, als auch in der Auswahl eines zufälligen Werts für die Kachel.
Unsere Herausforderung besteht dann darin, im Schritt „Nächsten Zug bestimmen“ zu entscheiden, was zu tun ist. Dies ist unser Algorithmus, um das Spiel zu spielen.,
Der allgemeine Überlauf davon scheint täuschend einfach zu sein:
Wir müssen nur jede der möglichen Bewegungen simulieren, bestimmen, welche das beste Ergebnis liefert, und dann verwenden.
Daher haben wir unseren Algorithmus jetzt darauf reduziert, eine bestimmte Bewegung zu simulieren und eine Punktzahl für das Ergebnis zu generieren.
Dies ist ein zweiteiliger Prozess. Der erste Durchgang besteht darin, zu sehen, ob der Zug überhaupt möglich ist, und wenn nicht, brechen Sie ihn früh mit einer Punktzahl von „0“ab., Wenn der Umzug möglich ist, fahren wir mit dem realen Algorithmus fort, in dem wir bestimmen, wie gut ein Umzug ist:
3.2. Bestimmen des nächsten Zuges
Der Schlüsselteil unseres Algorithmus besteht bisher darin, einen Zug zu simulieren, und der Schlüsselteil davon ist, wie wir für jeden möglichen Zug eine Punktzahl generieren. Hier kommt unser Expectimax-Algorithmus ins Spiel.
Wir simulieren jede mögliche Bewegung von beiden Spielern für mehrere Schritte und sehen, welche davon das beste Ergebnis liefert. Für den menschlichen Spieler bedeutet dies, dass sich jeder der Bewegungen“ oben“,“ unten“,“ links „und“ rechts “ bewegt.,
Für den Computerspieler bedeutet dies, sowohl eine „2“ – als auch eine „4“ – Kachel an jeder möglichen leeren Stelle zu platzieren:
Dieser Algorithmus ist rekursiv, wobei jeder rekursive Schritt nur dann gestoppt wird, wenn er eine bestimmte Tiefe von der tatsächlichen Bewegung im realen Spiel hat.,eine Punktzahl für das aktuell simulierte Board-Layout erstellen
- Simulieren Sie jede mögliche menschliche Bewegung
- Für jede dieser
- Kehren Sie zurück in den Algorithmus
- Geben Sie die aus dieser menschlichen Bewegung berechnete Punktzahl zurück
- Fügen Sie die von dieser Computerbewegung berechnete Punktzahl hinzu, gewichtet mit der Wahrscheinlichkeit, dass diese Bewegung stattfindet
Wenn wir damit fertig sind, addieren wir alle berechneten Punkte, und dies ist das Endergebnis für den Zug, den wir vom aktuellen Spielbrett aus machen möchten., Da wir dies viermal tun – eine für jeden möglichen Zug vom aktuellen Spielbrett–, erhalten wir vier Punkte, und die höchste davon ist der Zug, den wir machen müssen.
3.3. Scoring einer Board-Position
Zu diesem Zeitpunkt ist nur noch eine Punktzahl für ein Board zu berechnen. Dies ist nicht die gleiche Wertung wie das Spiel verwendet, aber es muss berücksichtigt werden, wie gut eine Position dies ist, um weiter zu spielen.
Es gibt eine Vielzahl von Möglichkeiten, dies durch Addition mehrerer Faktoren zusammen mit entsprechenden Gewichtungen zu erreichen., Zum Beispiel:
- Anzahl leerer Stellen
- Anzahl möglicher Zusammenführungen-d. H., wie oft sich dieselbe Zahl an zwei benachbarten Stellen befindet
- Der größte Wert an einem beliebigen Ort
- Summe aller Standorte
- Monotonie des Boards – so gut ist das Board strukturiert, dass Standortwerte in einer einzigen Richtung zunehmen.
Pseudocode
Nun, da wir wissen, wie der Algorithmus funktionieren wird, wie sieht das aus? Lassen Sie uns einen Pseudocode untersuchen, der den Algorithmus genauer beschreibt.,
Wir interessieren uns nicht für das eigentliche Spielen des Spiels, nur für den Algorithmus zum Bestimmen von Zügen, also fangen wir dort an:
Nach wie vor kommen wir zu dem Punkt, an dem wir jede der möglichen Bewegungen vom Startbrett simulieren und die zurückgeben, die am besten punktet. Dadurch müssen wir Punkte für die neu simulierten Boards generieren.
Wir haben ein Tiefenlimit hinzugefügt, damit wir die Verarbeitung nach einer Weile stoppen können., Da wir mit einem rekursiven Algorithmus arbeiten, brauchen wir eine Möglichkeit, ihn zu stoppen, da er sonst möglicherweise für immer ausgeführt wird:
Dies gibt uns unsere Rekursion, simuliert jede mögliche Bewegung von Mensch und Computer für eine bestimmte Anzahl von Schritten und entscheidet, welche menschlichen Bewegungen das bestmögliche Ergebnis liefern.
Das einzige, was übrig bleibt, ist ein Endergebnis für eine bestimmte Brettposition zu erarbeiten. Es gibt keinen perfekten Algorithmus dafür, und verschiedene Faktoren führen zu unterschiedlichen Ergebnissen.,
Leistungsoptimierung
Bisher haben wir einen Algorithmus, der versucht, das Spiel zu lösen, aber es ist nicht so effizient wie es sein könnte. Aufgrund der Zufälligkeit des Spiels ist es unmöglich, einen perfekt optimierten Löser zu haben – es wird immer ein gewisses Maß an Wiederholung geben, einfach wegen der Art des Prozesses.
Wir können zumindest unser Bestes tun, um die Arbeit zu reduzieren, die wir jedoch nicht benötigen.,
Wir optimieren bereits ein wenig im obigen Algorithmus, indem wir keine Züge verarbeiten, die keinen Einfluss auf das Spiel haben. Es gibt jedoch andere Möglichkeiten, die zu erledigende Arbeit zu reduzieren, z. B. die kumulative Wahrscheinlichkeit von Bewegungen zu verfolgen und anzuhalten, wenn dies zu niedrig wird. Dies hat das Risiko, die perfekte Lösung zu entfernen, aber wenn die Wahrscheinlichkeit so gering ist, dann wird es mit ziemlicher Sicherheit sowieso nicht passieren.
Wir können auch dynamisch bestimmen die tiefe grenze zu arbeiten mit., Unser obiger Pseudocode hat ein hartcodiertes Limit von 3, aber wir könnten dies dynamisch basierend auf der Form des Boards zu Beginn unserer Berechnungen berechnen – zum Beispiel auf die Anzahl der leeren Quadrate oder die Anzahl der verschiedenen Kacheln auf dem Board. Dies würde bedeuten, dass wir weniger Bewegungen von Boards durchlaufen, die weniger Spielraum für Erweiterungen haben.
Da es außerdem möglich ist, dieselben Board-Positionen mehrmals zu überprüfen, können wir uns diese merken und die Punktzahl für diese Positionen zwischenspeichern, anstatt sie jedes Mal neu zu berechnen., Möglicherweise können wir jede mögliche Brettposition im Voraus generieren, aber es gibt eine große Anzahl davon – 281.474.976.710.656 verschiedene mögliche Brettpositionen mit Kacheln bis 2048–, sodass dies wahrscheinlich nicht möglich ist.
Die wichtigste Optimierung, die wir durchführen können, ist jedoch die Anpassung des Algorithmus zum Generieren von Board-Scores. Dies entscheidet darüber, wie gut Board für das weitere Spielen ist, und die Faktoren und Gewichtungen, die wir dafür verwenden, hängen direkt damit zusammen, wie gut sich unser Algorithmus abspielt.,
Fazit
2048 ist ein äußerst interessantes Spiel zu lösen. Es gibt keinen perfekten Weg, es zu lösen, aber wir können Heuristiken schreiben, die nach den bestmöglichen Routen durch das Spiel suchen.
Die gleichen allgemeinen Prinzipien funktionieren für jedes Zwei-Spieler – Spiel – zum Beispiel Schach -, bei dem Sie nicht mit Sicherheit vorhersagen können, was der andere Spieler tun wird.
Warum nicht versuchen, eine Implementierung davon zu schreiben und zu sehen, wie gut es funktioniert?