TIPE sur le Rubik's cube

Si VRAIMENT aucun des autres forums ne vous inspire pour poster votre question ...
raphael
Passe sa journée ici. Et dort ici, aussi
Messages : 650
Enregistré le : lun. juin 14, 2010 6:26 pm
Localisation : 77
Contact :

Re: TIPE sur le Rubik's cube

Message par raphael »

Il faut regarder si ta métrique est robuste à une rotation globale du cube (le 2x2x2 j'entends).

Est-ce que tu prends en compte le fait qu'un bloc soit dans la bonne position, mais orienté différemment ?
Qu'est-ce que tu entends par métrique robuste ? Sinon oui je prends en compte ce fait, le 2x2x2 est donné par deux listes de 8 chiffres, les 8 premiers pour la position de chaque pièce, les 8 derniers pour l'orientation. C'est vrai que cette notation est embêtante si je veux atteindre toutes les positions du 2x2x2 puisqu'en faisant varier les éléments de la liste de 0 à 2 ou de 0 à 7 j'obtiens largement plus que le cardinal de l'ensemble des positions du cube.

Pour régler ça, il me semble qu'en se restreignant à 3 mouvements seulement on fixe une pièce, ce qui réalise ce dont Rafoo disait. Par exemple j'ai pris les mouvements R,F,D ce qui me fixe la pièce LUB. Mais on a toujours trop de positions atteintes par rapport au cardinal.
Bannière atoutcubes.com
Avatar du membre
bongo
Passe sa journée ici. Et dort ici, aussi
Messages : 507
Enregistré le : dim. déc. 11, 2016 6:56 pm

Re: TIPE sur le Rubik's cube

Message par bongo »

raphael a écrit :
Il faut regarder si ta métrique est robuste à une rotation globale du cube (le 2x2x2 j'entends).

Est-ce que tu prends en compte le fait qu'un bloc soit dans la bonne position, mais orienté différemment ?
Qu'est-ce que tu entends par métrique robuste ?
Prenons un exemple simple : le cube non mélangé.
Normalement la distance que tu prends (la distance est définie par une métrique (norme) dans un espace vectoriel normé) doit te donner 0.

Maintenant si tu fais une rotation globale du cube, quelle est la distance que ton algo donne ? Si c'est 0 quelque soit la rotation globale, alors elle est robuste au sens de la rotation globale.
Sinon... et bien cette métrique est problématique.
(1/3/5/12/50/100)
3^3 CFOP GTS 2M : 12.71 - 16.43 - 17.19 - 18.49 - 19.33 - 19.63
4^3 Yau Wuque: 1'16 - 1'25 - 1'26 - 1'30 - 1'36 - 1'39
5^3 Wushuang : 3'35 - 3'56 - 4'01 - 4'10 - 4'27 - 4'44
6^3 Red Unicorn: 7'04 - 7'45 - 7'54 - 8'05 - 8'28 - 8'56
rafoo
VIP au club des 1000
Messages : 2861
Enregistré le : jeu. avr. 09, 2009 11:57 am
Localisation : Paris
Contact :

Re: TIPE sur le Rubik's cube

Message par rafoo »

raphael a écrit :Mais on a toujours trop de positions atteintes par rapport au cardinal.
Ce n'est pas très grave mais il y a moyen de l'éviter. La meilleure source que je connais sur le sujet c'est http://kociemba.org/math/coordlevel.htm.

Pour le 2x2x2 : tu peux obtenir une représentation qui ne compte que les configurations effectivement atteignables depuis le cube résolu en stockant une permutation des 7 pièces mobiles d'une part et l'orientation de 6 des 7 pièces mobiles d'autre part (puisque l'orientation de la dernière est fixée par l'orientation des 6 premières).

Pour le 3x3x3 : même si la représentation donnée par Kociemba est très économique, il remarque bien qu'elle permet encore de représenter deux fois trop de cubes :
Only half of these cubes are really possible to generate because all achievable permutations are even and so we have only 12! * 8! /2 permutations (ignoring the orientations).
"Singmaster has heard of solutions in 2 minutes, but I find this difficult to believe."
raphael
Passe sa journée ici. Et dort ici, aussi
Messages : 650
Enregistré le : lun. juin 14, 2010 6:26 pm
Localisation : 77
Contact :

Re: TIPE sur le Rubik's cube

Message par raphael »

Hello,

Je n'ai qu'un un peu avancé depuis la dernière fois malgré pas mal de travail. J'ai réussi à implémenter l'algo qui remplit la matrice de transition, le soucis était qu'au début ça devait prendre environ 50 jours pour la générer. Après quelques optimisations, j'ai estimé le temps d'exécution à environ 20h, j'ai donc lancé l'algo. Après une journée d'exécution j'ai eu un magnifique "Memory error" ! Du coup je vois pas trop comment m'en sortir de ce côté là, sachant qu'en plus même si je parvenais à créer la matrice, il faudrait ensuite la mettre à la puissance au moins 30. Et comme elle doit tendre vers une matrice dont tous les coefficients sont égaux, elle est de moins en moins creuse ce qui augmente le nombre d'opérations. Je pensais donc réutiliser les résultats donnés par Fernique (post que j'ai cité plus haut), pour pouvoir avancer. C'est beaucoup moins gratifiant mais l'année avance et j'ai plus énormément de temps.

Pour la suite, je voudrais comparer cette étude théorique avec une étude pratique. Comme je l'ai déjà expliqué j'assigne à un mélange donné un indice de mélange, plus celui-ci est grand mieux le cube est mélangé. Je regarde l'orientation et la position de chaque pièce par rapport au cube résolu, et si une pièce est mal orientée ou positionnée j'augmente l'indice. J'ai aussi un algo qui compte le nombre de bloc 1x1x2 sur le 2x2x2, à chaque nouveau bloc, je réduis l'indice du mélange. Si le repérage des blocs me semble pertinent, celui de la position ou orientation d'une pièce par rapport au cube résolu me semble l'être moins. Je voudrais donc savoir si vous auriez des idées sur d'autres tests que je pourrais effectuer pour estimer la difficulté d'un mélange. Si vous avez d'autres suggestions, n'hésitez pas ;)
rafoo
VIP au club des 1000
Messages : 2861
Enregistré le : jeu. avr. 09, 2009 11:57 am
Localisation : Paris
Contact :

Re: TIPE sur le Rubik's cube

Message par rafoo »

Salut,

Par rapport à tes soucis de mémoire et de temps de calcul, tu parles du 3x3x3 ou du 2x2x2 ?

Sur le 3x3x3 c'est illusoire d'espérer stocker la matrice complète (a fortiori ces puissances) mais tu peux découper le problème entre les coins d'un côté et les arêtes de l'autre puis entre permutation et orientation. Ça peut te permettre de réduire les dimensions à quelque chose de manipulable, la plus grosse c'est la permutation des arêtes (12!).

Sur le 2x2x2 c'est beaucoup plus petit mais tu peux quand même séparer permutation et orientation. De plus ça m'étonnerait que tu doives calculer les puissances jusqu'à 30 pour le 2x2x2.

Si c'est encore trop gros, je te conseille de changer d'approche et de ne pas stocker la matrice de transition. Quelques pistes pour évaluer ton indice et répondre à la question de base de ton TIPE :
1) Évaluer ton indice sur des cubes dont on connait la distance. Pour les petites distances (disons jusqu'à 9), tu peux les lister par un parcours en largeur. Pour avoir des cubes à distance 20, tu peux aller voir ici : http://cube20.org/distance20s/
2) Évaluer ton indice sur des cubes tirés alétoirement suivant un tirage uniforme. Est-ce-que ton indice distingue les cubes à petite distance des cubes aléatoires ? Si oui passer au point 3, sinon il faut sans doute améliorer l'indice. Est-ce-qu'il distingue les cubes aléatoires des cubes à distance 20 ?
3) Évaluer ton indice sur des cubes mélangés en N coups (en faisant varier N).

Sinon, ton idée de recherche de blocs me fait penser à la fitness function de l'algorithme génétique de Cyril (https://www.francocube.com/cyril/genetic_alg). Regarder le nombre de coups pour remettre chaque pièce à sa place me fait penser au pruning de Kociemba (http://kociemba.org/math/pruning.htm).
"Singmaster has heard of solutions in 2 minutes, but I find this difficult to believe."
raphael
Passe sa journée ici. Et dort ici, aussi
Messages : 650
Enregistré le : lun. juin 14, 2010 6:26 pm
Localisation : 77
Contact :

Re: TIPE sur le Rubik's cube

Message par raphael »

rafoo a écrit :Par rapport à tes soucis de mémoire et de temps de calcul, tu parles du 3x3x3 ou du 2x2x2 ?

Sur le 3x3x3 c'est illusoire d'espérer stocker la matrice complète (a fortiori ces puissances) mais tu peux découper le problème entre les coins d'un côté et les arêtes de l'autre puis entre permutation et orientation. Ça peut te permettre de réduire les dimensions à quelque chose de manipulable, la plus grosse c'est la permutation des arêtes (12!).

Sur le 2x2x2 c'est beaucoup plus petit mais tu peux quand même séparer permutation et orientation. De plus ça m'étonnerait que tu doives calculer les puissances jusqu'à 30 pour le 2x2x2.
Je parle du 2x2x2, une puissance donnée de la matrice correspond au nombre de coups effectués dans le mélange, donc pour s'approcher suffisamment près de l'uniformité, 30 coups ça me semble pas trop. Après l'analyse du résultat peut révéler qu'un nombre inférieur de coup suffit.
rafoo a écrit :Pour les petites distances (disons jusqu'à 9), tu peux les lister par un parcours en largeur
Je vois pas vraiment comment tu penses les lister, si je génère toutes les combinaisons de 9 mouvements, je sais qu'on peut résoudre tous ces mélanges en 9 coups ou moins. Mais je peux pas savoir si c'est 9 coups exactement, ou moins ; tu me conseilles en fait de simplement générer des mélanges dont la distance est au maximum de 9 et de les considérer comme des "petites distances", c'est ça ?


Pour l'indice de mélange, pour l'instant c'est assez basique ce que je fais, et j'ai peu étudié les résultats, mais je vais regarder ça de plus près avec tes conseils ;) Merci !
rafoo
VIP au club des 1000
Messages : 2861
Enregistré le : jeu. avr. 09, 2009 11:57 am
Localisation : Paris
Contact :

Re: TIPE sur le Rubik's cube

Message par rafoo »

raphael a écrit : jeu. févr. 16, 2017 9:58 am Je parle du 2x2x2, une puissance donnée de la matrice correspond au nombre de coups effectués dans le mélange, donc pour s'approcher suffisamment près de l'uniformité, 30 coups ça me semble pas trop. Après l'analyse du résultat peut révéler qu'un nombre inférieur de coup suffit.
Je pense que 30 coups pour un 2x2x2, c'est vraiment excessif. Pour un 3x3x3 ça me paraît raisonnable.

Tu sépares permutation et orientation ? Si tu veux vraiment garder la matrice de transition en mémoire, tu peux encore simplifier le problème en n'autorisant que les demi-tours (ce qui réduit drastiquement le nombre de configurations atteignables) ou en prenant un puzzle plus simple comme le 3x3x1 voire le 2x2x1.
raphael a écrit : jeu. févr. 16, 2017 9:58 am
rafoo a écrit :Pour les petites distances (disons jusqu'à 9), tu peux les lister par un parcours en largeur
Je vois pas vraiment comment tu penses les lister, si je génère toutes les combinaisons de 9 mouvements, je sais qu'on peut résoudre tous ces mélanges en 9 coups ou moins. Mais je peux pas savoir si c'est 9 coups exactement, ou moins ; tu me conseilles en fait de simplement générer des mélanges dont la distance est au maximum de 9 et de les considérer comme des "petites distances", c'est ça ?
Je parle de ça : https://fr.wikipedia.org/wiki/Algorithm ... en_largeur
L'algo est le suivant :

Code : Tout sélectionner

Parcours_largeur (dist_max):
    R[0] = {cube_résolu}
    pour d allant de 0 à dist_max - 1:
        R[d+1] = {}
        pour c dans R[d]:
            pour c' voisin de c:
                si c' n'est ni dans R[d] ni dans R[d-1] alors insérer c' dans R[d+1]
    renvoyer R
À la sortie, R est un tableau tel que pour chaque d entre 0 et dist_max, R[d] est l'ensemble des cubes à distance exactement d.
Ça suppose de savoir calculer les voisins d'un cube donné. En utilisant des dictionnaires plutôt que des ensembles, tu peux aussi enregistrer de l'information sur chaque cube (par exemple une solution optimale ou la valeur de ton indice). Il y a des optimisations possibles si tu as encore des soucis de temps ou de mémoire (pour éviter des tests quand on sait d'avance que le cube c' qu'on regarde est à distance d ou d-1).
"Singmaster has heard of solutions in 2 minutes, but I find this difficult to believe."
raphael
Passe sa journée ici. Et dort ici, aussi
Messages : 650
Enregistré le : lun. juin 14, 2010 6:26 pm
Localisation : 77
Contact :

Re: TIPE sur le Rubik's cube

Message par raphael »

A en croire ce post, il faut environ 24 coups en QTM pour mélanger, donc c'est pour ça que je parle de 30 coups. Mon but était de refaire cette étude en HTM, puis de comparer ce résultat théorique avec l'expérience pour mieux comprendre la notion de bien mélangé pour un 2x2x2. C'est pour cela que j'essaye de rester focalisé sur le 2x2x2.

rafoo a écrit :Je parle de ça : https://fr.wikipedia.org/wiki/Algorithm ... en_largeur

D'accord, je connaissais pas le parcours en largeur. J'ai déjà une fonction qui donne les voisins d'un état donné donc je vais pouvoir mettre ça en place.
rafoo a écrit :Pour avoir des cubes à distance 20, tu peux aller voir ici : http://cube20.org/distance20s/
Par ailleurs aurais-tu un équivalent pour le 2x2x2 ?
Avatar du membre
Cubeur-manchot
VIP au club des 1000
Messages : 2999
Enregistré le : jeu. sept. 11, 2014 5:16 pm
Localisation : Bures-sur-Yvette (91)
Contact :

Re: TIPE sur le Rubik's cube

Message par Cubeur-manchot »

raphael a écrit : jeu. févr. 16, 2017 4:56 pmA en croire ce post, il faut environ 24 coups en QTM pour mélanger, donc c'est pour ça que je parle de 30 coups. Mon but était de refaire cette étude en HTM, puis de comparer ce résultat théorique avec l'expérience pour mieux comprendre la notion de bien mélangé pour un 2x2x2. C'est pour cela que j'essaye de rester focalisé sur le 2x2x2.
Le 24 ou 25 n'ayant pas été démontré proprement, je te conseille de refaire l'étude toi-même. Je pense aussi que pour le 2x2, sachant que le god's number en HTM est de 11, avec un petit 16 ou 17 HTM de mélange aléatoire on doit déjà être vraiment pas mal niveau homogénéïté :oui:
raphael a écrit : jeu. févr. 16, 2017 4:56 pm
rafoo a écrit :Pour avoir des cubes à distance 20, tu peux aller voir ici : http://cube20.org/distance20s/
Par ailleurs aurais-tu un équivalent pour le 2x2x2 ?
Quand tu auras ta liste avec le parcours en largeur, ça te sera donné automatiquement, pour la ligne d=11 :)
Sinon ça peut se regénérer assez facilement :
Il suffit de générer bêtement les cubes à partir de l'état résolu, de stocker les mélanges correspondant, et d'élaguer en enlevant tous les cas qui contiennent un "R R2" ou "F' F" (bien sûr on élague à chaque fois qu'on augmente d). Comme ça on vire assez de positions pour pouvoir toutes les générer (sinon 9 mouvements de base puissance 11 = trop). Ensuite parmi ces positions (il y en a plein qui sont sous-optimales, on s'en fiche), on prend tous les cubes en 11 HTM, et pour chacun on regarde si la position a déjà été générer dans les cubes en 1 à 10 HTM (c'est assez lourd mais ça doit passer normalement). Et tous ceux qui ne sont pas dans les cubes de 1 à 10 HTM, bah ils sont obligatoirement en 11 HTM :oui:
raphael
Passe sa journée ici. Et dort ici, aussi
Messages : 650
Enregistré le : lun. juin 14, 2010 6:26 pm
Localisation : 77
Contact :

Re: TIPE sur le Rubik's cube

Message par raphael »

Cubeur-manchot a écrit :Le 24 ou 25 n'ayant pas été démontré proprement, je te conseille de refaire l'étude toi-même. Je pense aussi que pour le 2x2, sachant que le god's number en HTM est de 11, avec un petit 16 ou 17 HTM de mélange aléatoire on doit déjà être vraiment pas mal niveau homogénéïté
C'est ce que j'essaye de faire depuis bien 3 mois mais comme je l'ai expliqué, j'ai vraiment des soucis de mémoire et de temps de calcul qui font que je désespère d'avoir un résultat. En quoi cela n'a pas été fait proprement selon toi ?
Cubeur-manchot a écrit :Quand tu auras ta liste avec le parcours en largeur, ça te sera donné automatiquement, pour la ligne d=11
Oui théoriquement ça fonctionne, mais le temps d’exécution explose pour 9 déjà.
Avatar du membre
cyril
Helvète Underground
Messages : 4097
Enregistré le : jeu. juin 30, 2005 10:13 am
Localisation : En Suisse
Contact :

Re: TIPE sur le Rubik's cube

Message par cyril »

raphael a écrit : jeu. févr. 16, 2017 4:56 pm Par ailleurs aurais-tu un équivalent pour le 2x2x2 ?
https://www.randelshofer.ch/rubik/virtu ... s_big.html
... bonne lecture de cette page et des autres liées, c'est dense mais ça te donnera de bonnes idées !
Avatar du membre
Cubeur-manchot
VIP au club des 1000
Messages : 2999
Enregistré le : jeu. sept. 11, 2014 5:16 pm
Localisation : Bures-sur-Yvette (91)
Contact :

Re: TIPE sur le Rubik's cube

Message par Cubeur-manchot »

raphael a écrit : jeu. févr. 16, 2017 9:06 pm
Cubeur-manchot a écrit :Le 24 ou 25 n'ayant pas été démontré proprement, je te conseille de refaire l'étude toi-même. Je pense aussi que pour le 2x2, sachant que le god's number en HTM est de 11, avec un petit 16 ou 17 HTM de mélange aléatoire on doit déjà être vraiment pas mal niveau homogénéïté
C'est ce que j'essaye de faire depuis bien 3 mois mais comme je l'ai expliqué, j'ai vraiment des soucis de mémoire et de temps de calcul qui font que je désespère d'avoir un résultat. En quoi cela n'a pas été fait proprement selon toi ?
Je n'en sais rien, j'ai juste lu quelqu'un que je ne connais pas, un non-cubeur entre autre, qui a donné une suite décroissante et a dit que c'était la total variation de la chaine de Markov. Pour ton TIPE on te demande du travail que toi tu as fait, de réfléchir par toi-même, pas de recopier celui de quelqu'un d'autre :wink:
Pour ton problème de mémoire et de temps de calcul, ce que tu peux faire, par exemple, c'est faire un échantillonage sur 1 million de cubes (ou un nombre plus grand si ce n'est pas assez significatif, à toi de voir). L'algorithme sera le même, tu auras juste à tirer aléatoirement ces cubes parmi les anciens + les nouveaux.
(pourquoi n'y a-t-on pas pensé plus tôt ?)
raphael
Passe sa journée ici. Et dort ici, aussi
Messages : 650
Enregistré le : lun. juin 14, 2010 6:26 pm
Localisation : 77
Contact :

Re: TIPE sur le Rubik's cube

Message par raphael »

cyril a écrit :https://www.randelshofer.ch/rubik/virtu ... s_big.html
... bonne lecture de cette page et des autres liées, c'est dense mais ça te donnera de bonnes idées !
Très bien, merci !
Cubeur-manchot a écrit :Je n'en sais rien, j'ai juste lu quelqu'un que je ne connais pas, un non-cubeur entre autre, qui a donné une suite décroissante et a dit que c'était la total variation de la chaine de Markov. Pour ton TIPE on te demande du travail que toi tu as fait, de réfléchir par toi-même, pas de recopier celui de quelqu'un d'autre
Je suis d'accord mais c'est pas non plus une raison pour tout rejeter, même si c'est vrai que le travail manque de justification pour réellement le considérer comme valable.
Cubeur-manchot a écrit :Pour ton problème de mémoire et de temps de calcul, ce que tu peux faire, par exemple, c'est faire un échantillonage sur 1 million de cubes (ou un nombre plus grand si ce n'est pas assez significatif, à toi de voir). L'algorithme sera le même, tu auras juste à tirer aléatoirement ces cubes parmi les anciens + les nouveaux.
(pourquoi n'y a-t-on pas pensé plus tôt ?)
Qu'entends-tu par anciens et nouveaux ?
L'idée de restreindre le nombre de cube est bonne, mais j'ai peur d'avoir un problème : pour remplir ma matrice, je cherche pour tous les cubes de mon échantillon considéré (ici 1 million par exemple), les voisins de ce cube pour ensuite affecter les coefficients de la matrice. Mais ici, comme je ne considère plus tous les cubes possibles, il y aura forcément des cubes dont tous les voisins ne seront pas dans l'échantillon, et donc la matrice n'est plus stochastique. Je pense pas que j'obtiendrais quelque chose de concluant en faisant mes calculs par la suite..
raphael
Passe sa journée ici. Et dort ici, aussi
Messages : 650
Enregistré le : lun. juin 14, 2010 6:26 pm
Localisation : 77
Contact :

Re: TIPE sur le Rubik's cube

Message par raphael »

Ca fait longtemps que je n'ai pas donné de nouvelles !

J'ai pas mal avancé depuis la dernière fois, j'ai réussi à contacter une personne du CNRS qui a su m'aider.
En fait depuis le début je m'y prenais mal, puisqu'il n'est pas toujours obligé d'utiliser la matrice de transition pour accéder à la total variation qui nous indique si on est loin de l'uniformité ou pas. Donc au lieu d'utiliser une matrice 3674160x3674160 je n'ai plus besoin que d'un vecteur 3674160x1 ! Ceci a résolu pas mal de soucis de temps de calcul, même si c'est encore assez long, les calculs sont faisables.
J'ai pas beaucoup de temps en ce moment, mais je compte faire l'étude en HTM d'ici peu.
Avatar du membre
bongo
Passe sa journée ici. Et dort ici, aussi
Messages : 507
Enregistré le : dim. déc. 11, 2016 6:56 pm

Re: TIPE sur le Rubik's cube

Message par bongo »

Ah ha ! en plus Mines-Ponts c'est bientôt... mi-avril fin-avril ?
(1/3/5/12/50/100)
3^3 CFOP GTS 2M : 12.71 - 16.43 - 17.19 - 18.49 - 19.33 - 19.63
4^3 Yau Wuque: 1'16 - 1'25 - 1'26 - 1'30 - 1'36 - 1'39
5^3 Wushuang : 3'35 - 3'56 - 4'01 - 4'10 - 4'27 - 4'44
6^3 Red Unicorn: 7'04 - 7'45 - 7'54 - 8'05 - 8'28 - 8'56
Répondre