TIPE sur le Rubik's cube

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


Bonjour à tous,

Je suis en deuxième année de prépa MP (5/2 même) donc je refais un TIPE, et cette année j'ai envie de faire ça sur le cube. Je sais que le thème est assez classique, j'ai donc choisi une approche un peu originale. Je voudrais essayer de répondre à la question suivante : Quel est le nombre de coups minimum pour être sûr que le 3x3 est mélangé lorsqu'on le mélange à la main ? En gros quand on mélange son cube à la main comme ça sans réfléchir (donc plus ou moins aléatoirement), en combien de coups est-on sûr que le cube est mélangé. Pour l'instant je pense m'intéresser au 3x3 mais la taille du cube peut évoluer en fonction de la difficulté.

Pour ce projet j'envisage déjà plusieurs points sur lesquels je vais travailler :

-il faut d'abord que je définisse ce que signifie "mélangé" pour un cube. Ainsi je pensais définir une distance sur le cube : par exemple tel pièce est à 3 coups de sa place dans le cube résolu, sa distance est donc de 3. Alors en sommant sur toutes les pièces du cube j'obtiendrais un indice de mélange du cube. En regardant quel est l'indice de mélange dans des cas où je suis sûr que le cube est bien mélangé, je pourrais définir un indice seuil qui définit si le cube est considéré comme mélangé ou non.
Cependant il y a plusieurs soucis à cette méthode, notamment le fait qu'on peut avoir des blocs déjà formés sur le cube (ce qui implique un mélange plus simple) sans que l'indice augmente. Aussi le fait que ça n'est pas parce qu'une pièce est proche de sa position à un instant donné que le mélange est facile. Le fait est que la méthode de résolution choisie influence aussi la difficulté du mélange.

-pour simuler un mélange à la main (donc aléatoire), je pense utiliser les marches aléatoires. Ca me permettrait de voir comment évolue l'indice du mélange à chaque nouveau coup, et de faire une étude probabiliste pour connaitre à partir de quel nombre de coups on peut considérer le cube comme mélangé.

-pour pouvoir accélérer ce travail je pense utiliser un cube implémenté sous Python, j'avoue que je suis pas très bon en informatique donc ça pourrait me faire perdre du temps pour une partie pas si intéressante du TIPE.

Le TIPE est pas un travail qui est censé aboutir à un résultat vraiment utilisable mais plus l'occasion de mettre en place une démarche scientifique. Je suis amené à prendre des hypothèses simplificatrices sur certains points.

Voilà en gros mon projet, je poste ici pour avoir des avis et conseils. Je ne suis qu'au début de mon travail donc si vous avez des idées, ou autres sujets sur le cube ça m'intéresse. Je suis aussi intéressé par vos avis sur la façon de définir un indice de mélange, l'approche que j'ai pour l'instant étant assez naïve.

Merci !
Curvy
Né sur ce forum
Messages : 124
Enregistré le : mar. août 30, 2016 3:36 pm


Je pense pas qu'il y est une reponse a ta question tu oeux avoir un melange de 250moves qui se resoux en 5 htm et un melange en 15moves qui amene ton cube dans une position completement random.
Quand a ta methode de calcule la distance pice/place de cette piece je suis scpetique. Une zbll aura souvent moin de moves pourtant elle modifiera beaucoup plus le cube.
Et si cette question est "resoluble " je pense que la response est le minimum moyen de couo pour resoudre le cube soit 18 moves si ma memoire est bonne.
Sur ce je laisse les matheux te repondre plus en detail
oranjules
"Le slip de Superman !"
Messages : 2837
Enregistré le : lun. août 24, 2009 1:56 pm


Curvy c'est 20 mouvements pour résoudre le cube au maximum, pas 18.

C'est hyper intéressant comme approche, et ça change pas mal :) Y a moyen que ce soit assez compliqué effectivement, tout le travail est vraiment dans la partie de définition de "bien mélangé". Ce genre de travail a été fait dans des jeux de cartes par exemple, tu peux partir de là pour avoir une bonne base. (notamment justement la définition de "bien mélangé", tu as le même genre de souci et certains y ont sûrement déjà réfléchi).
Pour un début je pense qu'il serait pas mal de se concentrer sur les blocs, c'est la manière la plus évidente de voir qu'un mélange est simple (pas mal d'autres facteurs dépendent effectivement de la méthode, et sont plus compliqués à détecter).
Par contre la partie informatique sera déterminante : tout réside dans la détection de si un cube est bien mélangé ou non : après avoir défini les critères, il faut être capable de les tester. Cependant je pense que ce ne sera pas si dur que ça, il suffit de créer le cube, les différents mouvements possibles, et ensuite de rajouter des tests selon les définitions que tu choisis, il n'y a aucun algo compliqué par exemple (pas besoin de t'embêter à faire les tests de manière vraiment efficace, si par exemple tu veux vérifier qu'il n'y a pas de blocs 2x2x2, vérifier qu'aucun des 8 possibles n'existe suffit même s'il y aurait des méthodes plus élaborées). Par contre je suis une quiche en python donc j'ai pas vraiment de conseils pratiques à donner.

Donc voila, je pense qu'il faut d'abord que tu fasses la partie informatique puisque c'est ce qui te bloquera le plus. Une fois que tu auras un cube, des mouvements, et que tu pourras faire une marche aléatoire dessus, tu pourras tester plusieurs définitions de bons mélanges et les résultats seront intéressants :)

Je trouve le projet stylé donc je serais pas contre que tu nous donnes certains résultats quand tu en auras :)

Bon courage !
raphael
Passe sa journée ici. Et dort ici, aussi
Messages : 650
Enregistré le : lun. juin 14, 2010 6:26 pm


Merci pour ces retours au fait ! Voilà ou j'en suis deux semaines après :

J'ai codé un 2x2x2 sur Python avec tous les mouvements de base (le 3x3x3 viendra après). J'ai voulu voir ce que donnait ma stratégie naïve, c'est-à-dire en regardant comment est orientée chaque pièce et à quelle distance elle est de son emplacement résolu. Tout ceci me donne un indice de mélange pour une position du cube donnée, plus l'indice est grand plus le cube est mélangé (du moins au sens de mélangé que j'ai pour l'instant).

Du coup j'ai fait une marche aléatoire sur le 2x2x2 puis j'ai regardé à chaque coup supplémentaire comment évoluait l'indice du mélange. Voici ce que ça donne pour une seule marche aléatoire de 50 coups : ici
Et en moyenne sur 2000 marches aléatoires de 50 coups : ici

On voit bien sur le deuxième qu'en moyenne après 10 coups en gros, mélanger ne sert plus à rien puisque l'indice est presque constant.

Voilà, je vais réfléchir à l'analyse des blocs pour pouvoir affiner mon critère de cube mélangé ou pas. Ensuite je verrai pour le 3x3x3.
N'hésitez pas si vous avez des remarques !
Spols
Le belge du Magic
Messages : 5177
Enregistré le : jeu. août 18, 2005 2:44 pm


Salut,

La première chose à laquelle je pense, c'est que le 222 n'a pas de pièce fixe donc il faudrait voir non pas un cas résolu, mais les 24 cas résolus.
par exemple si tu fait U D', tu a un indice de mélange de 0 mais chaque pièce est à 1 déplacement de sa position initiale. Je me demande si tu prends cela en compte.

Pour le 333, les centres sont fixe, tu peux donc les utiliser comme référence.
raphael
Passe sa journée ici. Et dort ici, aussi
Messages : 650
Enregistré le : lun. juin 14, 2010 6:26 pm


Ah oui en effet j'avais pas pensé à ça. Je vais voir comment régler ça, merci !
raphael
Passe sa journée ici. Et dort ici, aussi
Messages : 650
Enregistré le : lun. juin 14, 2010 6:26 pm


J'ai lu un certain nombre d'études sur le mélange d'un jeu de cartes, et notamment sur la question du nombre de coups à donner pour pouvoir considérer le jeu comme mélangé (mixing time). Ces études se basent souvent sur les chaînes de Markov, théorie que je ne connais pas très bien pour l'instant, mais j'ai l'impression que ça peut être accessible pour l’utilisation dont j'en ai besoin. Dans ces études ils considèrent que le nombre de coups donné dans le mélange est suffisant quand toutes les positions sont équiprobables, qu'on se rapproche d'une loi uniforme donc.
Je voudrais donc adapter ça sur le cube, mais je me demande si ce critère est vraiment bon. Pensez-vous que si on a donné assez de coups pour que chaque position du cube soit équiprobable alors c'est que le cube peut être considéré comme mélangé ? Merci pour votre aide.
oranjules
"Le slip de Superman !"
Messages : 2837
Enregistré le : lun. août 24, 2009 1:56 pm


Le nombre de coups dépendra juste de la marge d'erreur autour de l'équiprobabilité que tu cherches, et à un moment ça devrait plafonner, ça pourrait être intéressant de voir quand ça plafonne justement (la marge d'erreur en fonction du nombre de coups par exemple).
Les chaînes de Markov c'est pas hyper compliqué (tant que ça reste simple, après y a les chaînes de Markov cachées, ce genre de choses, c'est plus tendu mais tu devrais pas en avoir besoin)
raphael
Passe sa journée ici. Et dort ici, aussi
Messages : 650
Enregistré le : lun. juin 14, 2010 6:26 pm


fernique a écrit :

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).
J'ai trouvé ça sur le forum (http://forum.francocube.com/viewtopic.p ... 0&start=30), ça pourrait pas mal m'aider puisque en gros ça répond à la question que je me pose. Cependant je comprends pas comment créer la matrice de transition pour pouvoir ensuite faire des calculs. Vu sa taille colossale, ça peut pas être fait à la main, mais alors comment la générer ?
raphael
Passe sa journée ici. Et dort ici, aussi
Messages : 650
Enregistré le : lun. juin 14, 2010 6:26 pm


Je relance si jamais quelqu'un peut m'aider.
Cubeur-manchot
VIP au club des 1000
Messages : 2999
Enregistré le : jeu. sept. 11, 2014 5:16 pm


raphael a écrit :
fernique a écrit :

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
J'ai trouvé ça sur le forum (http://forum.francocube.com/viewtopic.p ... 0&start=30), ça pourrait pas mal m'aider puisque en gros ça répond à la question que je me pose. Cependant je comprends pas comment créer la matrice de transition pour pouvoir ensuite faire des calculs. Vu sa taille colossale, ça peut pas être fait à la main, mais alors comment la générer ?
Ne me jetez pas de trop grosses pierres si je dis des bêtises, ma prépa est déjà bien loin... (espérons de na pas dire la connerie du siècle)
On veut la matrice de transition, c'est-à-dire la matrice de probabilité de passage d'un état à un autre par 1 mouvement. Bon déjà dans la pratique on ne peut pas la générer parce qu'elle est colossalissime (colossale au carré), mais les maths c'est cool :D (parce qu'on aime les clichés)

Déjà pour moi la matrice de transition est symétrique, parce que tu as la même proba d'aller d'un état i à un état j en 1 move que l'inverse.
Si tu es sur un 2x2 et en QTM, sur chaque ligne tu as 7 valeurs non nulles, qui sont les 7 positions atteignables depuis un état donné et en 0 ou 1 move. On a d'ailleurs fixé ces probas à 1/7 chacune.

J'aurais donc fait :
Créer P comme matrice diagonale 1/7 * I3674160
Pour chaque état du i du cube, générer les 6 états j1, j2, j3, j4, j5, j6 atteignables depuis l'état i en 1 move, et affecter 1/7 à Pi,j.
Ça te fait une complexité en [nombre de mouvements]*[nombre d'états], ce qui n'est pas trop mauvais. Après on peut peut essayer d'être plus sioux en utilisant la symétrie pour ne pas générer deux fois chaque transition, m'enfin c'est seulement un facteur 2.

Remarque : pour le 3x3 c'est exactement pareil, et même pour chaque cube NxN, et même chaque twisty puzzle, parce qu'il n'y a pas beaucoup d'états atteignables depuis un état donné, ce qui nous donne une matrice creuse.

Autre remarque : si je n'ai pas dit trop de bêtises jusque là, on a tout intérêt à stocker uniquement la liste des adjacences, plutôt que de trimbaler la matrice entière (puisque justement elle est creuse).

Encore une autre remarque : dis donc je ne savais pas qu'on avait des sanguins comme ça sur le forum :smt048
oranjules
"Le slip de Superman !"
Messages : 2837
Enregistré le : lun. août 24, 2009 1:56 pm


(Désolé de pas avoir répondu plus tôt, j'avais pas trop le temps)

Effectivement ça n'a pas de sens de générer la matrice entière, c'est beaucoup trop gros et beaucoup trop vide. Dans ce cas particulier je représenterais plutôt ça sous forme d'automates (t'es en info ou SI ?), avec un état par état du cube. Ça reste énorme, mais pour le 22 ça peut rester utilisable (ça prendra quand même plusieurs Mo en mémoire donc ça sera long à utiliser en plus)
raphael
Passe sa journée ici. Et dort ici, aussi
Messages : 650
Enregistré le : lun. juin 14, 2010 6:26 pm


Moi non plus j'ai pas eu beaucoup de temps pour avancer, mais merci de vos retours. Je fais option SI donc je maitrise pas spécialement les automates.
J'en ai parlé avec mon prof d'informatique pour tous et il m'a conseillé le logiciel R, sachant qu'il y a un module dédié sur Python, je vais donc essayer avec ça pendant les vacances de Noël.
bongo
Inamovible
Messages : 487
Enregistré le : dim. déc. 11, 2016 6:56 pm


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 ?

Je pense qu'une distance absolue (mais ça dépend si tu comptes une opération L² comme un mouvement ou comme deux mouvements), où on sait que le nombre maximum de mouvement pour le meilleur algo est 26 (L² dans ce cas est compté comme 2 mouvements).

Apparemment ça bouge un peu sur ce nombre dit de dieu :
https://fr.wikipedia.org/wiki/Rubik's_C ... k.27s_Cube

20 ou 18 (attention à comment est compté un mouvement).


Et sur ce site les distances par configuration :
http://www.cube20.org/
rafoo
VIP au club des 1000
Messages : 2861
Enregistré le : jeu. avr. 09, 2009 11:57 am


Salut,

Ça fait des années que je n'ai pas posté, je m'appelle aussi Raphaël et j'ai aussi fait un TIPE sur le Rubik's Cube :D .

Je trouve que c'est une supère idée de TIPE ! Le risque avec un TIPE sur le Rubik's Cube c'est de faire de la vulgarisation en théorie des groupes et en topologie sans vraiment faire de maths au final, le fait d'axer sur un problème concret comme le mélange à la main rend le TIPE très intéressant.

Je pense que c'est une très bonne idée de commencer par le 2x2x2 parce que ça permet d'avoir une vision d'ensemble. On peut stocker sur un ordinateur normal toutes les configurations du 2x2x2 avec la séquence de coups qui permet de les résoudre. En particulier, ça permet de calculer à quel point ton "indice de mélange" est corrélé à la distance à l'état résolu (en nombre de coups). Si tu obtiens une bonne corrélation, ça semble raisonnable de supposer qu'on aurait une corrélation similaire sur le 3x3x3 (une bonne "hypothèse simplificatrice"), sinon il faut sans doute revoir ton indice.
Spols a écrit :
La première chose à laquelle je pense, c'est que le 222 n'a pas de pièce fixe donc il faudrait voir non pas un cas résolu, mais les 24 cas résolus.
par exemple si tu fait U D', tu a un indice de mélange de 0 mais chaque pièce est à 1 déplacement de sa position initiale. Je me demande si tu prends cela en compte.
Une manière simple de résoudre ce problème c'est de considérer que la pièce LBD est fixe. Du coup il n'y a qu'un cube résolu et en prime on a moins de mouvements à considérer. D'ailleurs certains vrais 2x2x2 ont effectivement le mécanisme fixé sur l'une des huit pièces.

Un autre point sur lequel il faut être vigilant c'est la question de la parité. Si tu as la mauvaise idée de partir sur la métrique QTM (c'est-à-dire que tu comptes les demi-tours comme deux fois plus cher que les quarts de tours) alors tu auras beau faire 200 coups sur ton cube, tu n'auras pas du tout une répartition uniforme parce que tu n'atteindra que la moitié des états possibles (par contre si tu fais 201 coups tu atteindras l'autre moitié).

Comme précisé dans le topic que tu cites, en compétition, on ne mélange le cube "à la main" ni dans le cas du 2x2x2 ni dans le cas du 3x3x3 mais cela n'a pas toujours été le cas. Ça serait sans doute intéressant de comparer ton résultat avec les bornes qui étaient choisies.
51 messages Page 1 sur 4