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

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

Erstens muss ich eine klar definierte Strategie verfolgen, 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 tue , ist an jedem Punkt, werde ich versuchen , die Fliesen mit Werten zu verschmelzen 2und 4, das heißt, ich versuche zu haben 2und 4Fliesen, so minimal wie möglich. Wenn ich es so versuche, wurden alle anderen Kacheln automatisch zusammengeführt und die Strategie scheint gut zu sein.

Aber wenn ich diesen Algorithmus tatsächlich benutze, bekomme ich nur ungefähr 4000 Punkte, bevor das Spiel endet. Maximale Punkte AFAIK ist etwas mehr als 20.000 Punkte, was viel größer ist als meine aktuelle Punktzahl. Gibt es einen besseren Algorithmus als den oben genannten?

Ich habe eine 2048-KI mit Expectimax- Optimierung anstelle der Minimax-Suche entwickelt, die vom @ ovolve-Algorithmus verwendet wird. Die KI führt einfach eine Maximierung über alle möglichen Züge durch, gefolgt von der Erwartung über alle möglichen Kachel-Spawns (gewichtet mit der Wahrscheinlichkeit der Kacheln, dh 10% für eine 4 und 90% für eine 2). Soweit mir bekannt ist, ist es nicht möglich, die Expectimax-Optimierung zu beschneiden (außer Zweige zu entfernen, die äußerst unwahrscheinlich sind). Daher wird als Algorithmus eine sorgfältig optimierte Brute-Force-Suche verwendet.

Performance

Die KI in ihrer Standardkonfiguration (maximale Suchtiefe von 8) benötigt je nach Komplexität der Board-Position zwischen 10 ms und 200 ms, um eine Bewegung auszuführen. Beim Testen erreicht die KI im Verlauf eines gesamten Spiels eine durchschnittliche Bewegungsrate von 5-10 Zügen pro Sekunde. Wenn die Suchtiefe auf 6 Züge begrenzt ist, kann die KI problemlos mehr als 20 Züge pro Sekunde ausführen, was für einige interessante Beobachtungen sorgt .

Um die Punktzahlleistung der KI zu beurteilen, habe ich die KI 100 Mal ausgeführt (über eine Fernbedienung mit dem Browsergame verbunden). Hier sind für jedes Plättchen die Anteile 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 Punktzahl betrug 794076. Die mittlere Punktzahl beträgt 387222. Die KI hat es nie versäumt, das 2048-Plättchen zu erhalten (so dass sie das Spiel auch in 100 Spielen nicht einmal verloren hat). Tatsächlich wurde die 8192- Kachel mindestens einmal in jedem Lauf erreicht!

Hier ist der Screenshot des besten Laufs:

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

Implementierung

Mein Ansatz codiert die gesamte Karte (16 Einträge) als einzelne 64-Bit-Ganzzahl (wobei Kacheln die Nybbles sind, dh 4-Bit-Chunks). Auf einem 64-Bit-Computer kann so die gesamte Karte in einem einzigen Maschinenregister herumgereicht werden.

Bitverschiebungsoperationen werden verwendet, um einzelne Zeilen und Spalten zu extrahieren. Eine einzelne Zeile oder Spalte ist eine 16-Bit-Größe, sodass eine Tabelle der Größe 65536 Transformationen codieren kann, die für eine einzelne Zeile oder Spalte ausgeführt werden. Zum Beispiel werden Verschiebungen als 4 Suchvorgänge in eine vorberechnete "Verschiebungseffekttabelle" implementiert, die beschreibt, wie sich jede Verschiebung auf eine einzelne Zeile oder Spalte auswirkt (zum Beispiel enthält die Tabelle "Nach rechts verschieben" den Eintrag "1122 -> 0023", der beschreibt, wie die Zeile [2,2,4,4] wird zur Zeile [0,0,4,8], wenn sie nach rechts verschoben wird.

Die Bewertung erfolgt auch mithilfe der Tabellensuche. Die Tabellen enthalten heuristische Bewertungen, die für alle möglichen Zeilen / Spalten berechnet wurden, und die resultierende Bewertung für eine Tafel ist einfach die Summe der Tabellenwerte für jede Zeile und Spalte.

Diese Board-Darstellung ermöglicht es der KI zusammen mit dem Table-Lookup-Ansatz für Bewegung und Wertung, in kurzer Zeit eine große Anzahl von Spielzuständen zu durchsuchen (über 10.000.000 Spielzustände pro Sekunde auf einem Kern meines Laptops Mitte 2011).

Die Expectimax-Suche selbst ist als rekursive Suche codiert, die zwischen "Erwartungs" -Schritten (Testen aller möglichen Kachel-Spawn-Positionen und -Werte und Gewichtung ihrer optimierten Punktzahlen mit der Wahrscheinlichkeit jeder Möglichkeit) und "Maximierungs" -Schritten (Testen aller möglichen Bewegungen) wechselt und Auswahl der mit der besten Punktzahl). Die Baumsuche wird beendet, wenn eine zuvor gesehene Position (unter Verwendung einer Transpositionstabelle ) angezeigt wird , wenn eine vordefinierte Tiefengrenze erreicht wird oder wenn ein Board-Status erreicht wird, der höchst unwahrscheinlich ist (z. B. indem 6 "4" -Kacheln erhalten wurden in einer Reihe von der Startposition). Die typische Suchtiefe beträgt 4-8 Züge.

Heuristik

Verschiedene Heuristiken werden verwendet, um den Optimierungsalgorithmus auf günstige Positionen auszurichten. 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 Boardpositionen zu maximieren. Die tatsächliche Punktzahl, wie vom Spiel gezeigt, wird nicht zur Berechnung der Brettpunktzahl verwendet, da sie zu stark für das Zusammenführen von Kacheln gewichtet ist (wenn eine verzögerte Zusammenführung einen großen Vorteil bringen könnte).

Anfangs habe ich zwei sehr einfache Heuristiken verwendet, die "Boni" für offene Quadrate und für große Werte am Rand gewähren. Diese Heuristiken zeigten eine ziemlich gute Leistung und erreichten häufig 16384, erreichten jedoch nie 32768.

Petr Morávek (@xificurk) nahm meine KI und fügte zwei neue Heuristiken hinzu. Die erste Heuristik war eine Strafe für nicht monotone Zeilen und Spalten, die mit zunehmenden Rängen zunahmen, wodurch sichergestellt wurde, dass nicht monotone Reihen mit kleinen Zahlen die Punktzahl nicht stark beeinflussen, aber nicht monotone Reihen mit großen Zahlen die Punktzahl erheblich beeinträchtigen. Die zweite Heuristik zählte die Anzahl möglicher Zusammenführungen (benachbarte gleiche Werte) zusätzlich zu offenen Räumen. Diese beiden Heuristiken dienten dazu, den Algorithmus in Richtung monotoner Boards (die einfacher zusammenzuführen sind) und in Richtung Board-Positionen mit vielen Zusammenführungen zu treiben (was ihn ermutigte, Zusammenführungen nach Möglichkeit auszurichten, um eine größere Wirkung zu erzielen).

Darüber hinaus optimierte Petr die heuristischen Gewichte mithilfe einer "Meta-Optimierungs" -Strategie (unter Verwendung eines Algorithmus namens CMA-ES ), bei der die Gewichte selbst angepasst wurden, um die höchstmögliche durchschnittliche Punktzahl zu erhalten.

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

Ich glaube, die Heuristik kann noch verbessert werden. Dieser Algorithmus ist definitiv noch nicht "optimal", aber ich habe das Gefühl, dass er ziemlich nahe kommt.

Dass die KI in über einem Drittel ihrer Spiele das 32768-Plättchen erreicht, ist ein großer Meilenstein. Ich werde überrascht sein zu hören, ob menschliche Spieler im offiziellen Spiel 32768 erreicht haben (dh ohne Werkzeuge wie Savestates oder Undo). Ich denke, die 65536 Fliese ist in Reichweite!

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

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

Derzeit erreicht das Programm eine Gewinnrate von etwa 90%, die in Javascript im Browser auf meinem Laptop ausgeführt wird, wenn etwa 100 Millisekunden Denkzeit pro Zug benötigt werden. Obwohl es (noch!) Nicht perfekt ist, funktioniert es ziemlich gut.

Da das Spiel ein diskreter Zustandsraum, perfekte Informationen, rundenbasiertes Spiel wie Schach und Dame ist, habe ich die gleichen Methoden verwendet, die sich bei diesen Spielen bewährt haben, nämlich die Minimax- Suche mit Alpha-Beta-Bereinigung . Da es bereits viele Informationen zu diesem Algorithmus gibt, werde ich nur auf die beiden wichtigsten Heuristiken eingehen, die ich in der statischen Bewertungsfunktion verwende und die viele der Intuitionen formalisieren, die andere Leute hier ausgedrückt haben.

Monotonie

Diese Heuristik versucht sicherzustellen, dass die Werte der Kacheln sowohl in der linken / rechten als auch in der oberen / unteren Richtung entweder zunehmen oder abnehmen. Diese Heuristik allein fängt die Intuition ein, die viele andere erwähnt haben, dass höherwertige Kacheln in einer Ecke gruppiert werden sollten. Dies verhindert normalerweise, dass Kacheln mit kleinerem Wert verwaist werden, und hält das Brett sehr gut organisiert, wobei kleinere Kacheln in die größeren Kacheln fallen und diese füllen.

Hier ist ein Screenshot eines perfekt monotonen Gitters. Ich habe dies erhalten, indem ich den Algorithmus mit der Bewertungsfunktion ausgeführt habe, die so eingestellt ist, dass die anderen Heuristiken ignoriert werden und nur die Monotonie berücksichtigt wird.

Glätte

Die obige Heuristik allein neigt dazu, Strukturen zu erzeugen, bei denen benachbarte Kacheln an Wert verlieren, aber zum Zusammenführen müssen benachbarte Kacheln natürlich den gleichen Wert haben. Daher misst die Glättungsheuristik nur die Wertdifferenz zwischen benachbarten Kacheln und versucht, diese Anzahl zu minimieren.

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

Hier ist ein Screenshot eines perfekt glatten Gitters, dank dieser hervorragenden Parodiegabel .

Kostenlose Fliesen

Und schließlich gibt es eine Strafe für zu wenige freie Kacheln, da die Optionen schnell ausgehen können, wenn das Spielbrett zu eng wird.

Und das ist es! Das Durchsuchen des Spielraums unter Optimierung dieser Kriterien führt zu einer bemerkenswert guten Leistung. Ein Vorteil der Verwendung eines solchen verallgemeinerten Ansatzes anstelle einer explizit codierten Bewegungsstrategie besteht darin, dass der Algorithmus häufig interessante und unerwartete Lösungen finden kann. Wenn Sie es laufen sehen, macht es oft überraschende, aber effektive Bewegungen, wie das plötzliche Umschalten der Wand oder Ecke, gegen die es sich aufbaut.

Bearbeiten:

Hier ist eine Demonstration der Leistungsfähigkeit dieses Ansatzes. Ich habe die Kachelwerte aufgehoben (so dass sie nach Erreichen von 2048 weitergingen) und hier ist das beste Ergebnis nach acht Versuchen.

Ja, das ist ein 4096 neben einem 2048. =) Das heißt, es hat das schwer fassbare 2048-Plättchen dreimal auf demselben Brett erreicht.

Ich interessierte mich für die Idee einer KI für dieses Spiel, die keine fest codierte Intelligenz enthält (dh keine Heuristiken, Bewertungsfunktionen usw.). Die KI sollte nur die Spielregeln "kennen" und das Spiel "herausfinden" . Dies steht im Gegensatz zu den meisten AIs (wie die in diesem Thread), bei denen das Spiel im Wesentlichen durch rohe Gewalt gesteuert wird, die durch eine Bewertungsfunktion gesteuert wird, die das menschliche Verständnis des Spiels darstellt.

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älligen Zügen, bis das Spiel vorbei ist. Dies geschieht mehrmals, während die Punktzahl des Endspiels verfolgt wird. Dann wird die durchschnittliche Endpunktzahl pro Startzug berechnet. Der Startzug mit der höchsten durchschnittlichen Endpunktzahl wird als nächster Zug ausgewählt.

Mit nur 100 Läufen (dh in Memory-Spielen) pro Zug erreicht die KI in 80% der Fälle die 2048-Kachel und in 50% der Fälle die 4096-Kachel. Bei Verwendung von 10000 Läufen erhalten Sie die 2048-Kachel 100%, 70% für die 4096-Kachel und etwa 1% für die 8192-Kachel.

Sehen Sie es in Aktion

Die am besten erzielte Punktzahl wird hier angezeigt:

Eine interessante Tatsache bei diesem Algorithmus ist, dass die Auswahl der besten (oder am wenigsten schlechten) Züge zu einem sehr guten Spiel führt, obwohl die Zufallsspiele nicht überraschend schlecht sind: Ein typisches KI-Spiel kann 70000 Punkte und die letzten 3000 Züge erreichen In-Memory-Zufallsspiele von einer bestimmten 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 KI ausführen und die Debug-Konsole öffnen.)

Diese Grafik zeigt diesen Punkt: Die blaue Linie zeigt die Brettpunktzahl nach jedem Zug. Die rote Linie zeigt die beste zufällige Punktzahl des Algorithmus für das Endspiel von dieser Position aus. Im Wesentlichen "ziehen" die roten Werte die blauen Werte nach oben zu ihnen, da sie die beste Vermutung des Algorithmus sind. Es ist interessant zu sehen, dass die rote Linie an jedem Punkt nur ein kleines Stück über der blauen Linie liegt, aber die blaue Linie nimmt immer mehr zu.

Ich finde es ziemlich überraschend, dass der Algorithmus kein gutes Spiel voraussehen muss, um die Bewegungen auszuwählen, die ihn erzeugen.

Bei einer späteren Suche stellte ich fest, dass dieser Algorithmus möglicherweise als reiner Monte-Carlo-Baumsuchalgorithmus klassifiziert ist .

Implementierung und Links

Zuerst habe ich eine JavaScript-Version erstellt, die hier in Aktion zu sehen ist . Diese Version kann Hunderte von Läufen in angemessener Zeit ausführen. Öffnen Sie die Konsole für zusätzliche Informationen. ( Quelle )

Später habe ich die hochoptimierte @ nneonneo-Infrastruktur verwendet und meine Version in C ++ implementiert, um ein bisschen mehr herumzuspielen. Diese Version ermöglicht bis zu 100000 Läufe pro Zug und sogar 1000000, wenn Sie die Geduld haben. Bauanleitung zur Verfügung gestellt. Es läuft in der Konsole und verfügt auch über eine Fernbedienung zum Abspielen der Webversion. ( Quelle )

Ergebnisse

Überraschenderweise verbessert das Erhöhen der Anzahl der Läufe das Spiel nicht drastisch. Es scheint eine Grenze für diese Strategie bei etwa 80000 Punkten mit dem 4096-Plättchen und allen kleineren zu geben, sehr nahe am Erreichen des 8192-Plättchens. Wenn Sie die Anzahl der Läufe von 100 auf 100000 erhöhen, erhöht sich die Wahrscheinlichkeit, dass Sie dieses Punktelimit erreichen (von 5% auf 40%), ohne es zu durchbrechen.

Durch Ausführen von 10000 Läufen mit einer vorübergehenden Erhöhung auf 1000000 in der Nähe kritischer Positionen konnte diese Barriere in weniger als 1% der Fälle durchbrochen werden, wobei eine maximale Punktzahl von 129892 und die 8192-Kachel erreicht wurden.

Verbesserungen

Nach der Implementierung dieses Algorithmus habe ich viele Verbesserungen versucht, einschließlich der Verwendung der Min- oder Max-Scores oder einer Kombination aus Min, Max und Avg. Ich habe auch versucht Tiefe mit: Statt K Läufe pro Zug zu versuchen , habe ich versucht , K bewegt sich pro Zug Liste einer bestimmten Länge ( „ nach oben, oben, links“ zum Beispiel) und den ersten Schritt der besten Scoring Zugliste auswählen.

Später implementierte ich einen Bewertungsbaum, der die bedingte Wahrscheinlichkeit berücksichtigte, einen Zug nach einer bestimmten Zugliste 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 Läufe versehentlich die nächsthöhere Kachel erreichte. Dies bot eine Zeitverbesserung.

Es würde mich interessieren 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 die KI auch als Lesezeichen implementiert und mich in die Steuerung des Spiels eingebunden. Dadurch kann die KI mit dem Originalspiel und vielen seiner Varianten arbeiten .

Dies ist aufgrund der domänenunabhängigen Natur der KI möglich. Einige der Varianten sind sehr unterschiedlich, wie beispielsweise der hexagonale Klon.

BEARBEITEN: Dies ist ein naiver Algorithmus, der den menschlichen bewussten Denkprozess modelliert und im Vergleich zu KI, die alle Möglichkeiten durchsucht, sehr schwache Ergebnisse erzielt, da nur eine Kachel vorausschaut. Es wurde früh in der Antwortzeitleiste eingereicht.

Ich habe den Algorithmus verfeinert und das Spiel geschlagen! Es kann aufgrund von einfachem Pech gegen Ende fehlschlagen (Sie sind gezwungen, sich nach unten zu bewegen, was Sie niemals tun sollten, und es erscheint eine Kachel dort, wo Ihre höchste sein sollte. Versuchen Sie einfach, die oberste Reihe gefüllt zu halten, damit Sie sich nicht nach links bewegen brechen Sie das Muster), aber im Grunde haben Sie am Ende einen festen Teil und einen mobilen Teil, mit dem Sie spielen können. Dies ist Ihr Ziel:

Dies ist das Modell, das ich standardmäßig ausgewä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, Sie drücken im Grunde nie eine Taste (die verbotene Bewegung), und wenn Sie dies tun, drücken Sie erneut das Gegenteil und versuchen, es zu reparieren. Für zukünftige Kacheln erwartet das Modell immer, dass die nächste zufällige Kachel eine 2 ist und auf der dem aktuellen Modell gegenüberliegenden Seite angezeigt wird (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 immer möglich zu sein, mit "professionelleren" KI-Techniken zu gewinnen, da bin ich mir jedoch 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:

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

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

Und die Kette, um dorthin zu gelangen, ist geworden:

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

Die Ostellen verbotene Räume dar ...

Also drückt es nach rechts, dann wieder nach rechts und dann (rechts oder oben, je nachdem, wo die 4 erstellt wurde), um die Kette zu vervollständigen, bis sie Folgendes erhält:

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 hatte Pech und sein Hauptplatz wurde eingenommen. Es ist wahrscheinlich, dass es scheitern wird, aber es kann es trotzdem erreichen:

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 die 128 erreicht, gewinnt es eine ganze Reihe, die wieder gewonnen wird:

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

Ich kopiere hier den Inhalt eines Beitrags in meinem Blog

Die von mir vorgeschlagene Lösung ist sehr einfach und leicht zu implementieren. Obwohl es die Punktzahl von 131040 erreicht hat, werden mehrere Benchmarks der Algorithmusleistungen vorgestellt.

Algorithmus

Heuristischer Bewertungsalgorithmus

Die Annahme, auf der mein Algorithmus basiert, ist ziemlich einfach: Wenn Sie eine höhere Punktzahl erzielen möchten, muss das Board so ordentlich wie möglich gehalten werden. Der optimale Aufbau ist insbesondere durch eine lineare und monoton abnehmende Reihenfolge der Kachelwerte gegeben. Diese Intuition gibt Ihnen auch die Obergrenze für einen Kachelwert: wobei n die Anzahl der Kacheln auf dem Brett ist.

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

In den folgenden Bildern sind zwei Möglichkeiten zur Organisation des Boards dargestellt:

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

Es können mehrere lineare Pfade gleichzeitig ausgewertet werden. Die endgültige Punktzahl ist die maximale Punktzahl eines Pfades.

Entscheidungsregel

Die implementierte Entscheidungsregel ist nicht ganz klug, 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 sicherlich verbessern. Offensichtlich wird eine ausgefeiltere Entscheidungsregel den Algorithmus verlangsamen und die Implementierung einige Zeit in Anspruch nehmen. Ich werde in naher Zukunft eine Minimax-Implementierung versuchen. (Bleib dran)

Benchmark

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

Im Fall von T2 erzeugen vier von zehn Tests die Kachel 4096 mit einer durchschnittlichen Punktzahl von 42000

Code

Der Code ist auf GiHub unter folgendem Link zu finden: https://github.com/Nicola17/term2048-AI Er basiert auf term2048 und ist in Python geschrieben. Ich werde so schnell wie möglich eine effizientere Version in C ++ implementieren.

Mein Versuch verwendet Expectimax wie andere Lösungen oben, jedoch ohne Bitboards. Die Lösung von Nneonneo kann 10 Millionen Züge überprüfen, was ungefähr einer Tiefe von 4 entspricht, wobei 6 Kacheln übrig bleiben und 4 Züge möglich sind (2 * 6 * 4) ⁴ . In meinem Fall dauert das Erkunden dieser Tiefe zu lange. Ich passe die Tiefe der Expectimax-Suche an die Anzahl der verbleibenden freien Kacheln an:

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

Die Punktzahlen der Bretter werden mit der gewichteten Summe des Quadrats der Anzahl der freien Kacheln und dem Punktprodukt 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]]

Dies zwingt dazu, die Kacheln in einer Art Schlange von der oberen linken Kachel absteigend zu organisieren.

Code unten oder auf Github :

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);
updateHint(predict(ai));

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


function updateHint(dir) {
	hintvalue.innerHTML = ['↑', '→', '↓', '←'][dir] || '';
}

document.addEventListener("keydown", function(event) {
	if (!event.target.matches('.r *')) return;
	event.preventDefault(); // avoid scrolling
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai);
		updateHint(predict(ai));
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai);
	updateHint(predict(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 {
	font-family: Arial;
}
table, th, td {
	border: 1px solid black;
	margin: 0 auto;
	border-collapse: collapse;
}
td {
	width: 35px;
	height: 35px;
	text-align: center;
}
button {
	margin: 2px;
	padding: 3px 15px;
	color: rgba(0,0,0,.9);
}
.r {
	display: flex;
	align-items: center;
	justify-content: center;
	margin: .2em;
	position: relative;
}
#hintvalue {
	font-size: 1.4em;
	padding: 2px 8px;
	display: inline-flex;
	justify-content: center;
	width: 30px;
}

<table title="press arrow keys"></table>
<div class="r">
    <button id=init>init</button>
    <button id=runai>run AI</button>
    <span id="hintvalue" title="Best predicted move to do, use your arrow keys" tabindex="-1"></span>
</div>

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 auf github verfügbar . In einem separaten Repo gibt es auch den Code, der zum Trainieren der Zustandsbewertungsfunktion des Controllers verwendet wird. Die Trainingsmethode ist in der Arbeit beschrieben .

Der Controller verwendet die Expectimax-Suche mit einer Zustandsbewertungsfunktion, die von Grund auf neu gelernt wurde (ohne menschliches 2048-Fachwissen), und zwar durch eine Variante des zeitlichen Differenzlernens (eine verstärkende Lerntechnik). Die Zustandswertfunktion verwendet ein n-Tupel-Netzwerk , bei dem es sich im Wesentlichen um eine gewichtete lineare Funktion der auf der Karte beobachteten Muster handelt. Insgesamt handelte es sich um mehr als 1 Milliarde Gewichte .

Performance

Bei 1 Zügen / s: 609104 (100 Spiele durchschnittlich)

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

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

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

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

(Die letzte Zeile bedeutet, dass die angegebenen Kacheln gleichzeitig auf dem Brett liegen).

Für 3-lagige:

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

Ich habe jedoch nie beobachtet, dass es die 65536-Kachel erhielt.

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

Bitte beachten Sie den Code unten:

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);
}

Es gibt bereits eine AI - Implementierung für dieses Spiel hier . Auszug aus README:

Der Algorithmus ist die iterative Vertiefung der Tiefe der ersten Alpha-Beta-Suche. Die Auswertungsfunktion versucht, die Zeilen und Spalten monoton zu halten (entweder alle abnehmend oder zunehmend), während die Anzahl der Kacheln im Raster minimiert wird.

In Hacker News gibt es auch eine Diskussion über diesen Algorithmus, die Sie möglicherweise nützlich finden.

Algorithmus

while(!game_over)
{
    for each possible move:
        evaluate next state

    choose the maximum evaluation
}

Auswertung

Evaluation =
    128 (Constant)
    + (Number of Spaces x 128)
    + Sum of faces adjacent to a space { (1/face) x 4096 }
    + Sum of other faces { log(face) x 4 }
    + (Number of possible next moves x 256)
    + (Number of aligned values x 2)

Bewertungsdetails

128 (Constant)

Dies ist eine Konstante, die als Basislinie und für andere Zwecke wie das Testen verwendet wird.

+ (Number of Spaces x 128)

Mehr Leerzeichen machen den Zustand flexibler. Wir multiplizieren mit 128 (was der Median ist), da ein mit 128 Flächen gefülltes Gitter ein optimal unmöglicher Zustand ist.

+ Sum of faces adjacent to a space { (1/face) x 4096 }

Hier bewerten wir Gesichter, die die Möglichkeit haben, zusammenzuführen, indem wir sie rückwärts auswerten. Kachel 2 hat den Wert 2048, während Kachel 2048 2 bewertet wird.

+ Sum of other faces { log(face) x 4 }

Hier müssen wir noch nach gestapelten Werten suchen, aber in geringerem Maße werden die Flexibilitätsparameter nicht unterbrochen, sodass wir die Summe von {x in [4,44]} haben.

+ (Number of possible next moves x 256)

Ein Staat ist flexibler, wenn er mehr Freiheit für mögliche Übergänge hat.

+ (Number of aligned values x 2)

Dies ist eine vereinfachte Überprüfung der Möglichkeit von Zusammenführungen innerhalb dieses Zustands, ohne einen Ausblick zu gewähren.

Hinweis: Die Konstanten können angepasst werden.

Dies ist keine direkte Antwort auf die Frage von OP. Dies sind mehr Dinge (Experimente), die ich bisher versucht habe, um das gleiche Problem zu lösen. Ich habe einige Ergebnisse erzielt und einige Beobachtungen gemacht, die ich teilen möchte. Ich bin gespannt, ob wir welche haben können weitere Erkenntnisse daraus.

Ich habe gerade meine Minimax-Implementierung mit Alpha-Beta-Bereinigung mit Suchbaum-Tiefenbegrenzung bei 3 und 5 versucht. Ich habe versucht, das gleiche Problem für ein 4x4-Raster wie eine Projektaufgabe für den edX-Kurs ColumbiaX zu lösen : CSMM.101x Künstliche Intelligenz ( AI) .

Ich habe eine konvexe Kombination (verschiedene heuristische Gewichte ausprobiert) mehrerer heuristischer Bewertungsfunktionen angewendet, hauptsächlich aus der Intuition und aus den oben diskutierten:

1. Monotonie
2. Freier Speicherplatz verfügbar

In meinem Fall ist der Computer-Player völlig zufällig, aber ich habe immer noch gegnerische Einstellungen angenommen und den AI-Player-Agenten als Max-Player implementiert.

Ich habe 4x4 Gitter für das Spiel.

Überwachung:

Wenn ich der ersten heuristischen Funktion oder der zweiten heuristischen Funktion zu viele Gewichte zuweise, sind in beiden Fällen die Punktzahlen, die der KI-Spieler erhält, niedrig. Ich habe mit vielen möglichen Gewichtszuweisungen für die heuristischen Funktionen gespielt und eine konvexe Kombination gewählt, aber sehr selten kann der KI-Spieler 2048 Punkte erzielen. Meistens stoppt er entweder bei 1024 oder 512.

Ich habe auch die Eckheuristik ausprobiert, aber aus irgendeinem Grund verschlechtert sie die Ergebnisse. Warum?

Außerdem habe ich versucht, den Grenzwert für die Suchtiefe von 3 auf 5 zu erhöhen (ich kann ihn nicht weiter erhöhen, da die Suche in diesem Bereich die zulässige Zeit auch beim Beschneiden überschreitet) und eine weitere Heuristik hinzugefügt, die die Werte benachbarter Kacheln berücksichtigt und gibt mehr Punkte, wenn sie zusammengeführt werden können, aber ich kann immer noch nicht 2048 bekommen.

Ich denke, es ist besser, Expectimax anstelle von Minimax zu verwenden, aber ich möchte dieses Problem nur mit Minimax lösen und hohe Punktzahlen wie 2048 oder 4096 erzielen. Ich bin mir nicht sicher, ob mir etwas fehlt.

Die folgende Animation zeigt die letzten Schritte des Spiels, das der KI-Agent mit dem Computerspieler gespielt hat:

Alle Einblicke werden wirklich sehr hilfreich sein, danke im Voraus. (Dies ist der Link meines Blogposts für den Artikel: https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve -2048-Spiel-mit-Computer / und das Youtube-Video: https://www.youtube.com/watch?v=VnVFilfZ0r4 )

Die folgende Animation zeigt die letzten Schritte des Spiels, in denen der KI-Spieler-Agent 2048 Punkte erzielen konnte, diesmal auch mit der absoluten Heuristik:

Die folgenden Abbildungen zeigen den Spielbaum, den der KI-Agent des Spielers untersucht hat, indem er den Computer für nur einen Schritt als Gegner annimmt:

Ich habe in Haskell einen 2048-Solver geschrieben, hauptsächlich, weil ich diese Sprache gerade lerne.

Meine Implementierung des Spiels unterscheidet sich geringfügig vom eigentlichen Spiel darin, dass ein neues Plättchen immer eine '2' ist (anstatt 90% 2 und 10% 4). Und dass die neue Kachel nicht zufällig ist, sondern immer die erste verfügbare von oben links. Diese Variante ist auch als Det 2048 bekannt .

Infolgedessen ist dieser Löser deterministisch.

Ich habe einen umfassenden Algorithmus verwendet, der leere Kacheln bevorzugt. Es funktioniert ziemlich schnell für Tiefe 1-4, aber in Tiefe 5 wird es mit etwa 1 Sekunde pro Bewegung ziemlich langsam.

Unten finden Sie den Code, der den Lösungsalgorithmus implementiert. Das Raster wird als 16-faches Array von Ganzzahlen dargestellt. Die Wertung erfolgt einfach durch Zählen der Anzahl der leeren Quadrate.

bestMove :: Int -> [Int] -> Int
bestMove depth grid = maxTuple [ (gridValue depth (takeTurn x grid), x) | x <- [0..3], takeTurn x grid /= [] ]

gridValue :: Int -> [Int] -> Int
gridValue _ [] = -1
gridValue 0 grid = length $ filter (==0) grid  -- <= SCORING
gridValue depth grid = maxInList [ gridValue (depth-1) (takeTurn x grid) | x <- [0..3] ]

Ich denke, es ist ziemlich erfolgreich für seine Einfachheit. Das Ergebnis, das erreicht wird, wenn mit einem leeren Gitter begonnen und in Tiefe 5 gelöst wird, ist:

Move 4006
[2,64,16,4]
[16,4096,128,512]
[2048,64,1024,16]
[2,4,16,2]

Game Over

Der Quellcode ist hier zu finden: https://github.com/popovitsj/2048-haskell

Dieser Algorithmus ist nicht optimal für den Gewinn des Spiels, aber in Bezug auf Leistung und Menge des benötigten Codes ziemlich optimal:

  if(can move neither right, up or down)
    direction = left
  else
  {
    do
    {
      direction = random from (right, down, up)
    }
    while(can not move in "direction")
  }

Viele der anderen Antworten verwenden KI für die rechenintensive Suche nach möglichen Zukünften, Heuristiken, Lernen und dergleichen. Diese sind beeindruckend und wahrscheinlich der richtige Weg, aber ich möchte eine andere Idee einbringen.

Modellieren Sie die Art von Strategie, die gute Spieler des Spiels verwenden.

Zum Beispiel:

13 14 15 16
12 11 10  9
 5  6  7  8
 4  3  2  1

Lesen Sie die Quadrate in der oben gezeigten Reihenfolge, bis der Wert der nächsten Quadrate größer als der aktuelle ist. Dies stellt das Problem dar, zu versuchen, eine andere Kachel mit demselben Wert in diesem Quadrat zusammenzuführen.

Um dieses Problem zu lösen, gibt es zwei Möglichkeiten, sich zu bewegen, die nicht übrig bleiben oder noch schlimmer sind. Wenn Sie beide Möglichkeiten untersuchen, werden möglicherweise sofort weitere Probleme angezeigt. Dies bildet eine Liste von Abhängigkeiten, wobei für jedes Problem zuerst ein anderes Problem gelöst werden muss. Ich glaube, ich habe diese Kette oder in einigen Fällen einen Baum von Abhängigkeiten intern, wenn ich mich für meinen nächsten Schritt entscheide, besonders wenn ich feststecke.

Die Kachel muss mit dem Nachbarn zusammengeführt werden, ist aber zu klein: Füge einen anderen Nachbarn mit diesem zusammen.

Größere Kachel im Weg: Erhöhen Sie den Wert einer kleineren umgebenden Kachel.

usw...

Der gesamte Ansatz wird wahrscheinlich komplizierter sein, aber nicht viel komplizierter. Es könnte dieses mechanische Gefühl sein, dem es an Punktzahlen, Gewichten, Neuronen und einer tiefen Suche nach Möglichkeiten mangelt. Der Baum der Möglichkeiten muss sogar groß genug sein, um überhaupt eine Verzweigung zu benötigen.