Algorithme optimal de période 11

Vos questions / remarques sur le cube classique 3x3x3
Les méthodes principales du 3x3x3 et leurs variantes
Les visiteurs peuvent poster des messages dans cette partie
Alsamoshelan
Commence à se plaire ici
Messages : 48
Enregistré le : jeu. janv. 05, 2017 1:10 pm

Algorithme optimal de période 11

Message par Alsamoshelan »

Bonjour, ceci est un avis de recherche :smt023:

Je fais en ce moment une étude sur les périodes du 3^3, et notamment aux algorithmes de période minimale 11, qui sont de loin les plus durs à trouver.

Rappels rapides sur la période
On dit qu'un algorithme A est de période k si A^k (A répété k fois) équivaut à ne rien faire. La plus petite période de A est appelée sa "période minimale".
Exemple : le sexy move (RUR'U') a pour périodes 12, 36, 360 etc. et sa période minimale est 6. Il est facile de voir que toute période d'un algo est multiple de sa période minimale.

Ce que je recherche
Des algorithmes de période minimale 11, les plus courts possible (en métrique HTM).
Le mieux que j'ai trouvé (avec un programme de mon cru qui a bien galéré, et avec beaucoup de chance) est le suivant, de période minimale 11 et de longueur 10 :


D' L R' F U' R U' D F' L
(cliquez pour voir l'animation)

Je ne sais pas si on peut faire mieux. D'où cet avis de recherche. Si quelqu'un trouve un tel algorithme également de longueur 10 je suis aussi preneur. :smt023:

Fact important pour guider la recherche
Un algorithme de période minimale 11 est forcément un 11-cycles d'arêtes.

Voilà, je vous remercie pour votre aide. :smt023:

Avatar du membre
Paul Hochon
Inamovible
Messages : 395
Enregistré le : sam. nov. 07, 2015 7:35 pm
Localisation : Quelque part au Speedcubikstan

Re: Algorithme optimal de période 11

Message par Paul Hochon »

Erratum désolé
333 : 1/3/5/12/50/100 : 6.84 / 9.01 / 9.26 / 10.14 / 11.05 / 11.16
Square-1 : 1/3/5/12/50/100 : 5.45 / 7.56 / 8.48 / 9.60 / 10.75 / 11.37 - Vice champion de France 2017:
Clock : 8.06 / 9.03 / 9.45 / 10.51 / 11.04
YT - Profil WCA

Alsamoshelan
Commence à se plaire ici
Messages : 48
Enregistré le : jeu. janv. 05, 2017 1:10 pm

Re: Algorithme optimal de période 11

Message par Alsamoshelan »

Problème résolu.

J'avais également posé la question sur speedsolving.com et la réponse a l'air sans appel (et positive : 10 est bien la longueur optimale) :
There are none of length less than 10. There are 17,760 of length 10 (canonical sequences; commuting moves have a
prescribed order). There are 194,496 of length 11 (canonical sequences). There are 2,355,600 of length 12.

The numbers increase geometrically from there.
Modifié en dernier par Alsamoshelan le jeu. août 30, 2018 1:36 pm, modifié 1 fois.

Avatar du membre
fabien63
Bavard intarissable
Messages : 77
Enregistré le : ven. juil. 13, 2018 4:50 pm

Re: Algorithme optimal de période 11

Message par fabien63 »

Il est interressant de s'intéresser aux séquences périodiques.
C'est avec une séquence (de 3 mouvements) périodique de période 15 que je résout (de manière non optimale, et non rapide, mais systématique le 4x4x4. (la séquence à une période 5, sur un ensemble de 5 arrêtes, et une période de 3 sur 3 groupes de 2 facettes centrales) .
Ces séquences sont inintéressantes à connaitre.

Pourquoi un intérêt juste sur la période 11 ?
Modifié en dernier par fabien63 le jeu. août 30, 2018 4:05 pm, modifié 1 fois.

Alsamoshelan
Commence à se plaire ici
Messages : 48
Enregistré le : jeu. janv. 05, 2017 1:10 pm

Re: Algorithme optimal de période 11

Message par Alsamoshelan »

Et bien j'ai déjà trouvé des algos très probablement optimaux pour toutes les périodes minimales possibles (il y en a 73), mais les algos optimaux de période 11 sont de très loin les plus dures à trouver et je n'étais pas du tout certain que 10 était le meilleur.

Pour comparaison on peut générer toutes les autres périodes en 7 mouvements ou moins. Donc la période 11 et ses 10 mouvements optimaux font figure d'exception.

La période la plus chiante après 11 c'est la période 110 (tiens, multiple de 11...), on peut générer des algos de période 110 mais ils doivent faire au moins 7 mouvements, par exemple :


R2 B U R D' L U
(cliquez pour voir l'animation)

Alors qu'on peut générer la majorité des périodes optimales avec des algos entre 3 et 5 mouvements. De toute façon je mettrai dans un autre post mes résultats.

Avatar du membre
fabien63
Bavard intarissable
Messages : 77
Enregistré le : ven. juil. 13, 2018 4:50 pm

Re: Algorithme optimal de période 11

Message par fabien63 »

quelles méthodes as tu utilisés pour chercher et trouvé tes séquences de moindre mouvements pour chaque période ?

(théorie mathématique des groupes, recherche (à l'aide de programme informatique ) systématique en testant toutes les séquences de 3, puis4, puis5.... mvts ..., )

as tu un récapitulative de ton travail : séquence minimal,pour tel période ?
(cela ne sert peut être à rien pour résoudre vite un cube, mais est intéressant pour comprendre sa résolution)

Alsamoshelan
Commence à se plaire ici
Messages : 48
Enregistré le : jeu. janv. 05, 2017 1:10 pm

Re: Algorithme optimal de période 11

Message par Alsamoshelan »

Pour analyser les algorithmes j'ai utilisé la théorie des groupes, j'ai notamment identifié l'ensemble des algorithmes au groupe symétrique S_48 (car 48 stickers, les centres ne sont pas comptés). Pour calculer la période j'ai utilisé là aussi un résultat de la théorie des groupes symétriques : c'est le PPCM de l'ordre de chaque cycle.

Pour la génération, pour le moment c'est très primitif, j'ai juste généré aléatoirement des milliards d'algorithmes de longueur inférieure ou égale à 20 pour établir une liste des périodes minimales. J'en ai trouvé 73, la plus grande étant 1260. Je ne sais pas encore exactement comment prouver rigoureusement qu'il n'y en a pas d'autres, mais a priori c'est improbable que j'en aie loupé (en tout cas, j'ai déterminé que statistiquement, la probabilité qu'un algo ait une période minimale autre que ces 73 est inférieur à 1/10^9).
Mais j'ai des pistes pour creuser le sujet et prouver que j'en ai pas loupé. Il y a des propriétés simples sur les diviseurs et multiples des périodes à exploiter.

Donc pour le moment j'ai trouvé des représentants probablement optimaux pour chaque période minimal.

Maintenant je vais aller plus loin et tester de façon exaustive tous les algorithmes possibles de longueur inférieure ou égale à 7 (c'est de l'ordre de la dizaine de million, largement faisable pour mon programme) ainsi j'aurais la confirmation pour toutes les périodes sauf 11 (traité dans ce sujet).

J'ai également déterminé la fréquence statistique d'apparition de chaque période minimale (en gros, tu fais un algo, sur quelle période tu risque de tomber ?), les résultats sont stables.

Je compte aussi faire tout ça pour le 2x2 (ça sera évidemment beaucoup plus simple).

Bref, j'ai fais plein de trucs, je boucle tout ça et j'avais prévu de publier tout ça ici. :)

Avatar du membre
fabien63
Bavard intarissable
Messages : 77
Enregistré le : ven. juil. 13, 2018 4:50 pm

Re: Algorithme optimal de période 11

Message par fabien63 »

Merci pour les précisions.
Cela correspond au principe que j’imaginais.
cool si tu publies sur le forum le résultat.


Pour ton test exhaustif d’algorithmes de longueur au plus 7 mouvements, tu peux peut être diminuer le nombre de combinaisons à tester en tenant compte de la symétrie du cube.
Par exemple tu peux tester uniquement les combinaisons commençant par une des 9 séquences de 2 mouvements suivantes.
R U,
R U'
R U2
R L
R L'
R2 U
R2 U2
R2 L
R2 L2


As tu prévu d'identifier dans une séquence de période N, les cycles associés ?
exemple une séquence de période 12: avec un cycle de 3 arrêtes et un cycle de 4 coins
ou une séquence de période 12 : avec un cycle des 12 arêtes et de 3 coins etc...
Modifié en dernier par fabien63 le lun. sept. 03, 2018 10:44 am, modifié 1 fois.

Avatar du membre
fabien63
Bavard intarissable
Messages : 77
Enregistré le : ven. juil. 13, 2018 4:50 pm

Re: Algorithme optimal de période 11

Message par fabien63 »

pour info, au cas où :

http://trucsmaths.free.fr/rubik_ordre_elts.htm

(seules différences :
longueurs de séquences sont en QTM et non HTM)
notation française des mouvements

Alsamoshelan
Commence à se plaire ici
Messages : 48
Enregistré le : jeu. janv. 05, 2017 1:10 pm

Re: Algorithme optimal de période 11

Message par Alsamoshelan »

fabien63 a écrit :
ven. août 31, 2018 12:06 pm
Merci pour les précisions.
Cela correspond au principe que j’imaginais.
cool si tu publies sur le forum le résultat.


Pour ton test exhaustif d’algorithmes de longueur au plus 7 mouvements, tu peut peut être diminuer le nombre de combinaisons à tester en tenant compte de la symétrie du cube.
Par exemple tu peux tester uniquement les combinaisons commençant par une des 9 séquences de 2 mouvements suivantes.
R U,
R U'
R U2
R L
R L'
R2 U
R2 U2
R2 L
R2 L2


As tu prévu d'identifier dans une séquence de période N, les cycles associés ?
exemple une séquence de période 12: avec un cycle de 3 arrêtes et un cycle de 4 coins
ou une séquence de période 12 : avec un cycle des 12 arêtes et de 3 coins etc...
Pas bête du tout l'histoire des deux premiers mouvements. Je ne savais pas comment exploiter l'équivalence des algorthimes (il y a en tout 48 transformations différentes).
Oui je connaissais cette page, c'était la base de mon travail. :)
De toute façon j'ai fini de faire tous les algos jusqu'à 6 moves, prouvant ainsi l'optimum pour toutes les périodes (sauf 11 qu'on a traité ici à part).