wiki.neuro.tu-berlin.de

FifteenPuzzle

Fifteen-Puzzle

Das 15-Puzzle, auch als Schiebepuzzle oder Schieberätsel bekannt, ist ein klassisches Rätselspiel. Es besteht aus einem 4x4-Rahmen mit 15 verschiebbaren, quadratischen Spielsteinen. Ein Feld bleibt immer leer, um die Bewegung der Steine zu ermöglichen.[1]

Spielregeln des 15-Puzzles:

Zielstellung
Abb. 2: Zielstellung
Zufällige Anfangsstellung
Abb. 1: Zufällige Anfangsstellung

Beim 15-Puzzle beginnt das Spiel mit einer zufälligen Anordnung der 15 Spielsteine innerhalb eines Rahmens, wobei ein Feld frei bleibt, um die Bewegung der Steine zu ermöglichen. Das Ziel des Spiels ist es, diese Steine in aufsteigender numerischer Reihenfolge von 1 bis 15 zu ordnen. Dabei soll die Anordnung mit der Zahl 1 in der oberen linken Ecke beginnen und mit der Zahl 15 in der unteren rechten Ecke enden, direkt neben dem leeren Feld.

Um die Steine zu bewegen, schieben die Spieler jeweils einen Stein, der direkt an das leere Feld angrenzt, in dieses Feld. Dies ermöglicht es, einen Stein nach dem anderen zu verschieben. Wichtig ist dabei, dass immer nur ein Stein gleichzeitig bewegt werden kann und dass nur die Steine beweglich sind, die unmittelbar neben dem leeren Feld liegen.

Lösbarkeit

Ein wichtiger Aspekt beim Lösen des 15-Puzzles ist die Erkenntnis, dass von den 15! möglichen Konfigurationen nur die Hälfte lösbar ist. Die Lösbarkeit eines Puzzles wird durch das Paritätskriterium bestimmt. In diesem Zusammenhang beschreibt Parität, ob die Anzahl der Vertauschungen, die notwendig sind, um die Kacheln von einer beliebigen Startkonfiguration in die Zielanordnung zu überführen, gerade oder ungerade ist. Eine Permutation der Kacheln im 15-Puzzle wird als lösbar eingestuft, wenn sie eine gerade Parität aufweist. Zusätzlich muss die Taxicab Distanz, also die Anzahl der horizontalen und vertikalen Bewegungen, die notwendig sind, um das leere Feld von seiner Position in der Anfangskonfiguration zur unteren rechten Ecke des Spielfelds zu bewegen, in die Gesamtparität einbezogen werden. Ein Puzzle ist demnach lösbar, wenn die Gesamtparität aus der Permutation der Kacheln und der Taxicab Distanz des leeren Feldes gerade ist.[2] [3]

komplexität

Das 15-Puzzle, stellt eine Herausforderung für Suchalgorithmen dar. Es wurde festgestellt, dass das Puzzle aus jeder Startposition in maximal 80 Zügen lösbar ist, wobei der durchschnittliche Lösungsweg etwa 52,6 Züge umfasst. Darüber hinaus ist das allgemeinere Problem, die minimale Anzahl von Zügen für die Lösung eines n x n-Puzzles zu finden, als NP-schwer
klassifiziert.[1:1]

Lösungsansätze

Im Bereich der heuristischen Suchalgorithmen sind der A*- und der IDA*-Algorithmus zwei führende Methoden für heuristische Suchvorgänge. Sie werden oft verwendet, um Lösungen für das Fünfzehn-Puzzle zu finden, ein Spiel, bei dem es darum geht, eine Anordnung von Zahlen in eine bestimmte Reihenfolge zu bringen. [4]

Der A*-Algorithmus ist besonders bekannt für seine Fähigkeit, den kürzesten Weg oder die geringste Anzahl von Zügen von einem Startzustand zu einem Zielzustand zu ermitteln. Ein Hauptnachteil des A*-Algorithmus ist jedoch sein hoher Speicherbedarf. Bei komplexen Puzzles, wo Milliarden von möglichen Zügen berücksichtigt werden müssen, speichert A* jeden einzelnen untersuchten Knoten (Zustand des Puzzles) im Speicher. Dies kann zu einem enormen Speicherverbrauch führen. [5]

Der IDA*-Algorithmus stellt eine Abwandlung des A*-Algorithmus dar, die sich für die Lösung des 15-Puzzle eignet und implementiert werden kann. Eine Eigenschaft von IDA* ist, dass es keine erweiterten Knoten im Speicher ablegt. Diese Vorgehensweise führt zu einem geringeren Speicherbedarf und ermöglicht es IDA*, Knoten schneller zu erweitern im Vergleich zum A*-Algorithmus.[6]

A* Anwendung auf 15-Puzzle

Beim Anwenden des A*-Algorithmus auf das 15-Puzzle werden spezifische Anpassungen für das Puzzle vorgenommen.
Dabei wird jeder Zustand des Puzzles als ein Knoten im Graphen betrachtet. Der A*-Algorithmus sucht den kürzesten Weg vom Startzustand zum Zielzustand.

A* verwendet eine Bewertungsfunktion f(n) = g(n) + h(n), wobei:

Der Algorithmus erweitert die Knoten mit den niedrigsten f(n)-Werten und führt dies fort, bis die Zielanordnung gefunden ist. A* ist effektiv in der Lösung von 15-Puzzle-Problemen, wenn eine geeignete Heuristik verwendet wird, die die Anzahl der verbleibenden Züge nicht überschätzt.[5:1]

bidirektionale A*-Algorithmus (BA*)

Der bidirektionale A*-Algorithmus, kurz BA*, ist eine Variante des klassischen A*-Suchalgorithmus. Bei BA* wird gleichzeitig von zwei entgegengesetzten Endpunkten - dem Start- und Zielzustand - gesucht, um einen Pfad zwischen ihnen zu finden. Dieser Ansatz kann effizienter sein, da die beiden Suchvorgänge sich treffen sollen und dadurch möglicherweise die Gesamtgröße des zu durchsuchenden Suchraums reduziert wird.

Pseudocode (angepasst)

Dieser Pseudocode ist aus dem Werk von Hasan, Dler O., et al.[7]

function BA* (StartState, GoalState)
    Initialise:
        IteratorF to control the loop  
        OpenListF to store the states to be traversed 
        ClosedListF to store already traversed states 
        OpenListB to store the states to be traversed 
        ClosedListB to store already traversed states
    if IteratorF = 0 then  
        set depth cost of StartState (g(s) in Equation (2)) to zero
        calculate HH value from StartState to GoalState. Equation (3)
        calculate evaluation function for StartState. Equation (2) 
        add StartState into OpenListF and ClosedListF
    while OpenListF is not empty do  
        CurrentStateF is state with lowest evaluation function value (Equation (2)) in OpenListF
        remove CurrentStateF from OpenListF  
        if CurrentStateF is GoalState then
        	reconstruct the solution path from StartState to CurrentStateF, and terminates the loop
        for each NeighboringStateF of CurrentStateF do
            if NeighboringStateF is not in ClosedListF then  
                depth cost of NeighboringStateF is equal to the depth cost of CurrentStateF plus one 
                calculate HH value from NeighboringStateF to GoalState. Equation (3)  
                calculate evaluation function for NeighboringStateF. Equation (2)  
                add NeighboringStateF into ClosedListF  
                add NeighboringStateF into OpenListF  
                if NeighboringStateF is in ClosedListB then
                    reconstruct the solution path from the two searches: from StartState 
                    to NeighboringStateF  
                    and from NeighboringStateF to GoalState, and terminates the loop
                increase IteratorF by 1  
        if IteratorF mod 15000 is equal to 0 after the first step of the cycle or IteratorF mod 75000
        is equal to 0 then  
             ->Expand in the backward direction, analogously

Erklärung

Initialisierung:

Start der Suche:

Suchprozess:

Bidirektionale Suche:

Spezielle Bedingungen:

HH Heuristik

Die HH-Heuristik im Pseudocode bezieht sich auf eine "Hybridized Heuristic" [7:1], die für den Bidirektionalen A*-Algorithmus verwendet wird. Diese Heuristik kombiniert drei verschiedene Heuristikmethoden: Manhattan-Distanz (MD), Lineare Konflikte (LC) und Walking-Distanz (WD). Das Ziel dieser Hybridisierung ist es, die Effizienz des Algorithmus zu verbessern, indem die Anzahl der generierten Zustände reduziert wird. Jede der Heuristiken hat ihre eigenen Stärken, und durch ihre Kombination wird eine umfassendere und genauere Schätzung der verbleibenden Distanz zum Zielzustand erreicht. Diese Kombination ermöglicht es dem Algorithmus, entweder optimale oder nahezu optimale Lösungen effizienter zu finden.[7:2]

Manhattan-Distanz (MD)

Die Manhattan-Distanz ist eine Heuristik, die häufig in Rätseln und Problemen der Wegfindung verwendet wird. Sie misst den Abstand zwischen zwei Punkten in einem Raster, wobei nur horizontale und vertikale Bewegungen erlaubt sind.[8]

Im Kontext des Fünfzehner-Puzzles wird die Manhattan-Distanz berechnet, indem für jede Kachel die Anzahl der Schritte gezählt wird, die benötigt werden, um sie von ihrer aktuellen Position in die Zielposition zu bewegen, ohne diagonale Bewegungen zu berücksichtigen. Für jede Kachel wird die Distanz in horizontaler und vertikaler Richtung einzeln berechnet und dann addiert. Die Summe dieser Distanzen über alle Kacheln gibt an, wie "weit entfernt" die aktuelle Konfiguration des Puzzles von der Zielkonfiguration ist.[7:3]

Linearer Konflikt (LC)

Der lineare Konflikt ist eine weitere Heuristik, die über die Manhattan-Distanz hinausgeht. Er tritt auf, wenn zwei Kacheln in derselben Reihe oder Spalte sind, um ihr Ziel zu erreichen, aber in der falschen Reihenfolge stehen und sich gegenseitig blockieren.

Zum Beispiel, wenn in einer Reihe die Kacheln 1 und 2 in der Zielkonfiguration nebeneinander stehen sollen, aber in der Reihenfolge 2-1 angeordnet sind, besteht ein linearer Konflikt. Um diesen Konflikt zu lösen, muss mindestens eine der Kacheln aus der Reihe bewegt werden, was zusätzliche Züge erfordert. Der lineare Konflikt addiert für jedes Paar von Kacheln, das in Konflikt steht, eine bestimmte Anzahl von Zügen zur Gesamtschätzung der Manhattan-Distanz hinzu, um eine realistischere Einschätzung der benötigten Züge zu geben.[7:4]

Walking Distance (WD)

Während die Manhattan-Distanz die Bewegungen jeder Kachel unabhängig betrachtet, berücksichtigt die Walking Distance die Tatsache, dass die Bewegung einer Kachel die Bewegung einer anderen beeinflussen kann.

Die Grundidee ist, dass, wenn eine Kachel bewegt wird, um sie näher an ihre Zielposition zu bringen, dies möglicherweise eine andere Kachel von ihrer Zielposition wegbewegt. Die Walking Distance versucht, diese gegenseitigen Abhängigkeiten in die Berechnung der Distanz einzubeziehen. Es ist eine komplexere Heuristik, die schwieriger zu berechnen ist, aber in vielen Fällen genauere Schätzungen über die Anzahl der benötigten Züge liefert.[7:5]

Resultate

Um die Wirksamkeit und Leistung des BA*-Algorithmus zu beurteilen, werden in diesem Abschnitt verschiedene Vergleiche angestellt. Zuerst vergleichen wir BA* mit HH in Bezug auf die Einhaltung der Anforderungen des ABC-Algorithmus (siehe Tabelle 1). Danach betrachten wir BA* im Vergleich zu UA* bezüglich der Richtungsorientierung, um zu demonstrieren, dass die bidirektionale Suche effektiver ist als die unidirektionale, besonders unter der Voraussetzung, dass sich die beiden Suchrichtungen nicht verfehlen (siehe Tabelle 2). Zum Schluss führen wir die BA*-Suche auf den 30 von 100 Korf-Instanzen durch und vergleichen sie mit der IDA*-Suche, ebenfalls im Kontext von HH[7:6] (siehe Tabelle 3).

Tabelle 1: Vergleich der BA*-Suche und der UA*-Suche für die 28 schwierigen Fünfzehn-Puzzle-Instanzen, die 80 Züge erfordern.

Tabelle 2: Vergleich der Ergebnisse zwischen BA*-Algorithmus und ABC-Algorithmus.

Tabelle 3: Vergleich des IDA*-Algorithmus mit MD und des LC- und BA*-Algorithmus mit HH für die 30 von 100 Korf-Instanzen. (in Anlehnung an Dler O., et al.[7:7])

Referenzen

Bildquellen

Abb. 1: Zufällige Anfangsstellung pdf
Abb. 2: Zielstellung pdf

Tabellenquellen

Tabelle 1: Vergleich der BA*-Suche und der UA*-Suche für die 28 schwierigen Fünfzehn-Puzzle-Instanzen, die 80 Züge pdf
Tabelle 2: Vergleich der Ergebnisse zwischen BA*-Algorithmus und ABC-Algorithmus.pdf
Tabelle 3: (modifiziert) Vergleich des IDA*-Algorithmus mit MD und des LC- und BA*-Algorithmus mit HH für die 30 von 100 Korf-Instanzen.pdf

Literaturverzeichnis

  1. https://de.wikipedia.org/wiki/15-Puzzle ↩︎ ↩︎

  2. Aaron F. Archer (1999) A Modern Treatment of the 15 Puzzle, The American Mathematical Monthly, 106:9, 793-799, URL ↩︎

  3. https://en.wikipedia.org/wiki/15_Puzzle#Mathematics ↩︎

  4. P. E. Hart, N. J. Nilsson and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," in IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, July 1968, URL ↩︎

  5. Culberson, Joseph, and Jonathan Schaeffer. "Efficiently searching the 15-puzzle." (1994). URL ↩︎ ↩︎

  6. Korf, R.E. Depth-first iterative-deepening: An optimal admissible tree search. Artif. Intell. 1985, 27, 97–109. URL ↩︎

  7. Hasan, D. O., Aladdin, A. M., Hardi, S. T., Tarik, A. R., & Mirjalili, S. (2023). The fifteen Puzzle—A new approach through hybridizing three heuristics methods. Computers, 12(1), 11. URL ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

  8. https://de.wikipedia.org/wiki/Manhattan-Metrik ↩︎