Bubble Breaker Game Solver besser als gierig?

Question

Als Denksportaufgabe beschloss ich, das Spiel "Bubble Breaker" zu lösen, das auf vielen Handys zu finden ist, wie auch ein Beispiel hier: Bubble Break Spiel

• Das zufällige (N,M,C) Brett besteht aus N Zeilen x M Spalten mit C Farben
• Ziel ist es, die höchste Punktzahl zu erreichen, indem man die Reihenfolge der Blasengruppen auswählt, die letztendlich zur höchsten Punktzahl führt
• Eine Blasengruppe besteht aus 2 oder mehr gleichfarbigen Blasen, die entweder in x- oder in y-Richtung nebeneinander liegen. Diagonalen zählen nicht mit
• Wenn eine Gruppe ausgewählt wird, verschwinden die Blasen, alle Löcher werden zuerst mit Blasen von oben gefüllt, d.h. nach unten verschieben, dann werden alle Löcher durch Verschieben nach rechts gefüllt
• Punktzahl einer Blasengruppe = n * (n - 1), wobei n die Anzahl der Blasen in der Blasengruppe ist

Der erste Algorithmus ist ein einfacher, erschöpfender, rekursiver Algorithmus, der das Brett Zeile für Zeile und Spalte für Spalte durchforstet und dabei Blasengruppen auswählt. Sobald die Blasengruppe ausgewählt ist, erstellen wir ein neues Brett und versuchen, dieses Brett zu lösen, indem wir rekursiv nach unten gehen

Einige der Ideen, die ich verwende, sind die normalisierte Memoisierung. Sobald ein Brett gelöst ist, speichern wir das Brett und die beste Punktzahl in einer Memoisierungstabelle.

Ich erstelle eine Prototyp in Python die zeigt, dass ein (2,15,5)-Brett in etwa 3 Sekunden 8859 Bretter zu lösen braucht. Ein (3,15,5)-Brett benötigt 12.384.726 Bretter in 50 Minuten auf einem Server. Die Lösungsrate beträgt ~3k-4k Bretter/Sekunde und nimmt allmählich ab, wenn die Memoisierungssuche länger dauert. Die Memoisierungstabelle wächst auf 5.692.482 Bretter an und wird 6.713.566 Mal getroffen.

Welche anderen Ansätze könnten neben der erschöpfenden Suche zu hohen Punktzahlen führen?

Ich sehe keine offensichtliche Möglichkeit, zu teilen und zu erobern. Aber die Tendenz zu immer größeren Blasengruppen scheint ein Ansatz zu sein

Vielen Dank an David Locke für den Link zu dem Papier, in dem von einem Fensterlöser die Rede ist, der eine Heuristik mit konstanter Tiefe verwendet.

Answer 1

Según dieses Papier Die Bestimmung, ob man das Brett leeren kann (was mit dem zu lösenden Problem zusammenhängt), ist NP-vollständig. Das bedeutet nicht, dass man keinen guten Algorithmus finden kann, es bedeutet nur, dass man wahrscheinlich keinen effizienten finden wird.

Answer 2

Ich denke, Sie könnten eine verzweigte und gebundene Suche mit der folgenden Idee versuchen:

1. Bei einem Spielzustand S verzweigt man auf S, indem man es in m Mengen Si zerlegt, wobei jede Si der Zustand nach einem erlaubten Zug aller m erlaubten Züge bei dem Zustand S ist

2. Sie benötigen zwei Funktionen U(S) und L(S), die eine untere bzw. obere Schranke für einen bestimmten Zustand S berechnen.

   Für die Funktion U(S) denke ich an die Berechnung der Punktzahl, die Sie erhalten würden, wenn Sie in der Lage wären, K Blasen auf dem Brett frei zu mischen (bei jedem Zug) und die Blöcke so anzuordnen, dass die höchste Punktzahl erreicht wird, wobei K ein Wert ist, den Sie selbst wählen. Bei der Berechnung von U(S) für ein gegebenes S sollte es schneller gehen, wenn Sie einen höheren Wert für K wählen (die Bedingungen sind entspannt), so dass die Wahl des Werts von K ein Kompromiss zwischen der Schnelligkeit, mit der Sie U(S) finden, und der Qualität ist (wie eng die obere Grenze von U(S) ist).

   Berechnen Sie für die Funktion L(S) die Punktzahl, die Sie erhalten würden, wenn Sie einfach wahllos so lange klicken würden, bis Sie einen Zustand erreichen, der nicht mehr gelöst werden kann. Sie können dies mehrere Male tun und die höchste untere Grenze nehmen, die Sie erhalten.

Sobald Sie über diese beiden Funktionen verfügen, können Sie die Standardsuche "Gebundene Suche" und "Verzweigung" anwenden. Beachten Sie, dass die Geschwindigkeit Ihrer Suche stark davon abhängt, wie eng Ihre obere und untere Grenze ist.

Answer 3

Um eine schnellere Lösung als die erschöpfende Suche zu erhalten, benötigen Sie wahrscheinlich eine dynamische Programmierung. Bei der dynamischen Programmierung finden Sie eine Art "Schritt", der Sie möglicherweise näher an Ihre Lösung bringt, und halten die Ergebnisse jedes Schritts in einer großen Matrix fest. Sobald Sie die Matrix ausgefüllt haben, können Sie das beste Ergebnis finden und dann rückwärts arbeiten, um einen Weg durch die Matrix zu finden, der zum besten Ergebnis führt. Die Matrix ist praktisch eine Form der Memoisierung.

Die dynamische Programmierung wird erörtert in Das Handbuch zum Algorithmenentwurf aber es gibt auch viele Diskussionen darüber im Internet. Hier ist eine gute Einführung: http://20bits.com/articles/introduction-to-dynamic-programming/

Ich bin mir nicht sicher, was genau der "Schritt" für dieses Problem ist. Vielleicht könnte man eine Wertungsmetrik für eine Tafel erstellen, die einfach die Punkte für jede der Blasengruppen zusammenzählt, und dann diese Punktzahl aufzeichnen, während man versucht, Ballons platzen zu lassen? Gute Schritte würden dazu führen, dass die Blasengruppen zusammenwachsen, was die Punktzahl verbessern würde, und schlechte Schritte würden die Blasengruppen auflösen, was die Punktzahl verschlechtern würde.

Answer 4

Man kann dieses Problem in das Problem der Suche nach dem kürzesten Weg im Graphen übersetzen. http://en.wikipedia.org/wiki/Shortest_path_problem

Ich würde es mit A* versuchen und die Heuristik würde die Anzahl der Inseln einschließen.

Answer 5

In meinem Schachprogramm verwende ich einige Ideen, die wahrscheinlich an dieses Problem angepasst werden könnten.

• Bestellung verschieben. Finden Sie zunächst alle möglichen Züge, speichern Sie sie in einer Liste, und sortiere sie nach einer Heuristik. Die "besseren" Züge zuerst, die "schlechten" zuletzt. Zum Beispiel, könnte dies eine Funktion der Größe der Gruppe sein der Gruppe sein (bevorzugt mittelgroße Gruppen), oder die Anzahl der benachbarten Farben, Gruppen, etc.

• Iterative Vertiefung. Anstatt eine reine Tiefensuche durchzuführen, die Suche nach einer bestimmten Tiefe ab und verwenden eine Heuristik zur Bewertung das Ergebnis. Untersuchen Sie nun den Baum mit "besseren" Zügen zuerst.

• Beschneiden. Suchen Sie nicht nach Zügen, die die "offensichtlich" schlecht erscheinen, gemäß wieder eine Heuristik. Dies beinhaltet das Risiko, dass Sie nicht mehr die optimale Lösung nicht mehr finden, sondern aber je nach Heuristik werden Sie finden Sie sie sehr wahrscheinlich viel früher.

• Hash-Tabellen. Sie müssen nicht jede Board zu speichern, sondern nur eine bestimmte eine bestimmte Anzahl und überschreibt ältere überschreiben.