Mémoire assistée par ordinateur

Rappel des épisodes précédents

Comme tous les billets qui sont tagués Suite, le présent billet repose sur un contexte décrit précédemment, en l'occurrence dans le billet Perte de mémoire. Je vais le résumer rapidement ici, mais n'hésitez pas à y revenir si le résumé est trop succinct.

Dans les années quatre-vingt-dix, j'ai appris une méthode pour résoudre un Rubik's Cube, en assemblant des séquences de mouvements, appelées algorithmes, qui produisent un résultat élémentaire donné.

Je suis rapidement devenue incapable de réciter ces séquences, mais j'ai pu constater, à peu près une fois toutes les quelques années, que j'étais encore capable de les exécuter machinalement, jusqu'à l'été 2017, lorsque j'ai constaté la perte du dernier algorithme.

J'ai pu constater au passage que la méthode que j'ai apprise semble complètement absente d'internet, et du coup définitivement perdue.

J'espérais mollement que dans les mois qui suivent, je pourrais reprendre un cube, et retrouver machinalement la séquence, mais ça n'a malheureusement pas été le cas.

À la recherche de l'algorithme perdu

L'algorithme perdu est donc une séquence de mouvements du Rubik's Cube dont le résultat net est la rotation d'un tiers de tour de deux coins adjacents, comme ceci :

Je me souviens clairement que dans cette méthode, les algorithmes étaient décrits à partir de dix mouvements de base, qui sont la rotation d'un quart de tour, dans un sens ou dans l'autre, de la face principale ou d'une des quatre faces adjacentes.

Pour ne pas m'encombrer avec des notations plus ou moins pénibles à assimiler, dans le présent billet je vais désigner ces dix mouvements de base de la façon suivante : , , , , , , , , , et .

Je me souvenais aussi clairement que cet algorithme manquant est nettement plus long que les autres. Un vague souvenir me disait 22 ou 24 mouvements de base.

Enfin, les manipulations du cube m'ont laissée sûre que cet algorithme contient , plutôt vers le début, et qu'il se termine par .

Les choses en étaient à peu près là depuis l'été 2017, jusqu'à la coïncidence récente de voir un Rubik's Cube au cours d'un rangement il y a quelques semaines, de commencer à jouer au projet Euler, et de me dire qu'avec un petit coup de pouce de ma mémoire un ordinateur pourrait retrouver l'algorithme perdu, en brutalisant l'espace de recherche.

Assistanat électronique

Donc forte de mes petits programmes pour le projet Euler, j'ai appliqué une stratégie similaire à la modélisation d'un Rubik's Cube, l'application de séquences de mouvements, et l'itération sur ces séquences.

En vrai, j'ai cherché assez tôt à estimer la futilité de cette idée, mais quand j'ai vu que je pouvais déborder mon compteur 32-bits en une dizaine de minutes sur ma machine très peu performante, et que je pouvais explorer toutes les séquences d'au plus 10 mouvements de base en quelques minutes, j'ai pris confiance et j'ai commencé à développer sérieusement.

La partie un peu geek mais intéressante, c'est que ce n'est pas la peine de parcourir tout le monoïde libre sur les mouvements de base toutes les séquences de mouvements, déjà parce que c'est un groupe libre ça n'a pas d'intérêt de faire un coup puis son inverse, mais aussi parce que ce sont des quarts de tour, donc quatre mouvements identiques de suite s'annulent, et en fait trois mouvements identiques sont déjà explorés par le mouvement inverse, et ça ne sert à rien d'explorer deux fois un mouvement quand on a déjà exploré deux fois son inverse, car ça fait le même demi-tour.

J'ai fait mon itérateur en ne considérant que les éliminations du paragraphe précédent, alors qu'on pourrait faire mieux en utilisant le fait que les mouvements de deux faces opposées commutent. Par exemple on pourrait élaguer puisqu'il donne le même résultat que seul, qui a été exploré plus tôt. Je me suis dit que c'est trop compliqué à tester par rapport au temps d'exploration gagné.

Et en parallèle, j'ai fait marcher le cube, parce que l'explosion combinatoire fait que les séquences jusqu'à 12 mouvements s'explorent en quelques heures, 13 mouvements dépasse la journée, et j'aurais à redémarrer la machine avant d'avoir fini toutes les séquences de 15 mouvements.

J'ai quand même lancé une double itération pour chercher toutes les séquences qui correspondent à ce que j'ai ci-dessus, histoire d'occuper le CPU, des fois qu'il trouve avant que je code quelque chose de mieux.

Assistanat neuronal

Je cherchais quelque chose de mieux, parce que j'ai quand même bien plus de souvenirs que ce que j'ai déjà écrit, mais leur fiabilité est douteuse.

En particulier, je me souviens clairement que l'algorithme était découpé mentalement en deux parties, et dans la fraction de seconde de pause entre les deux la face principale a une forme de point d'interrogation, c'est-à-dire la première ligne, les deux carrés de droite de la deuxième ligne, et le carré central de la troisième ligne, tous de la même couleur, et les autres de couleur différente. La première partie était assez courte, je pensais vaguement trois coups. Et j'avais le souvenir très vague que les cuboïdes de ce point d'interrogation ne sont pas tous à leur place (c'est-à-dire que la couleur est bonne mais pas portée par le cube qui devrait être là).

Du coup j'ai cherché toutes suites de coups qui arrivent à cette forme, mais aucun de ceux d'au plus 4 mouvements ne font réagir ma mémoire, et la liste de 5 mouvements est trop longue et m'a découragée.

En manipulant le cube, j'ai senti qu'après , je sentais bien .

Du coup j'ai continué d'explorer ces coups, et j'ai commencé à sentir peut-être quelque chose en bas ( ou ), puis peut-être .

Et en posant ça comme ça, ça a fait émerger un vague souvenir de mon apprentissage de cet algorithme, dans lequel je remarquais une alternance de et entrecoupés de choses en haut et en bas, deux fois dans un sens puis une fois dans l'autre, à moins que ce ne soit l'inverse…

Évidemment, à chaque étape de ce que je retrouvais, j'ai passé la moulinette automatique pour trouver onze ou douze coups manquants.

Sans que rien n'en ressorte.

Bien choisir ses indices

Le problème qu'il y a dans l'accumulation de souvenirs comme ça, c'est qu'il est à peu près certain qu'il y a des erreurs dedans, mais c'est difficile de deviner a priori où. Je crois même qu'à chaque fois que je me suis amusée à draguer le fond de ma mémoire comme ça, il y a toujours eu une trahison par des souvenirs que je croyais très fiables.

Du coup j'ai commencé à remettre tout en question, ce qui fait retomber dans l'explosion combinatoire.

Par exemple, assez tôt dans ce processus, juste après être partie sur , je me suis dit que finalement ce n'est peut-être pas une séquence « à un moment assez tôt », mais plutôt le même que celui est au début de la séquence finale .

Du coup j'ai cherché tous les préfixes de . en restant de taille raisonnable, et de taille moins raisonnable en formant un point d'interrogation assez tôt.

En vain, encore une fois.

Enfin, en vain sur le plan informatique, parce que c'est en essayant de sentir ce que donne cette séquence sur le cube que j'ai retrouvé le reste, en particulier l'alternance de et entrecoupés de choses en haut et en bas, que je sentais vraiment bien.

Du coup au lieu de coller bêtement les deux séquences que j'avais retrouvées en 2017, j'ai collé les versions plus longues, genre et , toujours avec le point d'interrogation atteint en 2 à 5 coups.

Ça n'a rien donné non plus.

Pendant ce temps, j'ai continué de pratiquer ces suffixes, dans l'espoir que ça finisse par évoquer quelque chose à ma mémoire musculaire, au moins pour distinguer les deux branches.

Et puis à un moment j'ai fini avec et là, je le sentais bien.

Du coup j'ai lancé la recherche sur le plus gros suffixe que je sentais, à savoir , toujours avec le point d'interrogation initial atteint en 2 à 5 coups.

J'avais tellement essayé de trucs, qu'à ce stade, c'est à peine si je vérifiais la sortie du programme. Heureusement qu'il y a trouvé des tonnes de séquences, sinon j'aurais peut-être raté que la réponse était enfin là, sous mes yeux.

La brutalité du résultat

Le premier résultat de la liste est : pour former le point d'interrogation initial, suivi de obtenu par exploration exhaustive, suivi du suffixe prédéfini .

Et là, on remarque quelque chose de très moche : les quatre premiers coups s'annulent mutuellement, et sont juste là pour satisfaire le critère du point d'interrogation. Du coup cette recherche a réussi malgré le souvenir du point d'interrogation, et non pas grâce à lui.

D'ailleurs c'est même pire que ça, parce que j'avais exclu la possibilité d'atteindre le point d'interrogation en un seul coup, et le premier résultat qu'il me sort l'atteint en trois coups, dont deux qui s'annulent l'un l'autre.

Et pareil au niveau de l'autre jonction, toutes les solutions trouvées par exploration exhaustive se terminent par pour annuler le premier coup du suffixe imposé.

Résultat, après ces simplifications évidentes, on tombe sur la séquence

Je l'ai pratiquée quelques fois, et ma mémoire musculaire trouve que c'est ce qui colle le mieux de tout ce que je lui ai proposé, mais sans affirmation enthousiaste.

Le tout début, donne bien une forme de point d'interrogation, qu'on a le loisir d'observer pendant , mais à l'envers, en miroir.

La séquence dont j'avais cru me souvenir assez tôt, , n'apparaît pas du tout, mais c'est probablement la corruption du juste après le qui fait tourner le fameux point d'interrogation.

Quant à la séquence dont j'avais cru me souvenir sur la fin, , son premier mouvement est également faux, ou mal placé. Je ne sais pas si j'ai zapé le qui aurait dû être entre et , ou si c'est le qui a été corrompu en , mais j'aurais pu chercher très longtemps si ma mémoire n'avait pas fini par réparer cette erreur.

Enfin, ça fait 16 mouvements, alors que mon vague souvenir était au-dessus de la vingtaine. Je me souvenais que les algorithmes étaient de plus en plus longs, et avoir 8 mouvements dans les deux ne colle pas avec ce souvenir. Passer du simple au double ensuite est aussi suspect, parce que c'est « rond » pour que ça ne me marque pas.

Comme quoi, la fiabilité des neurones…

Conclusion

J'ai passé un bon bout de temps sur cette recherche, et le résultat n'est pas tellement à la hauteur en termes de satisfaction émotionnelle. C'était une énigme amusante, du même acabit qu'un problème du projet Euler, mais sans plus.

Je suis un peu peinée que même maintenant que je suis sûre d'avoir retrouvé l'algorithme manquant, et l'avoir répété quelques dizaines de fois, je n'arrive toujours pas à le ressortir sans notes. Ou du moins pas assez souvent pour pouvoir compter dessus pour résoudre un cube à l'improviste.

J'ai du mal à me motiver pour la réapprendre, mais je ne suis toujours pas complètement en paix avec la perspective de l'abandonner.

Annexe : la version complète de la méthode que j'ai apprise

Si ça intéresse quelqu'un, voici en entier la méthode que j'ai apprise.

Il s'agit d'abord de placer les pièces à deux faces (arrêtes) sans se préoccuper de leur orientation, puis orienter ces pièces, puis placer les pièces à trois faces (coins) sans orientation, puis les orienter.

Chacune de ces étapes est réalisée au moyen d'un algorithme, qui est une séquence qui fait un mouvement de base dans l'étape courante tout en préservant ce qui a été fait dans les étapes précédentes.

Et voici les quatre algorithmes :

1. 

2. 

3. 

4. 

Commentaires

Pas de commentaire pour le moment.

Poster un commentaire

Nom ou pseudonyme :

Adresse e-mail (facultatif, ne sera pas publié) :

Site web (facultatif) :

Format de mise en forme : format historique Markdown restreint

Enregistrer ces informations dans un cookie

Commentaire (sera publié dans cette page, voir les conseils de mise en forme ci-dessous) :

Message personnel (ne sera pas publié) :

Mise en forme historique : pour mettre en valeur un mot ou un groupe de mot, tapez une étoile de part et d'autre, sans mettre d'espace entre l'étoile et le mot, comme ceci : *mise en valeur*. Pour insérer un lien, mettez le entre crochets, comme ceci : [http://instinctive.eu/].

Mise en forme markdown : voir le guide détaillé, en résumé c'est le Markdown traditionnel, sans HTML ni titres, mais avec les tables PHP-Markdown-Extra.

Attention : les balises HTML entrées dans les commentaires seront affichées telles quelles, et non pas interprétées.