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

Ich bin fast fertig mit dem Schreiben meiner Version des "Solvers" in Java. Er führt sowohl eine erschöpfende Suche durch, die bei größeren Brettern verdammt lange dauert, als auch eine gerichtete Suche auf der Grundlage eines "Pools" möglicher Pfade, der nach jeder Generation beschnitten wird, und einer Fitnessfunktion, die zum Beschneiden des Pools verwendet wird. Ich versuche gerade, die Fitnessfunktion zu optimieren...

Update - dieser Artikel ist jetzt verfügbar unter http://bubblesolver.sourceforge.net/

Answer 2

Dies ist nicht mein Fachgebiet, aber ich möchte Ihnen ein Buch empfehlen. Besorgen Sie sich ein Exemplar von Das Handbuch zum Algorithmenentwurf von Steven Skiena. Es enthält eine ganze Liste verschiedener Algorithmen, und wenn man es einmal durchgelesen hat, kann man es als Nachschlagewerk verwenden. Zumindest wird es Ihnen helfen, Ihre Optionen zu prüfen.