TIPE sur le Rubik's cube
-
- 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
Oui, X-ENS dans 3 semaines et Mines-Ponts dans la foulée.
- BallonSonde
- Né sur ce forum
- Messages : 159
- Enregistré le : ven. mars 10, 2017 9:14 pm
- Contact :
Re: TIPE sur le Rubik's cube
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.
-
- 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
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) :
Graphiquement ça donne ça :
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 !
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) :
Graphiquement ça donne ça :
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 !
- 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
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 ?
- BallonSonde
- Né sur ce forum
- Messages : 159
- Enregistré le : ven. mars 10, 2017 9:14 pm
- Contact :
Re: TIPE sur le Rubik's cube
Très belle courbe, et bon travail !
Le temps de mélange que tu calcules ici est associé à un algorithme de mélange bien particulier :
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 . Ensuite tu pourrais expliquer l'allure de la courbe ; ça, plus l'explication de ton programme de calcul devrait bien remplir le TIPE.
Attention avec cette conclusion, elle est attaquable de plusieurs manières...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).
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.
- 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,
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 . Ensuite tu pourrais expliquer l'allure de la courbe ; ça, plus l'explication de ton programme de calcul devrait bien remplir le TIPE.
-
- 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
Merci pour ces retours, je me remets dans mon TIPE, les concours étant terminés.
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.
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...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 ?
Le raisonnement suivant n'est-il pas valable ?BallonSonde a écrit :Les conclusions que tu en tires sont uniquement valables pour ce mélange.
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.
- BallonSonde
- Né sur ce forum
- Messages : 159
- Enregistré le : ven. mars 10, 2017 9:14 pm
- Contact :
Re: TIPE sur le Rubik's cube
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.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.
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 !
Et la réponse est... Non, malheureusement, pour plusieurs raisons.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é ?
- 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.
-
- 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
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.
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.
- 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
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
-
- 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
Hmm, non, sinon le mélange du record du monde serait de 4 mouvements.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
- 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
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.
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 >;.<'
Odder: we are all pretty god damn fast when we are not messing around :p and you are... just fucking retarded fast in comps >;.<'
- 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
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
-
- 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
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.
-
- 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
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).
"Singmaster has heard of solutions in 2 minutes, but I find this difficult to believe."
-
- 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
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.
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.