Frage Was ist der optimale Algorithmus für das Spiel 2048?


Ich bin kürzlich auf das Spiel gestoßen 2048. Du machst ähnliche Kacheln zusammen, indem du sie in eine der vier Richtungen bewegst, um "größere" Kacheln zu erstellen. Nach jedem Zug erscheint eine neue Kachel an einer zufälligen leeren Position mit einem Wert von entweder 2 oder 4. Das Spiel wird beendet, wenn alle Felder gefüllt sind und es keine Züge gibt, die Kacheln zusammenführen können, oder Sie erstellen eine Kachel mit einem Wert von 2048.

Erstens muss ich einer klar definierten Strategie folgen, um das Ziel zu erreichen. Also dachte ich daran, ein Programm dafür zu schreiben.

Mein aktueller Algorithmus:

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

Was ich gerade mache ist, ich werde versuchen, die Fliesen mit Werten zu verschmelzen 2 und 4Ich versuche es zu haben 2 und 4 Fliesen, so minimal wie möglich. Wenn ich es auf diese Weise versuche, werden alle anderen Kacheln automatisch zusammengeführt und die Strategie scheint gut zu sein.

Aber wenn ich diesen Algorithmus benutze, bekomme ich nur 4000 Punkte, bevor das Spiel beendet wird. Maximale Punkte AFAIK ist etwas mehr als 20.000 Punkte, was viel größer ist als mein aktueller Wert. Gibt es einen besseren Algorithmus als die oben genannten?


1753
2018-03-12 05:37


Ursprung


Antworten:


Ich entwickelte eine 2048 AI mit Expectimax Optimierung, anstelle der Minimax-Suche, die von @ Ovolves Algorithmus verwendet wird. Die KI führt einfach eine Maximierung über alle möglichen Züge aus, gefolgt von einer Erwartung über alle möglichen Kachel-Spawns (gewichtet mit der Wahrscheinlichkeit der Kacheln, d. H. 10% für eine 4 und 90% für eine 2). Soweit mir bekannt ist, ist es nicht möglich, Expectimax-Optimierung zu reduzieren (außer das Entfernen von Zweigen, die äußerst unwahrscheinlich sind), und so ist der verwendete Algorithmus eine sorgfältig optimierte Brute-Force-Suche.

Performance

Die AI in ihrer Standardkonfiguration (max. Suchtiefe von 8) benötigt zwischen 10ms und 200ms, um eine Bewegung durchzuführen, abhängig von der Komplexität der Brettposition. Im Test erreicht die KI im Laufe eines ganzen Spiels eine durchschnittliche Bewegungsrate von 5-10 Bewegungen pro Sekunde. Wenn die Suchtiefe auf 6 Züge begrenzt ist, kann die KI problemlos mehr als 20 Züge pro Sekunde ausführen interessantes Beobachten.

Um die Punktzahl der KI zu beurteilen, habe ich die KI 100 mal ausgeführt (per Fernbedienung mit dem Browserspiel verbunden). Für jedes Plättchen sind hier die Proportionen der Spiele, in denen dieses Plättchen mindestens einmal erreicht wurde:

2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%

Die Mindestpunktzahl über alle Läufe betrug 124024; die maximale erreichte Punktzahl war 794076. Der Medianwert ist 387222. Die KI hat es nie geschafft, das 2048-Plättchen zu erhalten (also hat sie das Spiel in 100 Spielen nie einmal verloren); Tatsächlich hat es das erreicht 8192 Fliese mindestens einmal in jedem Lauf!

Hier ist der Screenshot des besten Laufs:

32768 tile, score 794076

Dieses Spiel dauerte 27830 Züge über 96 Minuten oder durchschnittlich 4,8 Züge pro Sekunde.

Implementierung

Mein Ansatz codiert die gesamte Platte (16 Einträge) als eine einzelne 64-Bit-Ganzzahl (wobei Kacheln die Nybbles sind, d. H. 4-Bit-Blöcke). Auf einer 64-Bit-Maschine kann so die gesamte Platine in einem einzigen Maschinenregister weitergegeben werden.

Bit-Shift-Operationen werden verwendet, um einzelne Zeilen und Spalten zu extrahieren. Eine einzelne Zeile oder Spalte ist eine 16-Bit-Menge, daher kann eine Tabelle der Größe 65536 Transformationen kodieren, die auf einer einzelnen Zeile oder Spalte operieren. Zum Beispiel werden Bewegungen als 4 Nachschlagevorgänge in eine vorberechnete "Bewegungseffekttabelle" implementiert, die beschreibt, wie sich jede Bewegung auf eine einzelne Zeile oder Spalte auswirkt (beispielsweise enthält die Tabelle "nach rechts verschieben" den Eintrag "1122 -> 0023" und beschreibt, wie Die Zeile [2,2,4,4] wird zur Zeile [0,0,4,8], wenn sie nach rechts verschoben wird.

Das Scoring erfolgt ebenfalls mithilfe der Tabellensuche. Die Tabellen enthalten Heuristikbewertungen, die für alle möglichen Zeilen / Spalten berechnet werden, und die resultierende Punktzahl für eine Karte ist einfach die Summe der Tabellenwerte für jede Zeile und Spalte.

Diese Board-Darstellung, zusammen mit dem Table-Lookup-Ansatz für Bewegung und Scoring, erlaubt der KI, eine große Anzahl von Spielzuständen in einer kurzen Zeitspanne zu durchsuchen (über 10.000.000 Spielzustände pro Sekunde auf einem Kern meines Laptops von Mitte 2011).

Die Expecsimax-Suche selbst wird als rekursive Suche codiert, die zwischen "Erwartungsschritten" (Testen aller möglichen Spawnpositionen und -werte und Gewichtung ihrer optimierten Bewertungen durch die Wahrscheinlichkeit jeder Möglichkeit) und "Maximierungsschritten" (Testen aller möglichen Bewegungen) wechselt und wähle diejenige mit der besten Punktzahl). Die Baumsuche wird beendet, wenn sie eine zuvor gesehene Position sieht (mit a Umsetztisch), wenn es eine vordefinierte Tiefengrenze erreicht oder wenn es einen Platinenzustand erreicht, der höchst unwahrscheinlich ist (z. B. wurde es erreicht, indem 6 "4" Kacheln in einer Reihe von der Startposition erhalten wurden). Die typische Suchtiefe beträgt 4-8 Züge.

Heuristiken

Mehrere Heuristiken werden verwendet, um den Optimierungsalgorithmus zu günstigen Positionen zu lenken. Die genaue Wahl der Heuristik hat einen großen Einfluss auf die Leistung des Algorithmus. Die verschiedenen Heuristiken werden gewichtet und zu einer Positionsbewertung kombiniert, die bestimmt, wie "gut" eine bestimmte Brettposition ist. Die Optimierungssuche zielt dann darauf ab, die durchschnittliche Punktzahl aller möglichen Brettpositionen zu maximieren. Die tatsächliche Punktzahl, wie das Spiel zeigt, ist nicht wird verwendet, um die Board-Punktzahl zu berechnen, da sie zu stark gewichtet wird, um die Kacheln zusammenzufassen (wenn eine verzögerte Zusammenführung einen großen Vorteil erzeugen könnte).

Anfangs verwendete ich zwei sehr einfache Heuristiken, die "Boni" für offene Quadrate und für große Werte am Rand gewährten. Diese Heuristiken haben sich sehr gut entwickelt und erreichten häufig 16384, erreichten aber nie 32768.

Petr Morávek (@xificurk) nahm meine AI und fügte zwei neue Heuristiken hinzu. Die erste Heuristik war eine Strafe für nicht-monotone Zeilen und Spalten, die mit zunehmender Ränge anstiegen, wodurch sichergestellt wurde, dass nicht-monotone Zeilen kleiner Zahlen die Punktzahl nicht stark beeinflussten, aber nicht-monotone Zeilen mit großen Zahlen die Punktzahl erheblich beeinträchtigten. Die zweite Heuristik zählte neben Freiflächen auch die Anzahl möglicher Zusammenführungen (benachbarte Gleichwerte). Diese beiden Heuristiken dienten dazu, den Algorithmus in Richtung monotoner Boards (die leichter zusammenzufassen sind) und zu Board-Positionen mit vielen Zusammenführungen zu bringen (indem er dazu ermutigt wird, Merges auszurichten, wo dies für einen größeren Effekt möglich ist).

Darüber hinaus hat Petr auch die heuristischen Gewichte mithilfe einer "Meta-Optimierungs" -Strategie optimiert (mit einem Algorithmus namens CMA-ES), wobei die Gewichte selbst so angepasst wurden, dass der höchstmögliche Durchschnittswert erreicht wurde.

Die Auswirkungen dieser Änderungen sind äußerst signifikant. Der Algorithmus ging davon aus, die 16384-Kachel in 13% der Fälle in über 90% der Zeit zu erreichen, und der Algorithmus erreichte 32768 in 1/3 der Zeit (während die alten Heuristiken nie eine 32768-Kachel hervorbrachten). .

Ich glaube, dass die Heuristiken noch verbesserungsfähig sind. Dieser Algorithmus ist definitiv noch nicht "optimal", aber ich habe das Gefühl, dass es ziemlich knapp wird.


Dass die KI in mehr als einem Drittel ihrer Spiele das 32768-Plättchen erreicht, ist ein großer Meilenstein. Ich werde überrascht sein zu hören, ob irgendwelche menschlichen Spieler 32768 im offiziellen Spiel erreicht haben (d. H. Ohne Werkzeuge wie Savestates oder Undo zu benutzen). Ich denke, die 65536 ist in Reichweite!

Sie können die KI selbst ausprobieren. Der Code ist verfügbar unter https://github.com/nneonneo/2048-ai.


1130
2018-03-19 07:22



Ich bin der Autor des AI-Programms, das andere in diesem Thread erwähnt haben. Sie können die KI einsehen Aktion oder lies die Quelle.

Momentan erreicht das Programm eine Gewinnrate von 90%, die in Javascript im Browser auf meinem Laptop läuft, wenn man etwa 100 Millisekunden der Zeit pro Bewegung bedenkt, also ist es zwar nicht perfekt (noch!), Aber ziemlich gut.

Da das Spiel ein diskreter Zustandsraum, perfekte Information, rundenbasiertes Spiel wie Schach und Dame ist, habe ich die gleichen Methoden verwendet, die sich bei diesen Spielen bewährt haben, nämlich Minimax  Suche mit Alpha-Beta-Beschneidung. Da es bereits eine Menge Informationen über diesen Algorithmus gibt, werde ich nur über die zwei Hauptheuristiken sprechen, die ich in der statische Bewertungsfunktion und die viele der Intuitionen formalisieren, die andere Leute hier ausgedrückt haben.

Monotonie

Diese Heuristik versucht sicherzustellen, dass die Werte der Kacheln entweder entlang der Links / Rechts- und der Oben / Unten-Richtung entweder zu- oder abnehmen. Diese Heuristik erfasst nur die Intuition, die viele andere erwähnt haben, dass höherwertige Kacheln in einer Ecke gruppiert werden sollten. Es wird typischerweise verhindern, dass kleinerwertige Kacheln verwaist werden, und wird das Board sehr organisiert halten, wobei kleinere Kacheln in die größeren Kacheln einfallen und sich dort auffüllen.

Hier ist ein Screenshot eines perfekt monotonen Rasters. Ich habe dies erhalten, indem ich den Algorithmus mit der eval-Funktion ausgeführt habe, um die anderen Heuristiken außer Acht zu lassen und nur die Monotonie zu berücksichtigen.

A perfectly monotonic 2048 board

Glätte

Die obige Heuristik alleine neigt dazu, Strukturen zu erzeugen, in denen benachbarte Kacheln in ihrem Wert abnehmen, aber natürlich müssen angrenzende Kacheln denselben Wert haben, um zusammenzuführen. Daher misst die Glättungsheuristik nur den Wertunterschied zwischen benachbarten Kacheln, um diese Anzahl zu minimieren.

Ein Kommentator zu Hacker News gab eine interessante Formalisierung dieser Idee in Bezug auf die Graphentheorie.

Hier ist ein Screenshot von einem perfekt glatten Raster, mit freundlicher Genehmigung von diese ausgezeichnete Parodiegabel.

A perfectly smooth 2048 board

Kostenlose Fliesen

Und schließlich gibt es eine Strafe für zu wenige freie Plättchen, da Optionen schnell auslaufen können, wenn das Spielbrett zu eng wird.

Und das ist es! Das Durchsuchen des Spielraums während der Optimierung dieser Kriterien ergibt eine bemerkenswert gute Leistung. Ein Vorteil bei der Verwendung eines verallgemeinerten Ansatzes anstelle einer explizit codierten Bewegungsstrategie besteht darin, dass der Algorithmus oft interessante und unerwartete Lösungen findet. Wenn Sie es laufen sehen, wird es oft überraschende, aber effektive Bewegungen machen, wie zum Beispiel plötzlich die Wand oder Ecke, gegen die es sich aufbaut.

Bearbeiten:

Hier ist eine Demonstration der Kraft dieses Ansatzes. Ich habe die Fliesenwerte freigelegt (so ging es weiter nach 2048) und hier ist das beste Ergebnis nach acht Versuchen.

4096

Ja, das ist ein 4096 neben einem 2048. =) Das bedeutet, dass es das schwer fassbare 2048-Plättchen dreimal auf dem gleichen Brett erreichte.


1224
2018-03-13 20:04



BEARBEITEN: Dies ist ein naive Algorithmus, der den menschlichen Denkprozess modelliert und im Vergleich zur KI sehr schwache Ergebnisse erzielt, die alle Möglichkeiten durchsuchen, da sie nur eine Kachel voraus sieht. Es wurde früh in der Antwortzeitlinie eingereicht.

Ich habe den Algorithmus verfeinert und das Spiel geschlagen! Es kann durch einfaches Pech am Ende scheitern (Sie werden gezwungen, nach unten zu gehen, was Sie nie tun sollten, und eine Kachel erscheint dort, wo Ihre höchste sein sollte. Versuchen Sie einfach, die obere Reihe gefüllt zu halten, also nicht nach links) Brechen Sie das Muster), aber im Grunde haben Sie einen festen Teil und einen mobilen Teil zum Spielen. Das ist dein Ziel:

Ready to finish

Dies ist das Modell, das ich standardmäßig gewählt habe.

1024 512 256 128
  8   16  32  64
  4   2   x   x
  x   x   x   x

Die gewählte Ecke ist willkürlich, du drückst im Grunde nie eine Taste (die verbotene Bewegung), und wenn du dies tust, drückst du das Gegenteil nochmal und versuchst es zu beheben. Für zukünftige Kacheln erwartet das Modell immer die nächste zufällige Kachel als 2 und erscheint auf der gegenüberliegenden Seite des aktuellen Modells (während die erste Zeile unvollständig ist, in der unteren rechten Ecke, sobald die erste Zeile abgeschlossen ist, unten links) Ecke).

Hier geht der Algorithmus. Etwa 80% gewinnen (es scheint, dass es immer möglich ist, mit "professionelleren" KI-Techniken zu gewinnen, aber ich bin mir nicht sicher.)

initiateModel();

while(!game_over)
{    
    checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point

    for each 3 possible move:
        evaluateResult()
    execute move with best score
    if no move is available, execute forbidden move and undo, recalculateModel()
 }

 evaluateResult() {
     calculatesBestCurrentModel()
     calculates distance to chosen model
     stores result
 }

 calculateBestCurrentModel() {
      (according to the current highest tile acheived and their distribution)
  }

Ein paar Hinweise zu den fehlenden Schritten. Hier: model change

Das Modell hat sich aufgrund des Glückes geändert, näher am erwarteten Modell zu sein. Das Modell, das die KI versucht zu erreichen, ist

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

Und die Kette dorthin ist geworden:

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

Das O repräsentieren verbotene Räume ...

Also wird es rechts drücken, dann wieder rechts, dann (rechts oder oben, je nachdem, wo die 4 erstellt hat), dann wird fortgefahren, um die Kette zu vervollständigen, bis sie kommt:

Chain completed

Jetzt sind das Modell und die Kette zurück zu:

 512 256 128  64
  4   8  16   32
  X   X   x   x
  x   x   x   x

Zweiter Zeiger, es hat Pech gehabt und sein Hauptpunkt wurde genommen. Es ist wahrscheinlich, dass es scheitern wird, aber es kann es immer noch erreichen:

Enter image description here

Hier ist das Modell und die Kette:

  O 1024 512 256
  O   O   O  128
  8  16   32  64
  4   x   x   x

Wenn es gelingt, die 128 zu erreichen, gewinnt es wieder eine ganze Reihe:

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x

119
2018-03-12 16:05



Ich habe mich für die Idee einer KI für dieses Spiel interessiert keine fest codierte Intelligenz (d. h. keine Heuristik, Bewertungsfunktionen usw.). Die KI sollte "kennt" nur die Spielregeln, und "herausfinden" das Spiel spielen. Dies steht im Gegensatz zu den meisten AIs (wie die in diesem Thread), wo das Spiel im Wesentlichen rohe Gewalt ist, gesteuert durch eine Bewertungsfunktion, die das menschliche Verständnis des Spiels repräsentiert.

AI-Algorithmus

Ich fand einen einfachen, aber überraschend guten Spielalgorithmus: Um den nächsten Zug für ein bestimmtes Brett zu bestimmen, spielt die KI das Spiel im Speicher mit zufällige Bewegungen bis das Spiel vorbei ist. Dies wird mehrmals durchgeführt, während der Endspielstand verfolgt wird. Dann das durchschnittliche Endergebnis pro Startbewegung ist berechnet. Der Startzug mit dem höchsten durchschnittlichen Endstand wird als nächster Zug gewählt.

Mit nur 100 Läufen (d. H. In Speicherspielen) pro Zug erreicht die KI das Kärtchen 2048 zu 80% und das Kärtchen 4096 zu 50%. Bei Verwendung von 10000 Läufen erhält die Kachel 2048 100%, 70% für die Kachel 4096 und etwa 1% für die Kachel 8192.

Sehen Sie es in Aktion

Die beste erreichte Punktzahl wird hier angezeigt:

best score

Eine interessante Tatsache über diesen Algorithmus ist, dass, während die Zufallsspiele ziemlich überraschend schlecht sind, die Wahl des besten (oder schlechtesten) Zuges zu einem sehr guten Spiel führt: Ein typisches KI-Spiel kann 70000 Punkte erreichen und 3000 Züge dauern In-Memory-Spiele mit Zufallszahlen aus jeder beliebigen Position ergeben durchschnittlich 340 zusätzliche Punkte in etwa 40 zusätzlichen Zügen, bevor sie sterben. (Sie können dies selbst sehen, indem Sie die AI starten und die Debug-Konsole öffnen.)

Diese Grafik veranschaulicht diesen Punkt: Die blaue Linie zeigt den Spielstand nach jedem Zug. Die rote Linie zeigt die Algorithmen Beste Random-Run-End-Spielstand von dieser Position. Im Wesentlichen ziehen die roten Werte die blauen Werte nach oben zu ihnen, da sie die beste Schätzung des Algorithmus sind. Es ist interessant zu sehen, dass die rote Linie an jedem Punkt nur ein kleines bisschen über der blauen Linie ist, aber die blaue Linie nimmt immer mehr zu.

scoring graph

Ich finde es ziemlich überraschend, dass der Algorithmus nicht wirklich gutes Spiel voraussehen muss, um die Bewegungen zu wählen, die ihn erzeugen.

Später fand ich, dass dieser Algorithmus als a eingestuft werden könnte Reine Monte Carlo Baumsuche Algorithmus.

Implementierung und Links

Zuerst habe ich eine JavaScript-Version erstellt hier in Aktion gesehen. Diese Version kann 100 Runs in angemessener Zeit laufen. Öffne die Konsole für zusätzliche Informationen. (Quelle)

Später, um noch etwas herumzuspielen, habe ich @nneonneo hochoptimierte Infrastruktur benutzt und meine Version in C ++ implementiert. Diese Version erlaubt bis zu 100000 Läufe pro Bewegung und sogar 1000000, wenn Sie die Geduld haben. Bauanleitung zur Verfügung gestellt. Es läuft in der Konsole und hat auch eine Fernbedienung, um die Web-Version abzuspielen. (Quelle)

Ergebnisse

Überraschenderweise verbessert eine Erhöhung der Anzahl von Läufen das Spiel nicht drastisch. Es scheint eine Grenze für diese Strategie bei ungefähr 80000 Punkten mit der 4096-Kachel und allen kleineren zu geben, sehr nahe bei der Erreichung der 8192-Kachel. Erhöhen Sie die Anzahl der Läufe von 100 auf 100000 erhöht die Chancen bis zu diesem Punktestand (von 5% auf 40%), aber nicht durchbrechen.

Das Laufen von 10000 Runs mit einem vorübergehenden Anstieg auf 1000000 nahe kritischen Positionen schaffte es, diese Barriere in weniger als 1% der Fälle zu durchbrechen, wobei ein maximaler Score von 129892 und der 8192-Fliese erreicht wurde.

Verbesserungen

Nach der Implementierung dieses Algorithmus habe ich viele Verbesserungen versucht, einschließlich der Verwendung der Min- oder Max-Werte oder einer Kombination von Min, Max und Avg. Ich habe auch versucht, Tiefe zu verwenden: Anstatt K-Läufe pro Zug auszuprobieren, probierte ich K Züge pro Zug Liste von einer bestimmten Länge (zum Beispiel "oben, oben, links") und die erste Bewegung der besten Scoring-Move-Liste auswählen.

Später habe ich einen Bewertungsbaum implementiert, der die bedingte Wahrscheinlichkeit berücksichtigte, einen Zug nach einer bestimmten Bewegungsliste spielen zu können.

Keine dieser Ideen zeigte jedoch einen wirklichen Vorteil gegenüber der einfachen ersten Idee. Ich habe den Code für diese Ideen im C ++ - Code auskommentiert.

Ich habe einen "Deep Search" -Mechanismus hinzugefügt, der die Laufnummer vorübergehend auf 1000000 erhöhte, wenn einer der Runs versehentlich die nächsthöhere Kachel erreichte. Dies bot eine Zeitverbesserung.

Ich würde mich freuen zu hören, ob jemand andere Verbesserungsideen hat, die die Domänenunabhängigkeit der KI aufrechterhalten.

2048 Varianten und Klone

Nur zum Spaß, habe ich auch implementierte die AI als BookmarkletEinhaken in die Spielsteuerung. Dadurch kann die KI mit dem ursprünglichen Spiel arbeiten und viele seiner Varianten.

Dies ist aufgrund der domänenunabhängigen Natur der KI möglich. Einige der Varianten sind ziemlich verschieden, wie der Hexagonal-Klon.


114
2018-05-25 09:25



Ich kopiere hier den Inhalt eines Beitrag auf meinem Blog


Die von mir vorgeschlagene Lösung ist sehr einfach und einfach zu implementieren. Obwohl, hat es die Punktzahl von 131040 erreicht. Mehrere Benchmarks der Algorithmusleistungen werden präsentiert.

Score

Algorithmus

Heuristischer Scoring-Algorithmus

Die Annahme, auf der mein Algorithmus basiert, ist ziemlich einfach: Wenn Sie eine höhere Punktzahl erreichen wollen, muss das Board so sauber wie möglich gehalten werden. Insbesondere ist die optimale Einstellung durch eine lineare und monotone abnehmende Reihenfolge der Kachelwerte gegeben. Diese Intuition gibt Ihnen auch die Obergrenze für einen Kachelwert: s wobei n die Anzahl der Kacheln auf dem Board ist.

(Es besteht die Möglichkeit, das 131072-Plättchen zu erreichen, wenn das 4-Plättchen bei Bedarf zufällig erzeugt wird, anstatt das 2-Plättchen.)

In den folgenden Bildern sind zwei Möglichkeiten dargestellt, das Board zu organisieren:

enter image description here

Um die Ordination der Kacheln in einer monoton abnehmenden Reihenfolge zu erzwingen, wird die Punktzahl als Summe der linearisierten Werte auf der Platine multipliziert mit den Werten einer geometrischen Folge mit dem gemeinsamen Verhältnis r <1 berechnet.

s

s

Mehrere lineare Pfade können gleichzeitig ausgewertet werden, die endgültige Punktzahl ist die maximale Punktzahl eines beliebigen Pfades.

Entscheidungsregel

Die implementierte Entscheidungsregel ist nicht ganz schlau, der Code in Python wird hier vorgestellt:

@staticmethod
def nextMove(board,recursion_depth=3):
    m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
    return m

@staticmethod
def nextMoveRecur(board,depth,maxDepth,base=0.9):
    bestScore = -1.
    bestMove = 0
    for m in range(1,5):
        if(board.validMove(m)):
            newBoard = copy.deepcopy(board)
            newBoard.move(m,add_tile=True)

            score = AI.evaluate(newBoard)
            if depth != 0:
                my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)
                score += my_s*pow(base,maxDepth-depth+1)

            if(score > bestScore):
                bestMove = m
                bestScore = score
    return (bestMove,bestScore);

Eine Implementierung des Minmax oder des Expectiminimax wird den Algorithmus sicher verbessern. Offensichtlich ein mehr Eine ausgeklügelte Entscheidungsregel verlangsamt den Algorithmus und es wird einige Zeit benötigt, um implementiert zu werden. Ich werde in naher Zukunft eine Minimax-Implementierung versuchen. (Bleib dran)

Benchmark

  • T1 - 121 Tests - 8 verschiedene Wege - r = 0,125
  • T2 - 122 Tests - 8 verschiedene Wege - r = 0,25
  • T3 - 132 Tests - 8 verschiedene Wege - r = 0,5
  • T4 - 211 Tests - 2 verschiedene Wege - r = 0,125
  • T5 - 274 Tests - 2 verschiedene Wege - r = 0,25
  • T6 - 211 Tests - 2 verschiedene Wege - r = 0,5

enter image description here enter image description here enter image description here enter image description here

Im Fall von T2 erzeugen vier von zehn Tests das 4096 - Plättchen mit einer durchschnittlichen Punktzahl von s 42000

Code

Der Code kann auf GiHub unter folgendem Link gefunden werden: https://github.com/Nicola17/term2048-AI Es basiert auf Begriff2048 und es ist in Python geschrieben. Ich werde so bald wie möglich eine effizientere Version in C ++ implementieren.


88
2018-03-26 22:13



Mein Versuch verwendet expectimax wie andere Lösungen oben, aber ohne Bitboards. Nneonneos Lösung kann 10 Millionen Züge kontrollieren, was ungefähr einer Tiefe von 4 entspricht, wobei 6 Steine ​​übrig bleiben und 4 Züge möglich sind (2 * 6 * 4)4. In meinem Fall dauert es zu lange, um diese Tiefe zu erkunden. Ich stelle die Tiefe der Exposimax-Suche entsprechend der Anzahl der freien Kacheln ein:

depth = free > 7 ? 1 : (free > 4 ? 2 : 3)

Die Punktzahlen der Bretter werden mit der gewichteten Summe aus dem Quadrat der Anzahl der freien Kacheln und dem Skalarprodukt des 2D-Gitters berechnet:

[[10,8,7,6.5],
 [.5,.7,1,3],
 [-.5,-1.5,-1.8,-2],
 [-3.8,-3.7,-3.5,-3]]

was dazu zwingt, die Kärtchen absteigend in einer Art Schlange von der linken oberen Kachel zu organisieren.

Code unter oder Jsbin:

  
var n = 4,
	M = new MatrixTransform(n);

var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles

var snake= [[10,8,7,6.5],
            [.5,.7,1,3],
            [-.5,-1.5,-1.8,-2],
            [-3.8,-3.7,-3.5,-3]]
snake=snake.map(function(a){return a.map(Math.exp)})

initialize(ai)

function run(ai) {
	var p;
	while ((p = predict(ai)) != null) {
		move(p, ai);
	}
	//console.log(ai.grid , maxValue(ai.grid))
	ai.maxValue = maxValue(ai.grid)
	console.log(ai)
}

function initialize(ai) {
	ai.grid = [];
	for (var i = 0; i < n; i++) {
		ai.grid[i] = []
		for (var j = 0; j < n; j++) {
			ai.grid[i][j] = 0;
		}
	}
	rand(ai.grid)
	rand(ai.grid)
	ai.steps = 0;
}

function move(p, ai) { //0:up, 1:right, 2:down, 3:left
	var newgrid = mv(p, ai.grid);
	if (!equal(newgrid, ai.grid)) {
		//console.log(stats(newgrid, ai.grid))
		ai.grid = newgrid;
		try {
			rand(ai.grid)
			ai.steps++;
		} catch (e) {
			console.log('no room', e)
		}
	}
}

function predict(ai) {
	var free = freeCells(ai.grid);
	ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3);
	var root = {path: [],prob: 1,grid: ai.grid,children: []};
	var x = expandMove(root, ai)
	//console.log("number of leaves", x)
	//console.log("number of leaves2", countLeaves(root))
	if (!root.children.length) return null
	var values = root.children.map(expectimax);
	var mx = max(values);
	return root.children[mx[1]].path[0]

}

function countLeaves(node) {
	var x = 0;
	if (!node.children.length) return 1;
	for (var n of node.children)
		x += countLeaves(n);
	return x;
}

function expectimax(node) {
	if (!node.children.length) {
		return node.score
	} else {
		var values = node.children.map(expectimax);
		if (node.prob) { //we are at a max node
			return Math.max.apply(null, values)
		} else { // we are at a random node
			var avg = 0;
			for (var i = 0; i < values.length; i++)
				avg += node.children[i].prob * values[i]
			return avg / (values.length / 2)
		}
	}
}

function expandRandom(node, ai) {
	var x = 0;
	for (var i = 0; i < node.grid.length; i++)
		for (var j = 0; j < node.grid.length; j++)
			if (!node.grid[i][j]) {
				var grid2 = M.copy(node.grid),
					grid4 = M.copy(node.grid);
				grid2[i][j] = 2;
				grid4[i][j] = 4;
				var child2 = {grid: grid2,prob: .9,path: node.path,children: []};
				var child4 = {grid: grid4,prob: .1,path: node.path,children: []}
				node.children.push(child2)
				node.children.push(child4)
				x += expandMove(child2, ai)
				x += expandMove(child4, ai)
			}
	return x;
}

function expandMove(node, ai) { // node={grid,path,score}
	var isLeaf = true,
		x = 0;
	if (node.path.length < ai.depth) {
		for (var move of[0, 1, 2, 3]) {
			var grid = mv(move, node.grid);
			if (!equal(grid, node.grid)) {
				isLeaf = false;
				var child = {grid: grid,path: node.path.concat([move]),children: []}
				node.children.push(child)
				x += expandRandom(child, ai)
			}
		}
	}
	if (isLeaf) node.score = dot(ai.weights, stats(node.grid))
	return isLeaf ? 1 : x;
}



var cells = []
var table = document.querySelector("table");
for (var i = 0; i < n; i++) {
	var tr = document.createElement("tr");
	cells[i] = [];
	for (var j = 0; j < n; j++) {
		cells[i][j] = document.createElement("td");
		tr.appendChild(cells[i][j])
	}
	table.appendChild(tr);
}

function updateUI(ai) {
	cells.forEach(function(a, i) {
		a.forEach(function(el, j) {
			el.innerHTML = ai.grid[i][j] || ''
		})
	});
}
updateUI(ai)

function runAI() {
	var p = predict(ai);
	if (p != null && ai.running) {
		move(p, ai)
		updateUI(ai)
		requestAnimationFrame(runAI)
	}
}
runai.onclick = function() {
	if (!ai.running) {
		this.innerHTML = 'stop AI';
		ai.running = true;
		runAI();
	} else {
		this.innerHTML = 'run AI';
		ai.running = false;
	}
}


hint.onclick = function() {
	hintvalue.innerHTML = ['up', 'right', 'down', 'left'][predict(ai)]
}
document.addEventListener("keydown", function(event) {
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai)
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai)
}


function stats(grid, previousGrid) {

	var free = freeCells(grid);

	var c = dot2(grid, snake);

	return [c, free * free];
}

function dist2(a, b) { //squared 2D distance
	return Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2)
}

function dot(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		r += a[i] * b[i];
	return r
}

function dot2(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		for (var j = 0; j < a[0].length; j++)
			r += a[i][j] * b[i][j]
	return r;
}

function product(a) {
	return a.reduce(function(v, x) {
		return v * x
	}, 1)
}

function maxValue(grid) {
	return Math.max.apply(null, grid.map(function(a) {
		return Math.max.apply(null, a)
	}));
}

function freeCells(grid) {
	return grid.reduce(function(v, a) {
		return v + a.reduce(function(t, x) {
			return t + (x == 0)
		}, 0)
	}, 0)
}

function max(arr) { // return [value, index] of the max
	var m = [-Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] > m[0]) m = [arr[i], i];
	}
	return m
}

function min(arr) { // return [value, index] of the min
	var m = [Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] < m[0]) m = [arr[i], i];
	}
	return m
}

function maxScore(nodes) {
	var min = {
		score: -Infinity,
		path: []
	};
	for (var node of nodes) {
		if (node.score > min.score) min = node;
	}
	return min;
}


function mv(k, grid) {
	var tgrid = M.itransform(k, grid);
	for (var i = 0; i < tgrid.length; i++) {
		var a = tgrid[i];
		for (var j = 0, jj = 0; j < a.length; j++)
			if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j]
		for (; jj < a.length; jj++)
			a[jj] = 0;
	}
	return M.transform(k, tgrid);
}

function rand(grid) {
	var r = Math.floor(Math.random() * freeCells(grid)),
		_r = 0;
	for (var i = 0; i < grid.length; i++) {
		for (var j = 0; j < grid.length; j++) {
			if (!grid[i][j]) {
				if (_r == r) {
					grid[i][j] = Math.random() < .9 ? 2 : 4
				}
				_r++;
			}
		}
	}
}

function equal(grid1, grid2) {
	for (var i = 0; i < grid1.length; i++)
		for (var j = 0; j < grid1.length; j++)
			if (grid1[i][j] != grid2[i][j]) return false;
	return true;
}

function conv44valid(a, b) {
	var r = 0;
	for (var i = 0; i < 4; i++)
		for (var j = 0; j < 4; j++)
			r += a[i][j] * b[3 - i][3 - j]
	return r
}

function MatrixTransform(n) {
	var g = [],
		ig = [];
	for (var i = 0; i < n; i++) {
		g[i] = [];
		ig[i] = [];
		for (var j = 0; j < n; j++) {
			g[i][j] = [[j, i],[i, n-1-j],[j, n-1-i],[i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left]
			ig[i][j] = [[j, i],[i, n-1-j],[n-1-j, i],[i, j]]; // the inverse tranformations
		}
	}
	this.transform = function(k, grid) {
		return this.transformer(k, grid, g)
	}
	this.itransform = function(k, grid) { // inverse transform
		return this.transformer(k, grid, ig)
	}
	this.transformer = function(k, grid, mat) {
		var newgrid = [];
		for (var i = 0; i < grid.length; i++) {
			newgrid[i] = [];
			for (var j = 0; j < grid.length; j++)
				newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]];
		}
		return newgrid;
	}
	this.copy = function(grid) {
		return this.transform(3, grid)
	}
}
body {
	text-align: center
}
table, th, td {
    border: 1px solid black;
    margin: 5px auto;
}
td {
    width: 35px;
    height: 35px;
    text-align: center;
}
<table></table>
<button id=init>init</button><button id=runai>run AI</button><button id=hint>hint</button><span id=hintvalue></span>


30
2018-03-03 05:35



Ich denke, dass ich einen Algorithmus gefunden habe, der ziemlich gut funktioniert, da ich oft Werte über 10000 erreiche, meine persönliche Bestleistung liegt bei 16000. Meine Lösung zielt nicht darauf ab, die größten Zahlen in einer Ecke zu halten, sondern in der obersten Reihe zu halten.

Bitte beachten Sie den folgenden Code:

while( !game_over ) {
    move_direction=up;
    if( !move_is_possible(up) ) {
        if( move_is_possible(right) && move_is_possible(left) ){
            if( number_of_empty_cells_after_moves(left,up) > number_of_empty_cells_after_moves(right,up) ) 
                move_direction = left;
            else
                move_direction = right;
        } else if ( move_is_possible(left) ){
            move_direction = left;
        } else if ( move_is_possible(right) ){
            move_direction = right;
        } else {
            move_direction = down;
        }
    }
    do_move(move_direction);
}

25
2018-03-12 18:57



Ich bin der Autor eines 2048-Controllers, der besser abschneidet als jedes andere in diesem Thread erwähnte Programm. Eine effiziente Implementierung des Controllers ist verfügbar unter Github. Im ein separates Repo Es gibt auch den Code, der zum Trainieren der Zustandsbewertungsfunktion des Controllers verwendet wird. Die Trainingsmethode ist in der. Beschrieben Papier-.

Der Controller verwendet die Expectimax-Suche mit einer von Grund auf neu erlernten Zustandsbewertungsfunktion (ohne menschliche 2048-Expertise) durch eine Variante von Zeitunterschied lernen (eine Verstärkungslerntechnik). Die Statuswertfunktion verwendet ein n-Tupel-NetzwerkDies ist im Grunde eine gewichtete lineare Funktion der auf der Platine beobachteten Muster. Es umfasste mehr als 1 Milliarde Gewichte, insgesamt.

Performance

Bei 1 Züge / s: 609104 (100 Spiele Durchschnitt)

Bei 10 Zügen / s: 589355 (300 Spiele Durchschnitt)

Bei 3-lagig (ca. 1500 Züge / s): 511759 (1000 Spiele Durchschnitt)

Die Kachelstatistik für 10 Züge / s ist wie folgt:

2048: 100%
4096: 100%
8192: 100%
16384: 97%
32768: 64%
32768,16384,8192,4096: 10%

(Die letzte Zeile bedeutet, dass die gegebenen Steine ​​gleichzeitig auf dem Brett liegen).

Für 3-lagig:

2048: 100%
4096: 100%
8192: 100%
16384: 96%
32768: 54%
32768,16384,8192,4096: 8%

Ich habe jedoch nie beobachtet, wie das 65536-Plättchen erhalten wurde.


25
2017-12-21 10:49



Es gibt bereits eine KI-Implementierung für dieses Spiel: Hier. Auszug aus der README:

Der Algorithmus ist eine iterative Vertiefung der ersten Alpha-Beta-Suche. Die Auswertungsfunktion versucht, die Zeilen und Spalten monoton (entweder alle abnehmend oder ansteigend) zu halten und gleichzeitig die Anzahl der Kacheln im Raster zu minimieren.

Es gibt auch eine Diskussion über ycombinator über diesen Algorithmus, den Sie nützlich finden können.


21
2018-03-13 09:16