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 »

Oui, X-ENS dans 3 semaines et Mines-Ponts dans la foulée.
Bannière atoutcubes.com
Avatar du membre
BallonSonde
Né sur ce forum
Messages : 159
Enregistré le : ven. mars 10, 2017 9:14 pm
Contact :

Re: TIPE sur le Rubik's cube

Message par BallonSonde »

Aaah, c'est un sujet qui m'a l'air très intéressant ! Ce genre de problématique se rencontre d'habitude surtout avec des jeux de cartes (avec l'enjeu pour le casino de savoir si le paquet est assez bien mélangé), c'est rafraîchissant de le voir appliqué au cube. Je n'ai pas encore tout bien lu en détail, mais j'y repasserai bientô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 »

Je viens de finir l'étude en HTM !

J'ai donc considéré pour une position donnée, les 9 voisins atteignables en 1 coup au sens HTM (R,R',R2,F,F',F2,D,D',D2) ainsi que le cas où on ne fait rien. Ceci me donne donc 10 voisins, soit une probabilité de 1/10 pour chaque. A partir de là j'ai pu réaliser le traitement.

Voici l'évolution de la total variation (comprise entre 0 et 1, elle quantifie l'écart entre la répartition à l'instant t et la répartition uniforme) :

HTM TV(t) temps exécutions (s)
0 1 0
1 0.999997278381 3.0230000019073486
2 0.999982581131 3.44599986076355
3 0.999895214211 4.753000020980835
4 0.999392514269 15.373999834060669
5 0.996672981093 87.97199988365173
6 0.983027413124 171.90500020980835
7 0.953146150731 380.76550006866455
8 0.91145954404 371.30200004577637
9 0.873681113639 311.5349998474121
10 0.82526493274 134.69000005722046
11 0.767392107976 138.16799998283386
12 0.705632614649 144.39999985694885
13 0.643334589965 147.33200001716614
14 0.582430009523 148.8860001564026
15 0.524000632847 168.02199983596802
16 0.468675999286 153.02900004386902
17 0.416872185892 166.96200013160706
18 0.368983461422 164.04800009727478
19 0.325201272818 157.82699990272522
20 0.285556063134 157.04700016975403
21 0.249930563171 159.37099981307983
22 0.218124777301 157.21900010108948
23 0.189874700059 158.15499997138977
24 0.164910696845 161.26600003242493
25 0.142944855862 154.77699995040894
26 0.123700832194 155.65400004386902
27 0.106884309682 156.92700004577637
28 0.0922292238689 157.33500003814697
29 0.079489343438 152.57499980926514
30 0.068437310931 166.24699997901917
31 0.0588683053903 183.26500010490417
32 0.0505959396908 162.64200019836426
33 0.0434543010029 162.18799996376038
34 0.0372963093113 156.84300017356873
35 0.0319928505665 161.7739999294281
36 0.0274298301712 166.09150004386902
37 0.023506771397 232.32599997520447
38 0.0201364550308 203.2279999256134
39 0.0172428928036 216.20499992370605
40 0.0147605401796 228.61999988555908

Graphiquement ça donne ça :


Image


La définition de être bien mélangé est alors en fait donnée par le seuil à partir duquel on considère que la total variation est suffisamment faible, j'ai vu dans différents documents que la valeur de 1/2e = 0.184 était assez classique. Pour l'instant je considère donc cette valeur comme seuil.

Avec les résultats présentés plus haut, ce seuil est atteint pour t_mélange=24 coups, mais en fait on peut abaisser cette valeur pour deux raisons:
- en moyenne 1 fois sur 10 on n'a pas effectué de mouvement donc t_mélange=24-0.1*24=22.6
- certaines combinaisons de mouvements sont impossibles (par exemple R puis R2 ou R' ou R, puisque cela correspond à un seul coup, idem pour F et D), ainsi 3 fois sur 10 le coup est inutile donc t_mélange=22.6-0.3*22.6=15.8

J'en déduis qu'avec la valeur de seuil choisie, le cube est bien mélangé après 16 coups en HTM (j'avais au préalable refait l'étude en QTM, on trouve 24 coups pour le même seuil).

Si vous avez des remarques, je suis bien sur preneur !
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 »

Excellent ! :) mais juste une question (sans doute bête, mais je ne suis pas omniscient) : pourquoi définir le mouvement "ne rien faire" si c'est pour l'enlever après ? N'y a-t-il pas moyen de directement ne pas le compter dès le début ?
Avatar du membre
BallonSonde
Né sur ce forum
Messages : 159
Enregistré le : ven. mars 10, 2017 9:14 pm
Contact :

Re: TIPE sur le Rubik's cube

Message par BallonSonde »

Très belle courbe, et bon travail !
raphael a écrit : dim. avr. 02, 2017 9:36 pm Avec les résultats présentés plus haut, ce seuil est atteint pour t_mélange=24 coups, mais en fait on peut abaisser cette valeur pour deux raisons:
- en moyenne 1 fois sur 10 on n'a pas effectué de mouvement donc t_mélange=24-0.1*24=22.6
- certaines combinaisons de mouvements sont impossibles (par exemple R puis R2 ou R' ou R, puisque cela correspond à un seul coup, idem pour F et D), ainsi 3 fois sur 10 le coup est inutile donc t_mélange=22.6-0.3*22.6=15.8

J'en déduis qu'avec la valeur de seuil choisie, le cube est bien mélangé après 16 coups en HTM (j'avais au préalable refait l'étude en QTM, on trouve 24 coups pour le même seuil).
Attention avec cette conclusion, elle est attaquable de plusieurs manières...

Le temps de mélange que tu calcules ici est associé à un algorithme de mélange bien particulier :
  • à chaque étape, on choisit un mouvement uniformément parmi les 9 possibles (R,R',R2, F... D...) et le mouvement "rien", sans contrainte.
Les conclusions que tu en tires sont uniquement valables pour ce mélange. Si tu veux conclure pour un autre mélange, par exemple :
  • A la première étape, on choisit un mouvement au hasard parmi 9 possibles (R,R',R2, F... D...),
  • Aux étapes suivantes, on en prend un parmi les 6 qui ne touchent pas la face qu'on vient de tourner,
il faut changer ta chaîne de Markov. Je te laisse construire la chaîne de Markov associée, et vérifier si les hypothèses nécessaires (ergodicité, apériodicité...) sont vérifiées. Une fois que tu l'auras formalisée tu pourras adapter ta méthode directement.
Indice : il faut garder en mémoire le dernier mouvement effectué.

Pour résumer : ton heuristique est très naturelle (et à mon avis elle marche), mais si tu veux tout déchirer, montres aux examinateurs que tu sais faire la même chose pour d'autres mélanges :smt023:. Ensuite tu pourrais expliquer l'allure de la courbe ; ça, plus l'explication de ton programme de calcul devrait bien remplir le TIPE.
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 »

Merci pour ces retours, je me remets dans mon TIPE, les concours étant terminés.
Cubeur-manchot a écrit :pourquoi définir le mouvement "ne rien faire" si c'est pour l'enlever après ? N'y a-t-il pas moyen de directement ne pas le compter dès le début ?
En fait "ne rien faire" est utile en QTM puisque avec seulement des quarts de tour on ne peut atteindre que la moitié des positions en fonction de la parité du nombre de coups. En ne faisant rien avec une probabilité non nulle, on s'affranchit de ce problème. Ici, en HTM, les demi-tours réalisent déjà cela, ils sont donc inutiles, mais je m'en suis rendu compte seulement après...
BallonSonde a écrit :Les conclusions que tu en tires sont uniquement valables pour ce mélange.
Le raisonnement suivant n'est-il pas valable ?

On considère que la façon de mélanger énoncée plus haut donne 22 mouvements en HTM. Ensuite on "oublie" la chaîne de Markov, à un mélange donné de 22 mouvements suivant la chaîne, l'étude probabiliste des enchaînements possibles montre qu'en fait certains mouvement se télescopent ( par exemple R puis R2 devient R'), et que donc on peut réduire la longueur du mélange. On ne définit alors pas de nouvelle chaîne.
Avatar du membre
BallonSonde
Né sur ce forum
Messages : 159
Enregistré le : ven. mars 10, 2017 9:14 pm
Contact :

Re: TIPE sur le Rubik's cube

Message par BallonSonde »

raphael a écrit : dim. mai 21, 2017 11:35 am On considère que la façon de mélanger énoncée plus haut donne 22 mouvements en HTM. Ensuite on "oublie" la chaîne de Markov, à un mélange donné de 22 mouvements suivant la chaîne, l'étude probabiliste des enchaînements possibles montre qu'en fait certains mouvement se télescopent ( par exemple R puis R2 devient R'), et que donc on peut réduire la longueur du mélange. On ne définit alors pas de nouvelle chaîne.
C'est un raisonnement valable en première approximation, et la conclusion sera du bon ordre de grandeur ; mais c'est loin d'être une preuve ! Plusieurs obstacles empêchent même de conclure directement.

L'explication la plus directe et la plus juste, bien que pas forcément la plus satisfaisante, est que tu ne calcules pas réellement le temps de mélange pour un scramble sans télescopage. Le temps de mélange T est défini en fonction de la distance en variation totale à la loi uniforme sur les configurations du cube : après T mouvements, la distance en variation totale doit être plus petite que 1/2e. Il faut donc obligatoirement calculer la d_VT pour trouver T !
Un objecteur a écrit : Oui, mais j'ai déjà calculé la d_VT pour mon mélange à moi. Est-ce que je ne peux pas en déduire la d_VT pour cet autre mélange, qui est simplement le premier simplifié ?
Et la réponse est... Non, malheureusement, pour plusieurs raisons.
  • D'une part, le mélange sans télescopage n'est pas une "simplification" facilement exploîtable de ton mélange (le nombre de mouvements est constant, alors qu'après simplification du tien il est aléatoire)
  • On ne peut pas conditionner à ce que le mélange ait une longueur donnée après simplification, puisqu'il n'y a aucun moyen d'en garder trace dans le calcul de d_VT,
  • Le d_VT que tu as calculé est une moyenne pondérée de la distance en variation totale du mélange sans télescopage, donc un mélange de plusieurs valeurs dont une seule nous intéresse, ce qui parasite le calcul et donc le choix du temps de mélange.
On n'a donc pas le choix : pour confirmer ton intuition et ton raisonnement, il faut adapter la chaîne de Markov...
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,

J'ai essayé de mettre en place une nouvelle chaîne de Markov, sur le papier ça semble être faisable, mais après j'ai trop de mal à adapter mon programme informatique. Surtout que la date butoir approche...
Je me concentre donc plutôt sur ma présentation et mon rapport. Je prépare aussi des réponses à certaines questions classiques qu'on pourrait me poser.

J'en ai une à laquelle je n'ai pas de réponse : pourquoi la WCA a choisi de fixer à 11 mouvements les mélanges officiels ? Un rapport avec le diamètre du 2x2 ? Merci pour vos éclaircissements.
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 : dim. juin 04, 2017 7:46 pm J'en ai une à laquelle je n'ai pas de réponse : pourquoi la WCA a choisi de fixer à 11 mouvements les mélanges officiels ? Un rapport avec le diamètre du 2x2 ? Merci pour vos éclaircissements.
Si je ne dis pas de bêtises, les mélanges officiels sont optimaux pour les puzzles dont on peut générer les mélanges optimaux, dont le 2x2
Nameless
Passe sa journée ici. Et dort ici, aussi
Messages : 832
Enregistré le : mar. janv. 19, 2016 7:06 am
Contact :

Re: TIPE sur le Rubik's cube

Message par Nameless »

Cubeur-manchot a écrit : dim. juin 04, 2017 10:58 pmSi je ne dis pas de bêtises, les mélanges officiels sont optimaux pour les puzzles dont on peut générer les mélanges optimaux, dont le 2x2
Hmm, non, sinon le mélange du record du monde serait de 4 mouvements.
Image
Avatar du membre
oranjules
"Le slip de Superman !"
Messages : 2837
Enregistré le : lun. août 24, 2009 1:56 pm
Contact :

Re: TIPE sur le Rubik's cube

Message par oranjules »

Pour 22, 33, 44 et pyra, au lieu d'utiliser une suite de mouvements aléatoire, on choisit une position aléatoire puis on la résout. C'est ce que voulait dire Cubeur-Manchot.
Par contre effectivement le mélange est pas optimal, sûrement entre autre pour cacher ce genre de mélanges.
Odder: Bruno, Oka and I?
Odder: we are all pretty god damn fast when we are not messing around :p and you are... just fucking retarded fast in comps >;.<'
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 »

Oui c'est ça que je voulais dire, enfin ça partait de là. Du coup comme pour le 2x2 c'est assez facile de trouver le mélange optimal on peut le faire, parce que ça ne change rien si le mélange fait 4 mouvements à la table de mélanges, les compétiteurs n'ont pas cette information, et les mélangeurs ne résoudront pas ce mélange. Je me suis donc dit que puisque ça ne changeait rien autant faire toujours les mélanges optimaux à la table de mélange, et que c'était donc le cas pour le 2x2. Mais je peux me tromper hein :)
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 »

Je vois, merci. Qui plus est, si des mélanges optimaux étaient donnés, on repérerait plus facilement les mélanges vraiment trop faciles.
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 : dim. avr. 02, 2017 9:36 pm J'en déduis qu'avec la valeur de seuil choisie, le cube est bien mélangé après 16 coups en HTM
Je trouve ça très bizarre parce que l'écrasante majorité des cubes est à 17 coups ou plus (voir par exemple la répartition des cubes par distance sur http://cube20.org/).

Pour la question sur les mélanges de 2x2x2 en compétition, voici ce que dit le réglement (https://www.worldcubeassociation.org/re ... scrambling) :
  • 4b3) Caractéristique du programme utilisé pour les mélanges : 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). Les règles additionnelles suivantes s'appliquent :
  • 4b3b) Cube 2x2x2 : la position aléatoire doit nécessiter au moins 4 mouvements pour être résolue.
  • 4f) Les séquences de mélanges pour une compétition doivent être générées en utilisant la version officielle du mélangeur officiel de la WCA (disponible sur le site internet de la WCA).
Donc ce qui compte c'est que le mélange soit équiprobable parmis les états pas trop proches du but (la distance varie en fonction du casse-tête), le réglement n'impose pas que les mélanges soient optimaux par contre il impose l'utilisation d'un programme en particulier.
"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 »

Les chiffres que tu donnes sont ceux du 3x3, les 16 mouvements que j'ai trouvés sont ceux du 2x2.

Par ailleurs j'ai fait ma présentation vendredi dernier, ca s'est plutôt bien passé. Mais vu les questions du jury (vraiment très basiques), je me demande s'ils ont réellement pu apprécier les points plus techniques.
Répondre