[PYTHON] Schreiben Sie ein Programm, um den 4x4x4 Rubik Cube zu lösen! 3. Implementierung

Was ist dieser Artikel?

Ich mache gerade einen Roboter, der 4x4x4 Rubik Cube (Rubik Revenge) löst und einen Weltrekord anstrebt. Die größte Hürde bei der Herstellung eines Roboters bestand darin, einen Algorithmus zu implementieren, um einen 4x4x4-Würfel in einer realistischen Zeit und mit so wenigen Schritten wie möglich zu lösen. Wenn Sie nachschlagen, werden Sie feststellen, dass es nur wenige Dokumente und Vorfahren zu 4x4x4 gibt. Ich schreibe diesen Artikel in der Hoffnung, dass er eines dieser wertvollen Materialien sein wird. GitHub ist hier ** Der Inhalt dieses Artikels ist nicht vollständig. Es kann einige Ineffizienzen enthalten. Ich werde es nach Bedarf hinzufügen, wenn es in Zukunft verbessert wird. ** **.

↓ 4x4x4 Rubik Cube für den Wettbewerb und 4x4x4 Rubik Cube für den Wettbewerb, nummeriert für die Programmproduktion

Das ganze Bild

Diese Artikelsammlung besteht aus insgesamt drei Artikeln.

1. Übersicht
2. Algorithmus
3. Implementierung (dieser Artikel)

Worüber in diesem Artikel gesprochen werden soll

In diesem Artikel werde ich darüber sprechen, wie der zuletzt erläuterte Algorithmus und die TIPPS zu diesem Zeitpunkt tatsächlich implementiert werden. Vermeiden Sie Schritte, um die Implementierung zu erklären, da sie redundant wäre. Ich habe im Artikel hier eine ausführliche Erklärung zum 2x2x2 Rubik Cube geschrieben (der eigentliche Code ist ebenfalls enthalten). Bitte beziehen Sie sich auch darauf. ..

Indizierung

Durch die Suche in kleinen Phasen ist der zu durchsuchende Bereich extrem klein geworden. Dank dessen können Sie die möglichen Zustände dieser Phase der Reihe nach nummerieren. Dadurch entfällt die Notwendigkeit kostspieliger Arbeiten wie ** Simulieren der Bewegung des Puzzles nacheinander **, und Sie können die Arbeit ausführen, die dem Bewegen des Puzzles entspricht, indem Sie sich nur auf das Array beziehen. Wenn Sie jedoch beispielsweise über EP und CP zusammen nachdenken, passt es nicht in das Array von etwa 10 ^ 6-10 ^ 7 $ Elementen und verbraucht sehr viel Speicher. Daher gibt es zum Beispiel auch eine Phase, in der Nummern nur EP und CP zugewiesen werden und der Status des Puzzles durch zwei Nummern dargestellt wird.

Sie können sie auf beliebige Weise nummerieren. Aus Gründen der Übersichtlichkeit sind EP und CP Puzzle-Sequenznummern (Bodenmultiplikatoren), EO und CO binäre bzw. kubische Zahlen und Zentren werden dupliziert. Ich denke, es wäre besser, es in Basis auszudrücken. Hier ist für die Anzahl der Stockwerke leicht zu verstehen.

IDA * Suche

Ich denke, Sie werden bei der eigentlichen Suche eine Suche namens IDA * -Suche (Iterative Deepening A *) verwenden. Dies ist ein Satz, der in meinem Artikel oft vorkommt, aber wenn ich aus dem Artikel [hier] zitiere (https://qiita.com/guicho271828/items/b3e885c5bde5bf7183c2),

In einem Wort lautet IDA * "Wiederholung der Tiefenprioritätssuche (DFS) mit begrenzter maximaler Tiefe bei zunehmender Tiefe". Der Mechanismus von IDA * besteht darin, den einmal durchsuchten Knoten zu vergessen. Wenn Sie den Knoten vergessen haben, können Sie Speicher freigeben.

Wenn in IDA * eine Suche mit Tiefenpriorität bis zu einer Tiefe von $ N-1 $ durchgeführt wird und keine Lösung gefunden wird, wird die maximale Tiefe auf $ N $ erhöht und die Suche von Anfang an neu gestartet. Auf diese Weise

• Das zurückgegebene Ergebnis ist immer das kürzeste
• Sehr geringe Speichernutzung

Es gibt einen Vorteil.

Bei flachen Knoten (Zuständen) wird dieselbe Suche jedoch viele Male wiederholt, sodass der Rechenaufwand geringfügig zunimmt. Da jedoch der Zustand des Puzzles als Exponentialfunktion in Bezug auf die Tiefe zunimmt, ist die Zunahme des Rechenaufwands nicht so groß.

Der Schlüssel zu IDA * besteht darin, ** die "Entfernung" vom aktuellen Zustand bis zum Abschluss der Phase zu schätzen **. Diese "Entfernung" ist die Anzahl der Schritte, die in diesem Fall gelöst werden müssen. Insbesondere wenn der Zustand des Puzzles durch den Index $ i $ dargestellt wird,

depth \geq f(i) = g(i) + h(i)

Fahren Sie mit der Suche fort, damit Lassen Sie mich im Detail erklären.

• $ depth $ ist die Obergrenze der Tiefe (= Anzahl der Schritte) bei der Suche.
• $ f (i) $ ist eine Schätzung, wie viele Lösungen benötigt werden, um den Status des Index $ i $ zu durchlaufen.
• $ g (i) $ ist die Anzahl der Schritte vom Ausgangszustand zum Zustand des Index $ i $.
• $ h (i) $ ist eine Schätzung der Anzahl der Schritte, die vom Status des Index $ i $ zum Status der Phasenabwicklung ausgeführt werden.

Wenn Sie $ depth $ von 0 auf 1 erhöhen, während Sie diese Formel erfüllen, finden Sie mit kurzem Aufwand eine Lösung. Wenn die tatsächliche Anzahl von Schritten, die erforderlich sind, um die Phase aus dem Index $ i $ abzuschließen, $ h ^ \ star (i) $ ist und $ h (i) \ leq h ^ \ star (i) $ immer erfüllt ist. Sie finden die optimale Lösung. Das heißt, die Lösung mit dem geringsten Aufwand (innerhalb dieser Phase) wird gefunden. Dieser Fall wird als zulässig bezeichnet.

Vermeiden Sie es, mehrmals nach demselben Status zu suchen

Es wäre ineffizient, mehrmals nach demselben Zustand zu suchen. Wenn Sie den Status jedoch irgendwo speichern, wird viel Speicherplatz benötigt. Wenn wir den Rubik Cube lösen, werden wir dies implementieren, indem wir den Fall vermeiden, dass ** die Prozedur optimiert ist und die Prozedur dieselbe ist **. Dies allein kann natürlich nicht den Fall vermeiden, dass "ich verschiedene Schritte durchlaufen habe, aber die Situation dieselbe ist". Es wird jedoch gesagt, dass dies allein nicht mit hoher Wahrscheinlichkeit nach demselben Status suchen muss (für 3x3, hier Es ist in 6803 & item_no = 1 & page_id = 13 & block_id = 21) geschrieben.).

Bei einem 4x4x4-Rubikwürfel ist es in den folgenden beiden Fällen besser, nicht zu suchen.

• Wenn Sie dieselbe Oberfläche kontinuierlich drehen
• Wenn Sie dieselbe Achse drehen, wenn Sie in der Reihenfolge der inneren Schicht-> äußeren Schicht (oder der äußeren Schicht-> inneren Schicht: Entscheiden Sie, welche zuerst verwendet werden soll) drehen.

Eine Funktion, die eine Schätzung der Anzahl der auszuführenden Schritte zurückgibt

Er sagte, dass $ h (i) $ für die IDA * -Erforschung wichtig ist. Hier werde ich kurz auf die Berechnungsmethode von $ h (i) $ eingehen (obwohl ich sie selbst erforsche).

Berechnen Sie zunächst vorab, wie viele Schritte jeder Index aus dem abgeschlossenen Zustand ausführen wird, und erstellen Sie eine Tabelle. In meinem Fall habe ich diese CSV gemacht. Wenn dieser vorberechnete Wert tatsächlich verwendet wird, gibt es häufig mehrere Indizes (vorausgesetzt, es gibt $ n $), sodass $ n $ -Werte aus der vorberechneten Tabelle abgerufen werden können. Unter Verwendung dieser $ n $ "Abstände" müssen wir schließlich einen Abstand ausgeben, der angibt, wie weit das Board von der Fertigstellung entfernt ist.

Ich werde nur auflisten, was ich versucht habe. Der Abstand von $ n $ sei $ L = (l_0, l_1, \ dots l_ {n-1}) $. Nehmen Sie außerdem an, dass $ \ mathrm {sd} (L) $ die Standardabweichung von $ L $ darstellt.

1. h(i)=\max(L)
2. h(i)=\sum L
3. h(i)=\max(L)+a\ \mathrm{sd}(L)
4. h(i)=\sqrt{\sum_j l_j^2}
5. $ t = \ mathrm {pow} \ left (a, - \ left (\ frac {\ max (L)} {b \ \ mathrm {sd} (L)} - c \ right) ^ d \ right) $ H (i) = (1-t) \ max (L) + t \ sqrt {\ sum_j l_j ^ 2} $ als $ Auch $ h (wenn $ \ mathrm {sd} (L) = 0 $ i) = \ max (L) $

Das erste ist garantiert zulässig, aber es ist in der Regel rechenintensiv, da $ h (i) $ oft weit unter $ h ^ \ star (i) $ liegt. Die zweite verwendet Manhattan Distanz, aber es bricht zulässig zu viel. In einem einfachen Beispiel $ h ^ \ star (i) für $ n $ Bewertungselemente $ (l_0, l_1, \ dots l_ {n-1}) $, die durch Drehen derselben Drehung `` `R``` ausgerichtet werden Obwohl = 1 $, wird $ h (i) = n $ zurückgegeben. Das zulässige Brechen erhöht nicht nur die Anzahl der Lösungen, sondern auch den Suchraum, wodurch sich der Rechenaufwand tendenziell erhöht. Die dritte Formel basiert auf der Hypothese, dass $ h ^ \ star (i) $ dazu neigt, zuzunehmen, wenn die Variation von ** $ L $ groß ist. Aber es hat nicht sehr gut funktioniert. Der vierte ist der euklidische Abstand. Es ist besser als das zweite, aber es besteht immer noch die Möglichkeit, das Zulässige zu brechen. Die fünfte ist die derzeit verwendete Methode. Passen Sie die Konstanten $ a, b, c, d $ an, um $ 0 <t <1 $ zu erhalten. Verwenden Sie dieses $ t $, um den Maximalwert von $ L $ und den euklidischen Abstand intern zu teilen. $ t $ wird mit der Richtlinie berechnet, einen Wert zurückzugeben, der näher an der euklidischen Entfernung liegt, wenn $ \ mathrm {sd} (L) $ größer als ** $ \ max (L) $ ** ist. Diese Funktion $ h (i) $ wird willkürlich als Nyanyan-Funktion bezeichnet.

Pseudocode

Dies ist ein Python-ähnlicher Pseudocode von Programm in Cython geschrieben.

def phase_search(phase, indexes, depth, h_i): # phase:Phase, indexes:Puzzle-Statusindex, depth:Die Anzahl der Schritte, die noch übrig sein können, h_i:h im Zustand der Indizes(indexes)
    global path
    if depth == 0: #Wenn noch 0 Schritte übrig sind, geben Sie zurück, ob die Lösung erreicht wurde.
        return h_i == 0
    twist = successor[phase][0] #Twist ist eine Hand zum Drehen
    while twist <= successor[phase][-1] : #Nachfolger ist ein Kandidat für die Rotation
        if skip(twist, path): #Drehen Sie nicht dieselbe Seite, die Sie mit Ihrer vorherigen Hand gedreht haben
            twist = skip_axis[phase][twist] #Drehen Sie vor, bis Sie nicht mehr dieselbe Seite drehen können
            continue
        next_indexes = move(indexes, phase, twist) #Bewegen Sie das Puzzle nach Array-Referenz. Da die Definition von Indizes je nach Phase unterschiedlich ist, nehmen Sie die Phase als Argument.
        next_h_i = h(indexes, phase) # h(i)Gib es zurück. h(i)Da die Definition für jede Phase unterschiedlich ist, wird die Phase als Argument verwendet.
        if next_h_i > depth or next_h_i > h_i + 1: #Überspringen Sie, wenn Sie offensichtlich versuchen, einen Umweg zu machen
            twist = skip_axis[phase][twist]
        path.append(twist) #Fügen Sie den Schritten, die Sie bisher unternommen haben, eine Wendung hinzu
        if phase_search(phase, next_indexes, depth - 1, next_h_i): #Suchen Sie nach dem nächsten Zug durch rekursive
            return True #Lösung gefunden
        path.pop() #Entfernen Sie diese Prozedur aus der Prozedur, die bisher gedreht wurde
        twist = next_twist(twist, phase) #Nächster Zug
    return False #Keine Lösung gefunden

def solver(puzzle): # puzzle:Klassenobjekte, die alle Zustände des Puzzles usw. darstellen.
    global path
    solution = [] #Lösung
    for phase in range(6): #Drehen Sie die Phase mit für
        indexes = initialize_indexes(puzzle, phase) #Konvertieren Sie den Puzzle-Status in einen Index
        h_i = h(indexes, phase)
        for depth in range(60): #Tiefe drehen. 60 ist angemessen
            path = [] #Leerer Weg
            if phase_search(phase, indexes, depth, h_i): # IDA*Mach eine Suche
                for twist in path: #Simulieren Sie das Puzzle bis zum Ende der Phase
                    puzzle = puzzle.move(twist)
                solution.extend(path) #Fügen Sie der Lösung die Lösung der aktuellen Phase hinzu
                break #Ich habe eine Lösung gefunden, also brechen Sie sie und fahren Sie mit der nächsten Phase fort
    return solution #Geben Sie die Lösung zurück

Zusammenfassung

Bisher habe ich in drei Artikeln zusammengefasst, was ich beim Schreiben eines Programms zum Lösen von 4x4x4-Rubinwürfeln gelernt habe. Ich hoffe, es wird für alle hilfreich sein.