Mélanger le Rubik's Cube

[link-link]

[math à 2h du mat']
je n'ai malheureusement pas compris le début de ton post, à cause d'un manque de vocabulaire, mais je peu aisément répondre à ta question.

en supposant que tu parles en qtm:
je te donne une piste en te demandant de compter le nombre de mouvements de tes pll J, T, N, V, F, R, Y puis ceux de tes pll A, Z, E, U, H (avec le ré-alignement pour chacune), puis de réfléchir sur quelle critère j'ai pu classer ces plls.
Puis pour quelqu'un d'aussi cultivé en mathématique que toi, ça ne devrais pas être trop dure de trouver la solution.
[/math à 2h du mat']

[WydD]

J'ai pas voulu répondre directement quand j'ai lu le post, mais effectivement y'a plusieurs points pas assez détaillés. Personnellement c'est directement sur le fond épistémologique du post qui me gène (moi aussi je sais sortir des gros mots).

Ok... donc le principe de question de base c'est de savoir combien de mouvements "au hasard" il faut pour avoir un cube "potentiellement bien" mélangé. Donc plusieurs points là. Ici le "au hasard" n'est pas formellement vrai : le mélange est, en général, en métrique HTM donc les demi-tours comptent comme un mouvement. De plus, les mouvements sont simplifiés, par exemple RLRU [4 moves] est en fait R2LU ou LR2U [3 moves]. Donc sans connaitre ça, ce dont je doute puisque apparemment il n'y a aucune connaissance du cube en pratique, il devient difficile d'aborder le problème.

Ensuite, et c'est là que ça devient bancal. On veut appliquer les principes des chaines de Markov pour répondre à la question. Oui ça reste envisageable. Pas de quoi sortir les grands mots pour ça, mais ok on construit la chaine, on itère et on tente de converger sur l'uniformité des états. Et là on annonce qu'au final on a pour le 2x2, 24 ou 25 tours (selon) permettent de bien mélanger le cube. Euh ouais... mais on a toujours pas défini ce que c'était : "bien" mélangé... Je suppose que c'est la distance de la distribution de algo de marche à N itérations par rapport à la distribution uniforme et dans ce cas il faut préciser plusieurs critères très importants : la norme utilisée, et évidemment quel est la distance acceptable, et pourquoi c'est acceptable ? Car supposons que l'on soit en norme infinie, et l'on considère que 5% c'est un bon écart par rapport à l'uniforme. Et pourquoi pas 10%, 1%, 0.01% ?
Conclusion : on n'a pas répondu à la question, on l'a éludé sans résoudre le vrai problème de fond : "Qu'est-ce que mélangé de façon acceptable veut dire".

Tu saura que pas mal des mélangeurs utilisés par la World Cube Association, dont celui du 3x3, utilisent des tirages uniformes (en général, on tire l'état et on le résout). Donc on sait que bien mélangé ça veut dire uniforme. Par contre on ne sait pas ce que veut dire "correctement mélangé" et c'est pour ça qu'on a recourt à des mélanges un peu arbitraires tels que 40 mouvements pour le 4x4, 60 pour le 5x5, 80 pour le 6x6 et 100 pour le 7x7.

De plus ~25 mouvements ça me parait vraiment beaucoup, quand on sait que le diamètre est de 11 pour le 2x2, ça me paraît un peu excessif intuitivement parlant.

Ensuite plusieurs détails qui me font mal aux yeux.

la moitié des configurations ne sont accessibles que par un nombre pair de tours à partir d'une configuration donnée

Es-tu sur de ça ? Même en restant en QTM (R2 = 2 moves), il existe des séquences qui font la PLL T en 15 moves et d'autres en 16. Donc la notion de parité de mouvements je vois pas où elle intervient, ou alors en tout cas pas sur l'ensemble des positions du cube. (Et en HTM j'en connais en 10, 13 et 14)

(par l'algorithme dit "de Dieu" - qu'on n'a pas encore trouvé puisque la preuve actuelle consiste bêtement à explorer toutes les possibilités possibles

Encore la sémantique : Défini ce que tu entends par "Algorithme de Dieu". L'algo de Dieu c'est l'algo qui termine UN cube de la façon la plus courte possible (on appelle ça plutôt l'optimal entre nous). Or, des gens ont développé de quoi calculer l'algo de Dieu pour toute position. Ainsi, ils ont fait même plus fort en trouvant le méta-algo de Dieu qui permet de trouver une instance de l'algo de Dieu pour un cube donné (et même si on explore l'arbre des possibilités, et sache que ce n'est pas bêtement que c'est fait, sinon ça prendrait des siècles) : pas besoin de chercher plus loin.

Et pour information : le superflip c'est UNE seule position parmis tant d'autres qui se trouve dans le faible nombres de cubes qui ont un optimal à 20HTM.

[rafoo]

Zut j'avais écrit un petit post gentil que j'ai oublié d'envoyer et maintenant WydD a dit tout ce que je voulais.

Je rajouterais juste dans les gros mots la notion d'antipode de l'état résolu (ça vient de la topologie métrique) qui a été assez à la mode à un moment (là j'ai la flemme de chercher les postes de cube lovers / domain of the cube qui en parlent).

Les points qui me semblent important dans les divers réponses que tu as reçu :

* On a les moyens de mélanger le 3×3×3 (et tous les puzzles brute-forceables comme le 2×2×2) en tirant un état de manière équiprobable et en générant une solution par ordinateur. En compète on ne s'en prive pas.

* Tes 24 ou 25 coups tu nous les balances sans aucune espèce de justification. T'as le droit de donner tes calculs, on t'en voudra pas.

* La limite de ta chaine de Markov n'a pas de raison d'être la distribution uniforme.



Là ou pour le coup t'as raison c'est la parité (d'ailleurs WydD, je demande à voir ta PLL T en 16 q sur le 2×2×2), sur un 2×2×2 comme sur un 3×3×3, la parité de la permutation des 8 coins change à chaque quart de tour donc en particulier toute identité se fait en un nombre pair de quarts de tour.

Cependant ça ne casse pas forcément les espoirs à base de convergence de chaines de Markof, c'est juste que X_{2n} et X_{2n+1} auront des limites différentes, c'est pas la fin du monde.

Le problème c'est que quand notre ami JNet le Caribou génère un mélange aléatoire, il ne se contente pas de sortir 25 coups au hasard, il s'arrange pour que le mélange ne soit pas trop débile en évitant les cas comme R R' ou R L R'. Il regarde les deux derniers coups et modifie les probas des transitions en conséquent. Ça nous fait un peu sortir du modèle de chaine de Markof mais ça ne m'étonnerait guère qu'on puisse mettre ce genre d'info dans les états en prenant par exemple <état du cube plus les deux derniers coups> (ce qui fait gentiment augmenter la taille de la matrice qui faisait déjà peur à Philfully ) mais là j'ai atteint les limites de mes connaissances de probas discrètes . Niveau mélangeur on peut même aller plus loin avec la notion de syllabe si on veut être encore plus malins (ça pourrait être bien pour les gros cubes par exemple)

Enfin fernique, nous ne sommes pas méchants et nous aimons bien aussi faire des maths en rapport avec le Rubik's Cube mais ton post manquait cruellement de précisions, ça fait pas très sérieux. Ton manque de connaissances sur le Rubik's Cube et tes envolées pseudo-scientifiques nous font un peu penser à ce post EPATHANT. N'hésite pas à t'inscrire sur le forum et à apprendre à résoudre le cube !

[Philfully]

[math à 2h du mat']
en supposant que tu parles en qtm:
je te donne une piste en te demandant de compter le nombre de mouvements de tes pll J, T, N, V, F, R, Y puis ceux de tes pll A, Z, E, U, H (avec le ré-alignement pour chacune), puis de réfléchir sur quelle critère j'ai pu classer ces plls.
[/math à 2h du mat']

PLL J : 16 mouvements
PLL A : 12 mouvements
PLL U : 12 mouvements
PLL T : 15 mouvements
PLL V : 19 mouvements
PLL Z : 17 mouvements

J'ai besoin d'aide car soit je compte mal, soit je n'utilise pas les mêmes algos.

De plus, il me faudrait considérer uniquement les PLL d'ordre 3. Or, parmi toutes celles citées, seule la A est d'ordre 3. Et elle se fait en 12 mouvements, donc on ne tombe pas sur un nombre impair de mouvements au total.

Je ne comprends pas bien le classement. Tu avais séparé en nombre pair et impair de mouvements ?

De toute façon, Rafoo a donné la réponse :

Là ou pour le coup t'as raison c'est la parité (d'ailleurs WydD, je demande à voir ta PLL T en 16 q sur le 2×2×2), sur un 2×2×2 comme sur un 3×3×3, la parité de la permutation des 8 coins change à chaque quart de tour donc en particulier toute identité se fait en un nombre pair de quarts de tour.

Donc mes espoirs (peu nourris) de voir une matrice apériodique en QTM tombent à l'eau.

Je repensais, mais c'est vrai que si à la place de QTM, on prend comme norme HTM, alors la matrice de transition est directement apériodique et là plus de souci.

Mais finalement, avec le recul de la nuit de sommeil, je suis d'accord avec les autres remarques : ça fait une belle jambe de savoir que la chaîne converge vers une loi uniforme. On en fait quoi ?

[WydD]

Pour la parité des mouvements, au temps pour moi, celle que je connaissais en 16 qtm a un alignement en plus, donc elle fait 17. Je découvre ça.

[deadalnix]

Es-tu sur de ça ? Même en restant en QTM (R2 = 2 moves), il existe des séquences qui font la PLL T en 15 moves et d'autres en 16. Donc la notion de parité de mouvements je vois pas où elle intervient, ou alors en tout cas pas sur l'ensemble des positions du cube. (Et en HTM j'en connais en 10, 13 et 14)

Tu es sur de ton coup la ?

[WydD]

Pour la parité des mouvements, au temps pour moi, celle que je connaissais en 16 qtm a un alignement en plus, donc elle fait 17. Je découvre ça.

Merci de me lire deadal...

[fernique]

@ deadalnix : pas la peine d'être si aggressif, j'essaie juste d'aider (donner les termes matheux pour répondre au post initial, qui demandait où chercher des infos, avec idée qu'il n'aura qu'à faire une recherche sur ces termes pour avoir plus de détails). Au passage, je m'étonne que qqn qui a "fait des maths" comme vous pose une question aussi classique que la convergence d'une chaine de Markov ergodique vers sa distribution stationnaire...

@Philfully : effectivement la chaine de Markov naive (un coup = un tour) n'est pas apériodique dans le cas du pocket cube car il n'y a pas de cycle impair. Ceci dit, on peut toujours "l'apériodiciser" (lazy chain) (d'où le 24 ou 25 coups pour le pocket cube - résultat obtenu en itérant la matrice de transition sur la distribution concentré en un seul cube - tout ça tient facilement sur un ordi standard pour le pocket cube, contrairement au vrai Rubik's cube -- je vois pas quels calculs on me demande : le programme ? la total variation à chaque itération ?). Pour le 3x3x3 c'est pareil (regarder la signature de la permutation des 8 coins : elle change à chaque tour).

@tous : je vois que le fait que je n'aie jamais résolu de cube (pire : je n'en ai jamais eu en mains !) vous choque...je ne vois pas pourquoi. Simplement, ça ne m'intéresse pas d'appliquer un algorithme, j'ai un ordinateur pour ça (bon, il faut aussi trouver les algos, certes...). Je trouvais la question du post initial bcp plus intéressante (c'est histoire de goût).

[fernique]

ça fait une belle jambe de savoir que la chaîne converge vers une loi uniforme. On en fait quoi ?

on cherche le temps de mélange de la chaîne (ou du moins une borne sup), c'est toute la question du post initial...

[fernique]

@rafoo : éviter les paires de tours R puis R' parait malin, mais ça fausse la distribution stationnaire...

[fernique]

Devant l'insistence de certains forumeurs je donne mes "calculs" (plus exactement les résultats). Je formalise pour plus me faire allumer.

Chaine de Markov : le pocket cube à l'étape t+1 est obtenu à partir du pocket cube à l'étape t en faisant :
- rien avec proba 1/7
- un des 6 quarts de tours possibles avec proba 1/7 chacun

Cette chaine est ergodique (l'apériodicité vient du self-loop "rien"). Je donne ci-dessous, pour chaque t, la "total variation" :

TV(t) := 1/2 sum_{x\in \Omega} |\mu_t(x)-unif(x)|

où :
-\Omega = espace des configs (de taille 7!3^6, ici)
-unif(x)=1/|\Omega|
-\mu_t=P^t*e, où e est un vecteur avec une entrée à 1 les autres à 0 (peu importe lequel : le cube "résolu" n'a rien de particulier à part son aspect plus esthétique) et P est la matrice de transition de la chaine de Markov ci-dessus.

On voit qu'on passe sous la barre des 1/2e=0,1839... à la 28eme étape (évidemment cette "barre" est arbitraire, mais c'est celle traditionnellement associée au "mixing time"). A la 28eme étape on n'a en général pas fait 28 tours puisque, une fois sur 7 en moyenne, on n'a rien fait, mais plutôt 28*6/7=24 tours (en moyenne).

Voici les résultats (qui à mon avis n'éclairent rien, mais bon). Le défi étant de faire la même chose pour le 3x3x3...soit de manière aussi stupide (par ex. en louant des ordis à google pour calculer, comme on fait ceux qui ont démontré que le diamètre du graphe du Rubik's cube était 20), soit en réfléchissant plus (comme ceux qui ont prouvé le temps de mélange du modèle d'Ising 2D, pour ceux à qui ça parle)

t TV(t)
0 1
1 0,999998
2 0,999991
3 0,999958
4 0,999813
5 0,999199
6 0,996758
7 0,98776
8 0,959909
9 0,926159
10 0,894313
11 0,852463
12 0,806401
13 0,758439
14 0,708066
15 0,657944
16 0,607977
17 0,559124
18 0,511804
19 0,466669
20 0,423961
21 0,38396
22 0,346738
23 0,312368
24 0,280761
25 0,251838
26 0,22549
27 0,201571
28 0,179935
29 0,160419
30 0,142859
31 0,12709
32 0,112956
33 0,100309
34 0,089014
35 0,078938
36 0,069964
37 0,061978
38 0,054879
39 0,048573
40 0,042978
41 0,038016
42 0,03362
43 0,029725
44 0,026276
45 0,023224
46 0,020524
47 0,018135
48 0,016024
49 0,014157
50 0,012507
51 0,011049
52 0,009761
53 0,008623
54 0,007618
55 0,006731
56 0,005946
57 0,005254
58 0,004643
59 0,004103
60 0,003626
61 0,003204
62 0,002832
63 0,002504
64 0,002214
65 0,001958
66 0,001731
67 0,001531
68 0,001355
69 0,001199
70 0,001061

limite en t infini : 1/(3^6*7!)=0,000000272...

[deadalnix]

@ deadalnix : pas la peine d'être si aggressif, j'essaie juste d'aider (donner les termes matheux pour répondre au post initial, qui demandait où chercher des infos, avec idée qu'il n'aura qu'à faire une recherche sur ces termes pour avoir plus de détails). Au passage, je m'étonne que qqn qui a "fait des maths" comme vous pose une question aussi classique que la convergence d'une chaine de Markov ergodique vers sa distribution stationnaire...

Non mais tu n'essayes pas d'aider, tu veux te faire mousser en sortant des grands mots tout en n'y connaissant visiblement pas grand chose. Tu ne croyais quand même pas que j'allais être sympa ?

Quand à la convergence, il faudrait encore démontrer qu'elle existe (le 222 en QTM, ça oscille), prouver qu'elle est unique, et que les différents cas sont équiprobables.

Tu essaye de nous aider ? Tu nous prends pour des clowns ? Franchement, qu'est ce qui te fait penser qu'avec tes 20 minutes réflexions sur un sujet que tu dis toi même ne pas connaitre, tu allais réellement nous apporter quelque chose ? Tu es mégalomane ou tu nous prends pour des andouilles ?

[fernique]

la convergence est acquise avec la chaîne "fainéante" (proba non-nulle de ne rien faire).

il manquait apparemment à celui qui a posté initialement le terme "mixing time", terme clé qui permet moult lectures profitables. Je ne sais pas si ça l'a aidé de sortir ce terme, mais ce n'est pas à vous de me le dire.

[fernique]

PS : je cite le premier message pour rappel

J'ai tenté de faire une Recherche [sur le mélange du cube], mais soit le sujet n'a pas été abordé ou bien, je n'ai pas assez de vocabulaire pour le trouver

[WydD]

OOOOOOOOH ! Stop !

@deadal, arrête d'enrager pour rien ! Il n'a pas été insultant, il a juste étudié un truc, certes à sa façon mais je vois pas où il nous prend pour des buses, il nous présente même sa méthode détaillée et ses résultats de manière numérique au final. Bref je vois pas de quoi le blâmer.
@fernique arrête de triple-quadruple post. Si tu veux corriger un post précédent, inscrit toi et tu pourras faire ça, mais c'est très mal vu de faire ça.


Sinon, sur le fond. C'est sympathique, je trouve la chaine un peu simple par rapport à la complexité du problème et je ne rentrerai pas dans le détail (chui au boulot là).
D'un point de vue méthode : la distance utilisée (ton TV) est une distance simple que je trouve pas adéquate. J'aurai plus vu un max_{x \in \Omega} \abs{\mu_t(x) - unif(x)} (norme infinie) qui montre bien que TOUTES les positions sont atteignables avec la même proba.