"2048" in ein paar Wochen markiert 5 Jahre, was bedeutet, dass es Zeit ist, etwas zu schreiben, das diesem wunderbaren Spiel gewidmet ist.
Das Thema eines unabhängigen Spiels der künstlichen Intelligenz in einem Puzzle ist besonders informativ. Es gibt verschiedene Möglichkeiten, dies zu implementieren, und heute werden wir eine relativ einfache analysieren. Wir werden dem Computergeist nämlich beibringen, mit der Monte-Carlo-Methode Zweiergrade zu sammeln.
Dieser Artikel wurde mit Unterstützung von EDISON Software verfasst, einem Unternehmen, das mobile Anwendungen entwickelt und Softwaretestservices anbietet .
Die Inspiration für diese Arbeit war eine Diskussion über Stackoverflow, in der
kluge Jungs effektive Wege für ein Computerspiel vorschlugen . Anscheinend ist der beste Weg die Minimax-Methode mit Alpha-Beta-Clipping, und in ein paar Tagen wird die nächste Veröffentlichung ihr gewidmet sein.
Vom Stackoverflow-Benutzer vorgeschlagene Casino-Methode
Ronenz als Teil der obigen Diskussion. Der gesamte nächste Abschnitt ist eine Übersetzung aus seiner Veröffentlichung.
Monte-Carlo-Methode
Ich interessierte mich für die Idee der KI für dieses Spiel, in dem
es keine fest codierte Intelligenz gibt (dh es gibt keine Heuristiken, Punkte usw.). KI sollte nur die Spielregeln „kennen“ und das Spiel „verstehen“. Dies unterscheidet es von den meisten AIs (wie in diesem Thread), da das Gameplay in der Tat Brute Force ist, die von der Scoring-Funktion gesteuert wird und das menschliche Verständnis des Spiels widerspiegelt.
AI-Algorithmus
Ich habe einen einfachen, aber überraschend guten Spielalgorithmus gefunden: Um den nächsten Zug für einen bestimmten Feldzustand zu bestimmen, spielt die KI das Spiel im RAM und macht
zufällige Züge, bis das Spiel mit einer Niederlage endet. Dies wird mehrmals durchgeführt, wobei das Endergebnis verfolgt wird. Dann wird die durchschnittliche Endpunktzahl unter Berücksichtigung des Anfangskurses berechnet. Der erste Zug, der das höchste durchschnittliche Ergebnis zeigte, wird als bereits tatsächlich gewählter Zug ausgewählt.
Mit 100 Läufen für jede erste Runde erreicht die KI in 80% der Fälle 2048 und in 50% der Fälle 4096. Bei Verwendung von 10.000 Läufen wird in 100% der Fälle 2048 erhalten, bei 4096 70% und bei 8192 etwa 1%.
In Aktion anzeigenDas beste erzielte Ergebnis zeigt der Screenshot:
Eine interessante Tatsache für diesen Algorithmus ist, dass Spiele mit zufällig ausgeführten Zügen zwar ziemlich schlecht sein dürften, die Auswahl des besten (oder am wenigsten schlechten, wenn Sie möchten) Zugs jedoch zu einem sehr guten Gameplay führt: Ein typisches Monte-Carlo-KI-Spiel kann 70.000 Punkte erzielen Punkte für 3000 Züge, aber Spiele mit einem beliebigen Spiel im Speicher von einer bestimmten Position aus ergeben durchschnittlich 340 zusätzliche Punkte für etwa 40 zusätzliche Züge, bevor sie verlieren. (Sie können dies selbst überprüfen, indem Sie die KI starten und die Debug-Konsole öffnen.)
Diese Grafik veranschaulicht dieses Konzept: Die blaue Linie zeigt die Punktzahl des Spiels nach jedem Zug. Die rote Linie zeigt das
beste Ergebnis des Algorithmus und bewegt sich willkürlich von dieser Position bis zum Ende des Spiels. Tatsächlich „ziehen“ die roten Werte die blauen nach oben, da sie die besten Sätze des Algorithmus sind. Interessanterweise liegt die rote Linie an jedem Punkt leicht über der blauen Linie, aber die blaue Linie verringert die Lücke immer mehr.
Ich finde es ziemlich überraschend, dass der Algorithmus nicht unbedingt ein gutes Gameplay vorwegnimmt und dennoch die Bewegungen auswählt, die ihn erzeugen (ein guter Prozess).
Später entdeckte ich, dass diese Methode als
Monte-Carlo-Baumsuchalgorithmus klassifiziert werden kann.
Implementierung und Links
Zuerst habe ich eine JavaScript-Version erstellt, die hier
in Aktion zu
sehen ist . Diese Version kann 100 Läufe in angemessener Zeit ausführen. Öffnen Sie die Konsole für weitere Informationen. (
Quelle )
Später habe ich zum Herumspielen die hochoptimierte @ nneonneo-Infrastruktur verwendet und meine Version in C ++ implementiert. Diese Version erlaubt bis zu 100.000 Läufe pro Runde und sogar 1.000.000, wenn Sie bereit sind zu warten. Montageanleitung enthalten. Alles funktioniert in der Konsole und verfügt auch über eine Fernbedienung für die Wiedergabe in der Webversion. (
Quelle )
Ergebnisse
Überraschenderweise verbessert eine Erhöhung der Anzahl der Läufe das Gameplay nicht grundlegend. Es scheint, dass diese Strategie ein Limit von 80.000 Punkten mit einem Plättchen von 4096 und allen kleineren Ergebnissen hat, die sehr nahe am Erreichen von Plättchen 8192 liegen. Eine Erhöhung der Anzahl der Läufe von 100 auf 100.000 erhöht die Chancen, dieses Limit zu erreichen (von 5% auf 40%), aber nicht überwindet es.
Die Durchführung von 10.000 Läufen mit einer vorübergehenden Erhöhung von bis zu 1.000.000 in der Nähe kritischer Positionen ermöglichte es, diese Barriere in weniger als 1% der Fälle mit der maximalen Punktzahl von 129892 und den Kacheln 8192 zu überwinden.
Verbesserungen und Optimierungen
Nach der Implementierung dieses Algorithmus habe ich viele Verbesserungen versucht, einschließlich der Verwendung von minimalen oder maximalen Bewertungen oder einer Kombination aus minimalen, maximalen und durchschnittlichen Werten. Ich habe auch versucht, die Tiefe zu verwenden: Anstatt zu versuchen, K Läufe pro Runde abzuschließen, habe ich K Züge pro Liste von Zügen einer bestimmten Länge versucht (z. B. „hoch, hoch, links“) und den ersten Zug aus der Liste der Züge mit dem besten Gewinn ausgewählt.
Später implementierte ich einen Punktebaum, der die bedingte Wahrscheinlichkeit berücksichtigte, dass er einen Zug nach einer bestimmten Liste von Zügen ausführen kann.
Keine dieser Ideen zeigte jedoch einen echten Vorteil gegenüber einer einfachen ersten Idee. Ich habe auskommentierten Code für diese Ideen in der C ++ - Quelle hinterlassen.
Ich habe den Deep Search-Mechanismus hinzugefügt, der die Anzahl der Läufe vorübergehend auf 1.000.000 erhöhte, wenn einer der Läufe versehentlich die nächsthöhere Kachel erreichte. Dies führte zu einer Verbesserung der Zeitleistung.
Es würde mich interessieren, ob jemand andere Verbesserungsideen hat, die die Unabhängigkeit der KI vom Themenbereich unterstützen.
Optionen und Klone 2048
Zum Spaß habe ich die KI auch als Lesezeichen implementiert und sie mit den Steuerelementen des Spiels verbunden. Auf diese Weise können Sie sowohl mit dem Originalspiel als auch mit vielen seiner Variationen arbeiten.
Dies ist aufgrund der domänenunabhängigen Natur der KI möglich. Einige der Optionen sind recht originell, z. B. ein hexagonaler Klon.
2048.xlsm
Die Excel-Anwendung selbst
kann von Google heruntergeladen werden .
Das Bild kann angeklickt werden - ein Bild in voller Größe wird geöffnet.
Kurz auf die Oberfläche und Funktionalität der Anwendung.
Um mit dem Spielen zu beginnen, müssen Sie auf die Schaltfläche "
Benutzer: Spiel starten " klicken. Wenn Sie diese Taste erneut drücken, ändert sich die Beschriftung von "
Benutzer: Spiel starten " zu "
Benutzer: Spiel beenden " und umgekehrt, dh Sie können das Spiel jederzeit stoppen und dann erneut starten. Wenn das Spiel stoppt, können Sie die Ausrichtung auf dem Spielfeld manuell ändern und Ihre Position verbessern oder verschlechtern, um einige Ideen zu testen oder zu verifizieren.
Während des Spiels können Sie auf zwei Arten Züge machen:
- Tastatur: einfach durch Drücken der Tasten "hoch", "runter", "links", "rechts".
- Mit der Maus: Klicken Sie auf Zellen mit großen Pfeilen, die die gewünschte Richtung angeben.
Die Schaltfläche "
Neues Feld " löscht das Spielfeld und platziert zufällig die "zwei" und "vier" darauf.
Das Interessanteste ist, dass die Monte-Carlo-Methode genau in der Form implementiert wurde, in der sie vom Typ mit Stackoverflow vorgeschlagen wurde. An jeder Position durchläuft der Computer im Speicher bei jeder ersten Bewegung zufällige Verzweigungen („auf“, „ab“, „links“, „rechts“), bis dies zu einem Verlust führt. Statistisch gesehen ist die günstigste Richtung in einer speziellen Tabelle unten rot hervorgehoben. Sie können es als Hinweis verwenden, wenn Sie sehen, dass Ihr eigenes Spiel zum Stillstand kommt und Sie sich irgendwie retten müssen. ;)
Über der Tabelle befinden sich Kontrollkästchen mit Analyseoptionen. Momentan wurde nur Monte Carlo entschieden, der Rest wird in den kommenden Tagen hinzugefügt (aufgrund dessen wird es mehr Harastas mit der Aktualisierung der Excel-Anwendung und Erklärungen der Theorie geben).
Es gibt auch einen
AI: Game- Button. Wenn Sie darauf klicken, führt der Computerassistent eine Bewegung gemäß der Monte-Carlo-Methode oder einer anderen in der Switch-Gruppe ausgewählten Methode aus (Minimax und neuronales Netzwerk funktionieren in dieser Liste etwas später).
Alle Artikel der Serien AI und 2048