[PYTHON] Écrivez un programme pour résoudre le Rubik Cube 4x4x4! 3. Mise en œuvre

Quel est cet article?

Je suis actuellement en train de créer un robot qui résout le Rubik Cube 4x4x4 (Rubik Revenge) et vise un record du monde. Le plus gros obstacle dans la fabrication d'un robot était de mettre en œuvre un algorithme pour résoudre un cube 4x4x4 dans un temps réaliste et avec le moins d'étapes possible. Si vous le recherchez, vous constaterez qu'il existe peu de documents et d'ancêtres sur le 4x4x4. J'écris cet article en espérant que ce sera l'un de ces matériaux précieux. GitHub est ici ** Le contenu de cet article n'est pas complet. Il peut contenir certaines inefficacités. Je l'ajouterai au besoin s'il est amélioré à l'avenir. ** **

↓ Rubik Cube 4x4x4 pour la compétition et Rubik Cube 4x4x4 pour la compétition numéroté pour la production du programme

L'image entière

Cette collection d'articles se compose de trois articles au total.

1. Présentation
2. Algorithme
3. Mise en œuvre (cet article)

De quoi parler dans cet article

Dans cet article, je vais parler de la façon de mettre en œuvre réellement l'algorithme expliqué la dernière fois, et des CONSEILS à ce moment-là. Évitez de prendre des mesures pour expliquer l'implémentation car elle serait redondante. J'ai écrit une explication détaillée sur le Rubik Cube 2x2x2 dans l'article ici (le code actuel est également inclus), veuillez donc vous y référer également. ..

Indexage

En recherchant par petites phases, la zone à rechercher est devenue extrêmement petite. Grâce à cela, vous pourrez numéroter les états possibles de cette phase dans l'ordre. Cela élimine le besoin de travaux coûteux tels que ** simuler le mouvement du puzzle un par un **, et vous pouvez faire le travail équivalent à déplacer le puzzle simplement en vous référant au tableau. Cependant, si vous pensez à EP et CP ensemble, par exemple, cela ne rentrera pas dans le tableau d'environ 10 $ ^ 6-10 ^ 7 $ éléments, et cela consommera beaucoup de mémoire. Par conséquent, par exemple, il existe également une phase dans laquelle les numéros sont attribués uniquement à EP et CP, et l'état du puzzle est représenté par deux chiffres.

Vous pouvez les numéroter de n'importe quelle manière, mais pour plus de clarté, EP et CP sont des numéros de séquence de puzzle (multiplicateurs de plancher), EO et CO sont des nombres binaires et cubiques, respectivement, et les centres sont dupliqués. Je pense qu'il vaudrait mieux l'exprimer en base. Ici est facile à comprendre pour le nombre d'étages.

Recherche IDA *

Dans la recherche actuelle, je pense que vous utiliserez une recherche appelée IDA * search (Iterative Deepening A *). C'est une phrase qui est apparue à plusieurs reprises dans mon article, mais si je cite l'article ici,

En un mot, IDA * est «Répéter la recherche de priorité de profondeur (DFS) avec une profondeur maximale limitée tout en augmentant la profondeur». Le mécanisme d'IDA * est d'oublier le nœud une fois recherché. Si vous oubliez le nœud, vous pouvez libérer de la mémoire.

Dans IDA *, si une recherche de priorité de profondeur est effectuée jusqu'à une profondeur de $ N-1 $ et qu'aucune solution n'est trouvée, la profondeur maximale est augmentée à $ N $ et la recherche est relancée depuis le début. En faisant cela,

• Le résultat renvoyé est toujours le plus court
• Très faible utilisation de la mémoire

Il y a un avantage.

Cependant, pour les nœuds (états) peu profonds, la même recherche est répétée plusieurs fois, de sorte que la quantité de calcul augmente légèrement. Cependant, étant donné que l'état du puzzle augmente en tant que fonction exponentielle par rapport à la profondeur, l'augmentation de la quantité de calcul n'est pas si grande.

La clé de l'IDA * est d'estimer la «distance» entre l'état actuel et l'achèvement de la phase **. Cette «distance» est le nombre d'étapes à résoudre dans ce cas. Plus précisément, si l'état du puzzle est représenté par l'index $ i $,

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

Poursuivez la recherche pour que Laissez-moi vous expliquer en détail.

• $ profondeur $ est la limite supérieure de la profondeur (= nombre de pas) lors de la recherche.
• $ f (i) $ est une estimation du nombre de solutions nécessaires pour passer par l'état de l'index $ i $.
• $ g (i) $ est le nombre de pas effectués depuis l'état initial jusqu'à l'état d'index $ i $.
• $ h (i) $ est une estimation du nombre de pas effectués depuis l'état de l'index $ i $ jusqu'à l'état d'achèvement de phase.

Si vous augmentez $ depth $ de 0 à 1 tout en satisfaisant cette formule, vous trouverez une solution avec un petit effort. Si le nombre réel d'étapes nécessaires pour terminer la phase à partir de l'index $ i $ est $ h ^ \ star (i) $, et $ h (i) \ leq h ^ \ star (i) $ est toujours satisfait. Vous trouverez la solution optimale. Autrement dit, vous trouverez la solution avec le moins d'effort (dans cette phase). Cette affaire est dite recevable.

Évitez de rechercher le même état plus d'une fois

Il serait inefficace de rechercher le même état plusieurs fois. Cependant, si vous enregistrez l'état quelque part, cela consommera une énorme quantité de mémoire. Par conséquent, lors de la résolution du Rubik Cube, nous allons l'implémenter en évitant le cas où ** la procédure est optimisée et la procédure est la même **. Bien sûr, cela ne peut à lui seul éviter le cas où «j'ai traversé des étapes différentes mais la situation est la même». Cependant, on dit que cela seul n'a pas besoin de rechercher le même état avec une probabilité élevée (pour 3x3, ici Il est écrit en 6803 & item_no = 1 & page_id = 13 & block_id = 21).).

Dans le cas d'un cube rubic 4x4x4, il vaut mieux ne pas chercher dans les deux cas suivants.

• En tournant la même surface en continu
• Lorsque vous tournez le même axe, lorsque vous tournez dans l'ordre de la couche intérieure-> couche extérieure (ou couche extérieure-> couche intérieure: décidez laquelle utiliser en premier)

Une fonction qui renvoie une estimation du nombre d'étapes à effectuer

Il a dit que $ h (i) $ est important pour l'exploration de l'IDA *. Ici, je parlerai brièvement de la méthode de calcul de $ h (i) $ (bien que je la recherche moi-même).

Tout d'abord, calculez à l'avance le nombre d'étapes que chaque index prendra à partir de l'état terminé et créez une table. Dans mon cas, j'ai fait ce csv. Lorsque vous utilisez réellement cette valeur pré-calculée, il y a souvent plusieurs index (en supposant qu'il y a $ n $), donc il y a des valeurs $ n $ qui peuvent être récupérées à partir de la table pré-calculée. En utilisant ces «distances» $ n $, nous devons finalement afficher une distance qui représente la distance entre la carte et l'achèvement.

Je vais juste énumérer ce que j'ai essayé. Soit la distance de $ n $ $ L = (l_0, l_1, \ dots l_ {n-1}) $. Supposons également que $ \ mathrm {sd} (L) $ représente l'écart type de $ L $.

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} $ as $ Aussi, $ h (quand $ \ mathrm {sd} (L) = 0 $ i) = \ max (L) $

Le premier est garanti recevable, mais il a tendance à être coûteux en calcul car $ h (i) $ est souvent bien en dessous de $ h ^ \ star (i) $. Le second utilise la distance de Manhattan, mais il casse trop admissible. Dans un exemple simple, $ h ^ \ star (i) pour $ n $ éléments d'évaluation $ (l_0, l_1, \ points l_ {n-1}) $ qui sont alignés en tournant la même rotation R```. Même si = 1 $, il renvoie $ h (i) = n $. La rupture admissible augmente non seulement le nombre de solutions, mais augmente également l'espace de recherche, ce qui tend à augmenter la quantité de calcul. La troisième formule est basée sur l'hypothèse que si la variation de ** $ L $ est grande, $ h ^ \ star (i) $ a tendance à être grande **. Mais cela n'a pas très bien fonctionné. Le quatrième est la distance euclidienne. C'est mieux que le second, mais il y a toujours la possibilité de casser l'admissible. Le cinquième est la méthode actuellement utilisée. Ajustez les constantes $ a, b, c, d $ pour faire $ 0 <t <1 $. Ce $ t $ est utilisé pour diviser en interne la valeur maximale de $ L $ et la distance euclidienne. $ t $ est calculé avec la politique de renvoyer une valeur plus proche de la distance euclidienne lorsque $ \ mathrm {sd} (L) $ est supérieur à ** $ \ max (L) $ **. Cette fonction $ h (i) $ est appelée arbitrairement la fonction de Nyanyan.

Pseudo code

Il s'agit d'un pseudo-code semblable à Python de Programme écrit en Cython.

def phase_search(phase, indexes, depth, h_i): # phase:Phase, indexes:Index de l'état du puzzle, depth:Le nombre d'étapes qui peuvent être laissées, h_i:h à l'état d'index(indexes)
    global path
    if depth == 0: #S'il reste 0 pas, indiquez si la solution a été atteinte.
        return h_i == 0
    twist = successor[phase][0] #la torsion est une main à tourner
    while twist <= successor[phase][-1] : #le successeur est candidat à la rotation
        if skip(twist, path): #Ne tournez pas du même côté que vous avez tourné avec votre main précédente
            twist = skip_axis[phase][twist] #Avancez la torsion jusqu'à ce que vous ne puissiez pas tourner du même côté
            continue
        next_indexes = move(indexes, phase, twist) #Déplacez le puzzle par référence de tableau. Comme la définition des index diffère selon la phase, prenez la phase comme argument.
        next_h_i = h(indexes, phase) # h(i)rends le. h(i)Comme la définition est différente pour chaque phase, la phase est prise comme argument.
        if next_h_i > depth or next_h_i > h_i + 1: #Sautez si vous essayez manifestement de faire un détour
            twist = skip_axis[phase][twist]
        path.append(twist) #Ajoutez de la torsion aux étapes que vous avez franchies jusqu'à présent
        if phase_search(phase, next_indexes, depth - 1, next_h_i): #Rechercher le coup suivant par récursif
            return True #Solution trouvée
        path.pop() #Supprimez cette procédure de la procédure qui a été tournée jusqu'à présent
        twist = next_twist(twist, phase) #Prochaine étape
    return False #Aucune solution trouvée

def solver(puzzle): # puzzle:Objets de classe qui représentent tous les états du puzzle, etc.
    global path
    solution = [] #Solution
    for phase in range(6): #Tournez la phase avec pour
        indexes = initialize_indexes(puzzle, phase) #Convertir l'état du puzzle en index
        h_i = h(indexes, phase)
        for depth in range(60): #Tournez en profondeur. 60 est approprié
            path = [] #Chemin vide
            if phase_search(phase, indexes, depth, h_i): # IDA*Faites une recherche
                for twist in path: #Simulez le puzzle jusqu'à la fin de la phase
                    puzzle = puzzle.move(twist)
                solution.extend(path) #Ajouter la solution de la phase actuelle à la solution
                break #J'ai trouvé une solution, alors cassez-la et passez à la phase suivante
    return solution #Renvoyer la solution

Résumé

Jusqu'à présent, j'ai résumé ce que j'ai appris en écrivant un programme pour résoudre des cubes rubic 4x4x4 en trois articles. J'espère que cela sera utile à tout le monde.