Francocube

Bonjour à tous,

je m'intéresse à la mécanique des mélanges générés par le programme TNoodle qu'utilise la WCA.

On suppose deux choses dans un premier temps :
S1 : une face ne peut pas subire deux rotations successives (pas de L' L2 par exemple).
S2 : la suite de mouvement est aléatoire, avec S1 pour contrainte.

Déjà, on peut se poser la question (légitime) suivante : toutes les configurations sont-elles théoriquement atteignables avec ces mélanges ? On appelle (P1) cette proposition.

D'abord, il est connu que toutes les configurations sont atteignables en 20 mouvements ou moins.
Tous ces mélanges ont une longueur comprise entre 18 et 21 inclus (d'après ce que j'ai pu voir sur les mélanges officiels, j'ai testé sur une centaine de mélanges).
On appelle "plus petit algorithme" d'une configuration la plus petite suite de mouvements, à partir d'un cube résolu, qui entraîne cette configuration.
Donc en supposant S2, toutes les configurations dont le plus petit algorithme est de longueur comprise entre 18 et 20 inclus sont atteignables par ces mélanges. Donc (P1) est vraie pour celles-ci.

La question se pose pour celles dont le plus petit algorithme est de longueur inférieure ou égale à 17. Soit C une telle configuration et A son plus petit algorithme.
On remarque que U D U' D' est équivalent au mouvement nul.
Donc pour obtenir C en 18, 19, 20 ou 21 mouvements, il suffit d'ajouter à A un certain nombre de fois U D U' D' jusqu'à ce que le nombre de mouvements soit inclus dans [18; 21].

Par exemple : pour obtenir le résultat de R en un nombre de mouvements inclus dans [18; 21] et qui respecte S1, il suffit de faire R (U D U' D')5, ce qui fait 21 mouvements. Et on peut montrer que ça marche avec n'importe quel C. Cela fonctionne bien car il y a 4 nombres entre 18 et 21 et que mon algorithme neutre fait 4 mouvements.

Conclusion : (P1) est vrai, les mélanges générés par ce programme peuvent théoriquement atteindre toutes les configurations.

Oui, MAIS : en supposant S2, c'est-à-dire que les mouvements sont aléatoires. Le sont-ils réellement et y a-t-il des critères ? Pour la petite histoire, j'ai moi-même fait un programme en Python qui génère des mélanges respectant S1 et S2, ça ressemble plutôt bien à ceux de la WCA (mais évidemment cela ne veut absolument pas dire que ceux de la WCA respectent S2).

- Visiblement, aucun sur la croix, nous avons tous eu l'occasion de croiser (ah ah) une croix faisable en 2-3 mouvements.
- Aucun sur les blocs formés (pour les utilisateurs de méthodes basées sur les blocs).
- Aucun sur l'orientation des arêtes et des coins (pour les blinfolders et les utilisateurs de la méthode ZZ).

Ce qui fait néanmoins la puissance de cette absence de critères, ça serait précisément la neutralité. Aucun utilisateur n'est avantagé et aucun désavantagé.

Mais, même si théoriquement toutes les configurations sont atteignables par ce programme de la WCA, je doute fort qu'une configuration revenant au même qu'à faire un R soit imaginable.

On peut se poser la question du 21 mouvement : pourquoi y-t-il des mélanges de 21 mouvements alors que toutes les configurations sont atteignables en 20 mouvements ou moins ? Pourquoi 18 est le minimum ?

C'est peut-être simplement parce qu'il est plus facile de trouver un algorithme amenant à une configuration donnée en 21 mouvements qu'en 15 (en supposant que cela existe pour cette configuration).
Ou bien l'algorithme fait 18 mouvements aléatoires systématiquement et en rajoute 1, 2 ou 3 si le cube n'est pas considéré comme bien mélangé selon certains critères. Ce dont je doute : par exemple si en 18 mouvements on se retrouve avec une configuration revenant à faire un R, ce n'est pas rajouter 3 mouvements qui va empêcher un cubeur qui a l’œil de se rendre compte du truc.

J'aimerais donc en savoir plus sur la mécanique de ces mélanges, si des personnes s'y connaissent.

Comment le programme garantit-il que les cas triviaux sont évités ? Peut-être que des personnes motivées et qui savent coder en Java/Python pourraient aller fouiller dans leur algorithme ?

Merci beaucoup de vos éventuelles réponses.

Je comprends pas ton raisonement, il était peut être valable il y a 10 ans mais depuis les mélanges jusqu'au 444 sont généré sur une position aléatoire et non plus sur une séquence aléatoire.

je te renvoie vers le reglement WCA pour une grande partie de tes questions.

Par contre, il y a une 3e condition lors d'une génération de séquence aléatoire. si 2 mouvement consécutif sont sur le même axe, le 3e ne peut pas être sur le même axe. un U D U' D' est donc impossible.

Si je ne m'amuse c'est plutôt l'inverse, le scrambler définit d'abord une position aléatoire du cube, et ensuite la résout avec un logiciel du type Cube Explorer, et le mélange donné est l'inverse de la séquence qui résout la position. On obtient donc des algos en 18 à 21 mouvements, qui est donc un mélange presque optimal (presque parce que c'est proche de l'optimal mais il n'y a aucune garantie que ça le soit).
Pour le 2x2, le mélange est optimal. Pour les autres cubes (4-7), on fait un certain nombre de mouvements, exactement dans ton style. Pour le mega aussi ça marche pareil, pour le pyra j'imagine que c'est de l'optimal, pour le sq-1 j'imagine que c'est de l'optimal en gardant le CS puis on défait le CS avec un algo optimal de CSP, pour le skewb c'est optimal aussi, pour le clock je ne sais pas. Pour le FM il y a toujours R' U' F au début et à la fin (je n'ai jamais compris pourquoi).
Il faut aussi prendre en compte les restrictions WCA sur le nombre minimal de coups, mais ça c'est juste un bête test, il suffit de générer les positions atteignables en n mouvements et regarder si notre position est dedans.

Topic très intéressant j'espère qu'un délégué du type Philippe pourra préciser tout ça

Merci pour vos réponses très intéressantes.

Voilà ce que j'ai trouvé sur le règlement WCA :

Règlement WCA a écrit :une séquence de mélange officielle doit permettre d'atteindre une position aléatoire parmi celles nécessitant au moins 2 mouvements pour être résolues (chaque état est équiprobable)

Puisque chacun de ces états est équiprobable, cela signifie qu'un jour un cubeur pourrait tomber sur un mélange équivalent à U R par exemple. Je m'attendais franchement à des contraintes plus solides (ce n'est pas une critique : je respecte bien évidemment ce choix).

Cependant, le critère que tu cites Spols est très intéressant : cela veut dire que ma démonstration tombe à l'eau. On a donc 4 contraintes pour un 3x3x3 :

S1 : deux mouvements successives d'une même face est impossible.
S2 : deux mouvements effectués dans un même axe ne peut pas être suivi d'un mouvement dans le même axe.
S3 : toute position après mélange doit pouvoir être résolu en un minimum de 2 mouvements.
S4 : chaque position est équiprobable en tenant compte de S3.

Mais comment être alors sûr que tout mélange respectant S3 est faisable en 18, 19, 20 ou 21 mouvements en respectant S1 et S2 ? En imaginant que le programme choisisse une configuration qui soit faisable en 14 mouvements mais pas en 18...21 mouvements, alors le programme devrait théoriquement délivrer le mélange en-dehors de [18; 21] ?

ton [18,21] est empirique, je pense que le logiciel est programmé pour ne pas chercher plus profond en cas de mélange faisable en moins de mouvement. il se contente de ce qu'il a trouvé.

Pour le 444, je sais pas trop j'aurais dit comme Cubeur-Manchot mais le réglement WCA ne mentionne que le 5, 6, 7 et mega comme exception donc j'en déduis que les mélange sont généré à partir d'une position aléatoire et non une séquence.

Et pour info, le clock est le plus facile (et je pense historiquement le premier) pour un mélange de position aléatoire.
Chaque mouvement du clock peut être fait d'ans n'importe quel ordre sans influence sur le résultat donc il est facile de définir les mouvements amenant à une position définie. d'ailleur le mélange ressemeble fort à une résolution optimisé. (PS c'est le cas aussi du gear shift)

Cubeur-manchot a écrit : ↑ven. mars 24, 2017 7:17 pm Si je ne m'amuse

hihi

Un mélange en 13* STM s'est déjà vu dans les compètes, sans influence sur les temps effectués, c'est juste très rare.

Si tu regardes la répartition des mélanges (Par exemple le tableau de droite sur http://cube20.org) tu comprends assez vite pourquoi l'algo donne souvent une solution en 18~20 moves : Les 17* et 18* représentent environ 41*10^18 des 43*10^18 mélanges possibles, soit plus de 95%

Par contre l'algo donne pas forcément la solution optimale : au pyra y a eu un 3 moves + tips avec un mélange d'une longueur normale (dans les 7-8 moves + tips)

Voilà, c'est ce que j'allais dire.

Il faudrait savoir si cette configuration solvable en 13 mouvements dont tu parles a dû être mélangée en 13 mouvements (ce dont je doute) ou entre 18 et 21 (qui effectivement est empirique mais peut-être pas si faux que ça).

Car moi je me pose franchement une question : on est d'accord qu'il est plus aisé pour un logiciel de trouver une manière d'atteindre une configuration en 21 mouvements qu'en 18 mouvements (si cela existe pour une telle configuration).

Alors pourquoi certains mélanges font 18 mouvements ? C'est plus difficile que de trouver en 21...
Est-ce parce que certaines configurations atteignables en 18 mouvements ne le sont pas en 19, 20, ou 21 mouvements ?

Quand Cube Explorer te donne une solution, des fois elle est en 18, 21, 22, 19, ça dépend. S'il trouve directement une solution en 18 c'est simplement un coup de bol. Quand tu fais un FM et que tu trouves une solution en 33 dès le début, c'est que ta recherche a donné ça, mais évidemment c'est "moins dur" de trouver une solution en 47, tu en conviendras. C'est exactement pareil pour les mélanges, le solveur génère sa position, trouve une solution avec une méthode du type Kociemba, et rend l'inverse, et des fois il tombe sur 18, d'autres sur 21, etc. Pour être juste il faudrait regarder la répartition en profondeur, pas l'optimale mais celle obtenue avec la méthode utilisée par le solveur (qui n'est pas une résolution optimale).
Après dans l'algo il y a peut-être des choses du type "si la solution est en plus que 23, tu cherches si tu ne peux pas trouver mieux", qui fait descendre au pire à 22-23

Lucas Garron a fait une présentation très intéressante sur ça pendant des US Nationals:

https://youtu.be/i2yKyA8Xe4o

Je l'ai pas revue (je suis sur mobile) mais il me semble que tu peux y trouver pas mal de réponses

Edit: ce lien est de bien meilleure qualité: https://youtu.be/fMDxNgXzLwM

Voilà, Lucas a bien détaillé pourquoi l'approche décrite dans ce sujet (des mouvements aléatoires) n'est pas bonne et ne génère pas un état aléatoire.

Si la vidéo de Lucas n'est pas assez claire je peux sûrement faire un mini résumé en Français. En quelque mots : on tire une position aléatoire, on résout cet état, et l'inverse de la solution est la séquence génératrice du mélange.

Car moi je me pose franchement une question : on est d'accord qu'il est plus aisé pour un logiciel de trouver une manière d'atteindre une configuration en 21 mouvements qu'en 18 mouvements (si cela existe pour une telle configuration).

On est pas d'accord
Ça serait vrai si le programme faisait une recherche en profondeur de l'arbre, mais ce n'est pas entièrement le cas.
Arsonist a pointé cube20, il y a également sur le site la méthode de résolution que certains programmes (dont celui de la WCA) utilisent : la méthode "two-phase". J'avais fait un post explicatif ici.

La phase 1 est bien une exploration en profondeur mais la phase 2 c'est une simple consultation d'une grosse table.
La taille de ta solution dépend donc en fait de où atterrie ta première "phase" dans le sous groupe des positions orientées (noté H dans le lien pointé).
Ce que tu dis pourrais s'observer sur la phase 1 si on connaissait le découpage phase 1 / phase 2 dans le mélange (on peut en fait le trouver en regardant à quel moment on entre/sort de H) : genre 6 moves en phase 1 pour arriver dans une position de H résoluble en 12 c'est plus "dur" à trouver que 5 moves pour arriver dans une position de H résoluble en 14, puisqu'il y a eu une profondeur de plus parcourir.

Pour les autre questions/remarques du thread : oui le 4x4 c'est bien du random state, c'est pourquoi la génération de mélanges pour ce puzzle est aussi longue :p
Pour le 2x2 (et le pyra je crois), on retourne des solutions d'une longueur minimum de ~10 (j'ai plus le nombre exact en tête), pour "cacher" visuellement les solutions optimales trop courtes (ce qui implique que même si on a trouvé une solution optimale assez vite pour l'état choisi, on continue à en chercher une plus longue).

Alsamoshelan a écrit : ↑sam. mars 25, 2017 10:51 amIl faudrait savoir si cette configuration solvable en 13 mouvements dont tu parles a dû être mélangée en 13 mouvements (ce dont je doute) ou entre 18 et 21 (qui effectivement est empirique mais peut-être pas si faux que ça).

C'était un 13* qui était mélangé en 13, c'est pour ça qu'on (Enfin, que Phillou/Mr0.) l'a remarqué.