Algorithmus zur Optimierung eines Matchspiels mit bekannter Warteschlange

Ich versuche, einen Löser in C # .NET für ein Spiel namens Flowerz zu schreiben. Als Referenz können Sie es auf MSN hier abspielen: http://zone.msn.com/gameplayer/gameplayer.aspx?game=flowerz . Ich schreibe es zum Spaß, nicht für irgendeine Art von Aufgabe oder irgendetwas, was mit Arbeit zu tun hat. Aus diesem Grund ist die einzige Einschränkung mein Computer (ein Intel i7-Kern mit 8 GB RAM). Für mich muss es nirgendwo anders laufen.

Kurz gesagt, die Regeln lauten wie folgt:

• Es gibt eine Schlange mit bunten Blumen. Ihre Länge ist beliebig
  • Die Warteschlange kann nicht beeinflusst werden
  • Die Warteschlange wird zu Beginn des Levels generiert
• Blumen haben entweder eine oder zwei Farben.
  • Wenn es zwei Farben gibt, gibt es eine äußere Farbe und eine innere Farbe. Bei zwei Farben wird die Außenfarbe zum Abgleichen verwendet.
  • Wenn es eine Übereinstimmung gibt, verschwindet die äußere Farbe und die Blume ist jetzt eine einfarbige Blume mit der gleichen Farbe wie die innere Blume
• Das Ziel des Spiels ist es, Übereinstimmungen mit drei (oder mehr) derselben Farbe zu erstellen
  • Wenn eine einzelne Blume Teil eines Spiels ist, wird sie vom Spielfeld entfernt, wodurch ein leerer Raum entsteht
  • Sie können eine einfarbige Blume mit der Außenfarbe einer zweifarbigen Blume vergleichen. In diesem Fall verschwindet die einfarbige Blume, die äußere Farbe der zweifarbigen Blume verschwindet und die innere Farbe bleibt erhalten
• Sie gewinnen die Runde, wenn die Warteschlange leer ist und mindestens ein Platz frei ist
• Kaskadierende Übereinstimmungen sind möglich. Eine Kaskade ist, wenn drei (oder mehr) äußere Blüten verschwinden und wenn ihre inneren Farben eine weitere Kette von drei (oder mehr Blüten) bilden.
• Das Spielfeld ist immer 7x7
• Einige Felder auf dem Feld sind von Steinen bedeckt
  • Sie können keine Blumen auf Felsen legen
• Die Warteschlange kann auch einen Spaten enthalten, mit dem Sie jede platzierte Blume an einen freien Platz verschieben können
  • Sie müssen den Spaten verwenden, aber Sie müssen die Blume nicht wirklich bewegen: Es ist völlig legal, sie direkt von der Stelle zu platzieren, an der sie gekommen ist
• Die Warteschlange kann auch einen farbigen Schmetterling enthalten. Wenn Sie diesen Schmetterling auf einer Blume verwenden, erhält die Blume die Farbe des Schmetterlings
  • Das Anwenden eines Schmetterlings auf eine Blume mit zwei Farben führt dazu, dass die Blume nur eine einzige Farbe erhält, nämlich die des Schmetterlings
  • Sie können den Schmetterling auf einem leeren Platz oder einer Blume verschwenden, die bereits diese Farbe hat
• Das Löschen des Feldes gewinnt das Spiel nicht

Das Ziel des Lösers ist einfach: Finden Sie einen Weg, die Warteschlange mit möglichst vielen verbleibenden Feldern auf dem Spielfeld zu leeren. Grundsätzlich spielt die KI das Spiel für mich. Die Ausgabe des Solvers ist eine Liste mit gefundenen Bewegungen. Ich bin nicht an Partituren interessiert, sondern daran, so lange wie möglich zu überleben. Daher interessiere ich mich für die Bewegungen, die so viele Freiräume wie möglich lassen.

Es ist unnötig zu erwähnen, dass der Suchraum mit zunehmender Warteschlange schnell wächst, sodass eine rohe Gewalt nicht in Frage kommt. Die Warteschlange beginnt bei 15 und wächst mit 5 alle zwei oder drei Ebenen, wenn ich mich recht erinnere. Und natürlich unterscheidet sich das Platzieren der ersten Blume auf (0,0) und der zweiten auf (0,1) vom Platzieren der ersten auf (1,0) und der zweiten Blume auf (0,0), insbesondere wenn Das Feld ist bereits mit Blumen aus einer früheren Runde besiedelt. Eine so einfache Entscheidung könnte den Unterschied ausmachen, ob sie getroffen wird oder nicht.

Die Fragen, die ich habe, sind die folgenden:

• Was für ein Problem ist das? (Denken Sie an einen reisenden Verkäufer, einen Rucksack oder ein anderes kombinatorisches Problem). Wenn ich das weiß, könnte mein Google-Fu ein bisschen besser werden.
• Welche Art von Algorithmus könnte mir schnell gute Ergebnisse bringen?

Zu letzterem: Zuerst habe ich versucht, meinen eigenen heuristischen Algorithmus zu schreiben (im Grunde: Wie würde ich ihn lösen, wenn ich die Warteschlange wüsste?), Aber das führt zu vielen Randfällen und Scoring-Übereinstimmungen, die ich möglicherweise übersehen habe.

Ich habe überlegt, einen genetischen Algorithmus zu verwenden (weil ich zumindest weiß, wie man das benutzt ...), aber ich habe einige Probleme, mich für eine binäre Darstellung des Boards zu entscheiden. Dann gibt es das Crossover-Problem, das jedoch mit einem bestellten Crossover-Operator oder einer ähnlichen Art von Operation gelöst werden kann.

Ich vermute, dass der Solver immer die Board-Konfiguration und die Warteschlange kennen muss, die er zu leeren versucht.

Ich kenne einige andere heuristische Algorithmen wie neuronale Netze und Fuzzy-Logik-Systeme, aber mir fehlt die Erfahrung, um zu wissen, welcher am besten geeignet ist oder ob es andere gibt, die für die jeweilige Aufgabe besser geeignet sind.

Auf den ersten Blick scheint mir dies ein Problem bei der Suche nach einem einzelnen Agenten zu sein . Das heißt: Sie haben einen Agenten (den KI- "Spieler"). Es ist ein Spiel Zustand , den Zustand des Spielbretts und Warteschlange darstellt, und Sie haben eine Nachfolgerfunktion , die neuen Staaten aus einem gegebenen Zustand erzeugen kann.

Es gibt auch ein Zielkriterium , das Ihnen sagt, wann der Zustand der "gelöste" Zustand ist. Und Pfadkosten - die Kosten für das Vorrücken in einen bestimmten Zustand (in diesem Fall immer "1 Zug").

Ein prototypisches Puzzle dieser Art ist das 15-Puzzle . Die typische Lösung besteht in einer informierten Suche - zum Beispiel der klassischen heuristischen Suche A * und ihren Varianten.

Es gibt jedoch ein Problem mit diesem Ansatz auf den ersten Blick. Algorithmen wie A * sollen Ihnen den kürzesten Weg zu einem Ziel geben (zum Beispiel: kleinste Anzahl von Zügen). In Ihrem Fall ist die Anzahl der Züge immer festgelegt - es gibt keinen kürzesten Weg -, sodass Sie bei einer heuristischen Suche nur einen Weg zu einem abgeschlossenen Spiel finden.

Was Sie wollen, ist eine Abfolge von Zügen, die Ihnen den besten abgeschlossenen Spielstatus gibt.

Sie müssen das Problem also ein wenig umkehren. Anstatt dass das Spielbrett der "Zustand" ist, wird die Abfolge der Züge zum "Zustand". (Dh: Stellen Sie die Elemente in die Warteschlange an den Positionen "D2, A5, C7, B3, A3, ...")

Dies bedeutet, dass es uns egal ist, wie diese Zustände erzeugt werden. Die Tafel selbst ist zufällig und muss nur die Qualität eines bestimmten Staates bewerten.

Dies macht das Problem zu einem Optimierungsproblem , das mit einem lokalen Suchalgorithmus gelöst werden kann (was im Grunde bedeutet, Zustände um einen bestimmten Zustand herum zu erstellen und den besten Zustand auszuwählen, ohne sich um den Pfad zwischen Zuständen zu kümmern.)

Das prototypische Puzzle dieser Art ist das Eight Queens Puzzle .

In dieser Problemklasse suchen Sie im Zustandsraum nach einer guten Lösung, bei der "gut" durch eine objektive Funktion (auch als Bewertungsfunktion oder für genetische Algorithmen als Fitnessfunktion bezeichnet ) bewertet wird .

Für Ihr Problem gibt eine Zielfunktion möglicherweise einen Wert zwischen 0 und N für die Anzahl der Elemente in der Warteschlange zurück, die vor Erreichen eines Fehlerzustands verbraucht wurden (wobei N die Länge der Warteschlange ist). Andernfalls ein Wert von N + M, wobei M die Anzahl der Leerzeichen auf der Platine ist, nachdem die Warteschlange leer ist. Als solches - je höher der Wert, desto "objektiv besser" die Lösung.

(Es ist an dieser Stelle erwähnenswert, dass Sie den Mist aus dem Code, der das Spiel ausführt, optimieren sollten - das verwandelt einen Zustand in ein fertiges Brett, das für die Zielfunktion verwendet werden kann.)

Beispiele für lokale Suchalgorithmen : Das Grundmuster ist eine Bergsteigersuche , die einen bestimmten Zustand annimmt, ihn mutiert und zum nächsten Zustand übergeht, der ein besseres Ergebnis liefert.

Offensichtlich kann dies in lokalen Maxima (und dergleichen) stecken bleiben. In dieser Form wird es eine gierige lokale Suche genannt . Es gibt eine Reihe von Variationen, um dieses und andere Probleme zu lösen ( Wikipedia hat Sie behandelt ). Einige davon (z. B. lokale Strahlensuche ) verfolgen mehrere Zustände gleichzeitig.

Eine besondere Variation davon ist der genetische Algorithmus ( Wikipedia ). Die grundlegenden Schritte für einen genetischen Algorithmus sind:

1. Bestimmen Sie eine Möglichkeit, einen Status in eine Zeichenfolge umzuwandeln. In Ihrem Fall kann dies eine Folge von Ziffern mit Warteschlangenlänge von 1 bis 49 sein (die alle möglichen Platzierungen auf einer 7x7-Karte darstellen, die wahrscheinlich jeweils 1 Byte gespeichert sind). (Ihr "Spaten" -Stück könnte durch zwei aufeinanderfolgende Warteschlangeneinträge für jede Phase des Umzugs dargestellt werden.)
2. Wählen Sie nach dem Zufallsprinzip eine Brutpopulation aus, um Staaten mit besserer Fitness eine höhere Wahrscheinlichkeit zu geben . Die Brutpopulation sollte die gleiche Größe wie die ursprüngliche Population haben - Sie können Staaten aus der ursprünglichen Population mehrmals auswählen.
3. Koppeln Sie Zustände in der Brutpopulation (erster geht mit zweiter, dritter geht mit vierter usw.)
4. Wählen Sie zufällig Kreuzungspunkte für jedes Paar aus (eine Position in der Zeichenfolge).
5. Erstellen Sie zwei Nachkommen für jedes Paar, indem Sie den Teil der Saite nach dem Kreuzungspunkt austauschen.
6. Mutieren Sie zufällig jeden der Nachkommenzustände. Beispiel: Wählen Sie nach dem Zufallsprinzip eine zufällige Position in der Zeichenfolge in einen zufälligen Wert.
7. Wiederholen Sie den Vorgang mit der neuen Population, bis die Population zu einer oder mehreren Lösungen konvergiert (oder nach einer bestimmten Anzahl von Generationen oder wenn eine ausreichend gute Lösung gefunden wurde).

Eine genetische Algorithmus Lösung fühlt sich an wie es könnte für Ihr Problem geeignet sein - mit einigen Anpassungen. Die größte Schwierigkeit, die ich sehe, besteht darin, dass Sie mit der obigen Zeichenfolgendarstellung feststellen werden, dass das Umschalten der hinteren Hälften von Zuständen mit sehr unterschiedlichen vorderen Hälften wahrscheinlich zu "toten" Zuständen führt (aufgrund widersprüchlicher Bewegungen zwischen den beiden Hälften, die sich ergeben in einem niedrigen Fitness-Score).

Vielleicht ist es möglich, dieses Problem zu überwinden. Eine Idee, die mir in den Sinn kommt, ist es, Staaten mit ähnlichen Vorderhälften eher zu Brutpaaren zu machen. Dies könnte so einfach sein, wie die Brutpopulation von Staaten zu sortieren, bevor sie gepaart werden. Es kann auch hilfreich sein, die wahrscheinliche Position der Frequenzweiche schrittweise vom Anfang bis zum Ende der Zeichenfolge zu verschieben, wenn die Generierungszahl zunimmt.

Es kann auch möglich sein, eine Darstellung von Bewegungen innerhalb eines Zustands zu erstellen, der widerstandsfähiger (möglicherweise sogar völlig immun) gegen das Auftreten des Fehlerzustands "Quadrat ist voll" ist. Möglicherweise werden Bewegungen als relative Koordinaten der vorherigen Bewegung dargestellt. Oder wenn Sie Bewegungen ausführen, wählen Sie den nächstgelegenen leeren Raum zur angegebenen Position aus.

Wie bei allen nicht trivialen KI-Problemen wie diesen ist ein erhebliches Basteln erforderlich.

Und wie ich bereits erwähnt habe, besteht die andere große Herausforderung darin, einfach Ihre Zielfunktion zu optimieren. Wenn Sie dies beschleunigen, können Sie viel Speicherplatz durchsuchen und nach Lösungen für Spiele mit längeren Warteschlangen suchen.

Für diese Antwort musste ich, insbesondere um die Terminologie richtig zu machen, mein Universitäts-KI-Lehrbuch "Künstliche Intelligenz: Ein moderner Ansatz" von Russell und Norvig ausgraben. Ich bin mir nicht sicher, ob es "gut" ist (ich habe keine anderen KI-Texte, mit denen ich es vergleichen kann), aber es ist nicht schlecht. Zumindest ist es ziemlich groß;)

Kategorisierung

Die Antwort ist nicht einfach. Die Spieltheorie hat einige Klassifikationen für Spiele, aber es scheint keine klare 1: 1-Übereinstimmung für dieses Spiel mit einer speziellen Theorie zu geben. Es ist eine spezielle Form des kombinatorischen Problems.

Es ist kein reisender Verkäufer, der sich für eine Reihenfolge entscheidet, in der Sie "Knoten" mit einigen Kosten besuchen, um den nächsten Knoten vom letzten zu erreichen. Sie können die Warteschlange nicht neu anordnen und müssen auch nicht alle Felder auf der Karte verwenden.

Der Rucksack stimmt nicht überein, da einige Felder leer werden, während einige Gegenstände in den "Rucksack" gelegt werden. Es ist also vielleicht eine erweiterte Form davon, aber höchstwahrscheinlich sind die Algorithmen aus diesem Grund nicht anwendbar.

Wikipedia gibt hier einige Hinweise zur Kategorisierung: http://en.wikipedia.org/wiki/Game_theory#Types_of_games

Ich würde es als "zeitdiskretes Problem der optimalen Steuerung" ( http://en.wikipedia.org/wiki/Optimal_control ) einstufen , aber ich denke nicht, dass dies Ihnen helfen wird.

Algorithmen

Wenn Sie die gesamte Warteschlange wirklich kennen, können Sie Baumsuchalgorithmen anwenden. Wie Sie sagten, wächst die Komplexität des Problems mit der Länge der Warteschlange sehr schnell. Ich schlage vor, einen Algorithmus wie "Depth-First Search (DFS)" zu verwenden, der nicht viel Speicher benötigt. Da die Punktzahl für Sie keine Rolle spielt, können Sie einfach aufhören, nachdem Sie die erste Lösung gefunden haben. Um zu entscheiden, welcher Unterzweig zuerst durchsucht werden soll, sollten Sie eine Heuristik für die Bestellung anwenden. Das heißt, Sie sollten eine Auswertungsfunktion schreiben (z. B. Anzahl leerer Felder; je ausgefeilter diese ist, desto besser), die eine Bewertung ergibt, um zu vergleichen, welcher nächste Schritt am vielversprechendsten ist.

Sie benötigen dann nur noch folgende Teile:

1. Modell des Spielstatus, das alle Informationen des Spiels speichert (z. B. Brettstatus / Karte, Warteschlange, Bewegungsnummer / Position in der Warteschlange)
2. Ein Bewegungsgenerator, der Ihnen alle gültigen Züge für einen bestimmten Spielstatus gibt
3. eine Funktion "Verschieben ausführen" und "Verschieben rückgängig machen"; die einen bestimmten (gültigen) Zug in einen Spielzustand anwenden / rückgängig machen. Während die Funktion "Verschieben" einige "Rückgängig-Informationen" für die Funktion "Rückgängig" speichern sollte. Das Kopieren und Ändern des Spielstatus in jeder Iteration verlangsamt die Suche erheblich! Versuchen Sie zumindest, den Status auf dem Stapel zu speichern (= lokale Variablen, keine dynamische Zuordnung mit "new").
4. eine Bewertungsfunktion, die für jeden Spielzustand eine vergleichbare Punktzahl ergibt
5. Suchfunktion

Hier ist eine unvollständige Referenzimplementierung für die Tiefensuche:

public class Item
{
    // TODO... represents queue items (FLOWER, SHOVEL, BUTTERFLY)
}

public class Field
{
    // TODO... represents field on the board (EMPTY or FLOWER)
}

public class Modification {
    int x, y;
    Field originalValue, newValue;

    public Modification(int x, int y, Field originalValue, newValue) {
        this.x = x;
        this.y = y;
        this.originalValue = originalValue;
        this.newValue = newValue;
    }

    public void Do(GameState state) {
        state.board[x,y] = newValue;
    }

    public void Undo(GameState state) {
        state.board[x,y] = originalValue;
    }
}

class Move : ICompareable {

    // score; from evaluation function
    public int score; 

    // List of modifications to do/undo to execute the move or to undo it
    Modification[] modifications;

    // Information for later knowing, what "control" action has been chosen
    public int x, y;   // target field chosen
    public int x2, y2; // secondary target field chosen (e.g. if moving a field)


    public Move(GameState state, Modification[] modifications, int score, int x, int y, int x2 = -1, int y2 = -1) {
        this.modifications = modifications;
        this.score = score;
        this.x = x;
        this.y = y;
        this.x2 = x2;
        this.y2 = y2;
    }

    public int CompareTo(Move other)
    {
        return other.score - this.score; // less than 0, if "this" precededs "other"...
    }

    public virtual void Do(GameState state)
    {
        foreach(Modification m in modifications) m.Do(state);
        state.queueindex++;
    }

    public virtual void Undo(GameState state)
    {
        --state.queueindex;
        for (int i = m.length - 1; i >= 0; --i) m.Undo(state); // undo modification in reversed order
    }
}

class GameState {
    public Item[] queue;
    public Field[][] board;
    public int queueindex;

    public GameState(Field[][] board, Item[] queue) {
        this.board = board;
        this.queue = queue;
        this.queueindex = 0;
    }

    private int Evaluate()
    {
        int value = 0;
        // TODO: Calculate some reasonable value for the game state...

        return value;
    }

    private List<Modification> SimulateAutomaticChanges(ref int score) {
        List<Modification> modifications = new List<Modification>();
        // TODO: estimate all "remove" flowers or recoler them according to game rules 
        // and store all changes into modifications...
        if (modifications.Count() > 0) {
            foreach(Modification modification in modifications) modification.Do(this);

            // Recursively call this function, for cases of chain reactions...
            List<Modification> moreModifications = SimulateAutomaticChanges();

            foreach(Modification modification in modifications) modification.Undo(this);

            // Add recursively generated moves...
            modifications.AddRange(moreModifications);
        } else {
            score = Evaluate();
        }

        return modifications;
    }

    // Helper function for move generator...
    private void MoveListAdd(List<Move> movelist, List<Modifications> modifications, int x, int y, int x2 = -1, int y2 = -1) {
        foreach(Modification modification in modifications) modification.Do(this);

        int score;
        List<Modification> autoChanges = SimulateAutomaticChanges(score);

        foreach(Modification modification in modifications) modification.Undo(this);

        modifications.AddRange(autoChanges);

        movelist.Add(new Move(this, modifications, score, x, y, x2, y2));
    }


    private List<Move> getValidMoves() {
        List<Move> movelist = new List<Move>();
        Item nextItem = queue[queueindex];
        const int MAX = board.length * board[0].length + 2;

        if (nextItem.ItemType == Item.SHOVEL)
        {

            for (int x = 0; x < board.length; ++x)
            {
                for (int y = 0; y < board[x].length; ++y)
                {
                    // TODO: Check if valid, else "continue;"

                    for (int x2 = 0; x2 < board.length; ++x2)
                    {
                        for(int y2 = 0; y2 < board[x].length; ++y2) {
                            List<Modifications> modifications = new List<Modifications>();

                            Item fromItem = board[x][y];
                            Item toItem = board[x2][y2];
                            modifications.Add(new Modification(x, y, fromItem, Item.NONE));
                            modifications.Add(new Modification(x2, y2, toItem, fromItem));

                            MoveListAdd(movelist, modifications, x, y, x2, y2);
                        }
                    }
                }
            }

        } else {

            for (int x = 0; x < board.length; ++x)
            {
                for (int y = 0; y < board[x].length; ++y)
                {
                    // TODO: check if nextItem may be applied here... if not "continue;"

                    List<Modifications> modifications = new List<Modifications>();
                    if (nextItem.ItemType == Item.FLOWER) {
                        // TODO: generate modifications for putting flower at x,y
                    } else {
                        // TODO: generate modifications for putting butterfly "nextItem" at x,y
                    }

                    MoveListAdd(movelist, modifications, x, y);
                }
            }
        }

        // Sort movelist...
        movelist.Sort();

        return movelist;
    }


    public List<Move> Search()
    {
        List<Move> validmoves = getValidMoves();

        foreach(Move move in validmoves) {
            move.Do(this);
            List<Move> solution = Search();
            if (solution != null)
            {
                solution.Prepend(move);
                return solution;
            }
            move.Undo(this);
        }

        // return "null" as no solution was found in this branch...
        // this will also happen if validmoves == empty (e.g. lost game)
        return null;
    }
}

Dieser Code funktioniert nicht und ist auch nicht kompilierbar oder vollständig. Aber es sollte Ihnen eine Idee geben, wie es geht. Die wichtigste Arbeit ist die Bewertungsfunktion. Je ausgefeilter es ist, desto falscher "versucht" der Algorithmus es später (und muss es rückgängig machen). Dies reduziert die Komplexität extrem.

Wenn dies zu langsam ist, können Sie auch versuchen, einige Methoden von Zwei-Personen-Spielen als HashTables anzuwenden. Dazu müssen Sie für jeden Spielstatus, den Sie auswerten, einen (iterativen) Hash-Schlüssel berechnen und Status markieren, die nicht zu einer Lösung führen. Beispielsweise muss jedes Mal, bevor die Search () -Methode "null" zurückgibt, ein HashTable-Eintrag erstellt werden. Wenn Sie Search () eingeben, prüfen Sie, ob dieser Status bereits ohne positives Ergebnis erreicht wurde, und geben Sie in diesem Fall "null" ohne zurück weitere Untersuchung. Dafür benötigen Sie eine riesige Hash-Tabelle und müssten "Hash-Kollisionen" akzeptieren, was dazu führen könnte, dass Sie wahrscheinlich keine vorhandene Lösung finden, was aber sehr unwahrscheinlich ist, wenn Ihre Hash-Funktionen gut genug sind und Ihre Tabelle groß genug (es besteht das Risiko eines kalkulierbaren Risikos).

Ich denke, es gibt keinen anderen Algorithmus, um dieses Problem (wie von Ihnen beschrieben) effizienter zu lösen, vorausgesetzt, Ihre Bewertungsfunktion ist optimal ...