Dans ma dernière vidéo, je me suis amusé à écrire un bout de code qui propose une résolution automatisée des jeux à la WORDLE ou SUTOM. Tout ça m’a évidemment été inspiré par la formidable vidéo de 3Blue1Brown sur le sujet !

J’avais promis dans la vidéo que je partegerai le code, alors le voici avec quelques explications.

Le code est disponible ici : https://github.com/scienceetonnante/WordleSutom

Il n’y a vraiment rien de sophistiqué dans l’algorithme une fois qu’on a compris qu’on cherche à identifier le coup qui maximise l’espérance de l’information acquise. Pour faire ça, on a essentiellement besoin d’un ingrédient : une fonction qui détermine si un mot peut toujours prétendre être la réponse, étant donné l’état actuel la partie. Au début quand on ne sait rien, tous les mots peuvent prétendre à être la solution. Au fur et à mesure que la partie avance, la liste des suspects se restreint.

Pour faire ça, on doit modéliser d’une façon ou d’une autre « l’état actuel de nos connaissances ». Au début j’ai essayé de faire un truc subtil en maintenant une liste de lettres vertes, grises et jaunes. Et puis je me suis rendu compte que ça n’était pas si simple notamment à cause de la question des lettres doubles. Si on part du principe qu’il peut y avoir des lettres qui apparaissent plusieurs fois, la notion de couleur d’une lettre devient dépendante du contexte (à part pour les vertes). Avec le mot TAPIS, si vous jouez TATIN le premier T sera vert, le second gris. Mais si le mot est TARTE, TATIN donnera un vert et un jaune. Je me suis donc résolu à ne pas finasser, et pour représenter l’état de connaissances, j’enregistre bêtement la liste des coups joués et des résultats obtenus.

Pour manipuler les « suites de carrés de couleur », j’ai choisi une représentation numérique : 0 pour gris, 1 pour jaune, 2 pour vert. Et ensuite je code un pattern du genre 🟩🟩⬛🟨⬛ par « 22010 » et donc par le nombre qu’il représente en écriture ternaire (ici \(2 + 2.3 + 0.3^2 + 1.3^3 + 0.3^4\)). Un motif est donc codé par un entier entre 0 et \(3^K-1\) où K est le nombre de lettres.

J’ai implémenté une variante « SUTOM » où la première lettre est donnée. Ca marche bien aussi.

Pour l’histoire de « jouer pour acquérir de l’information » vs « jouer pour gagner », j’ai fait un choix basique : s’il reste moins de 3 possibilités, je tente une des 3. Sinon je cherche le mot qui apporte le plus d’informations, même s’il n’est pas dans la liste des candidats.

Pour les performances, j’obtiens une moyenne de 3.5 coups sur le WORDLE classique (en français). Sur un SUTOM à 7 lettres (dont la première est donnée), je suis plutôt autour de 2.6.

J’ai aussi joint une version « interactive », où vous pouvez jouer une vraie partie sur WORDLE ou SUTOM en même temps. Le code vous suggère un coup, vous entrez ce que le site vous a répondu, et ainsi de suite.

Il y certainement moyen d’améliorer la rapidité du code. J’ai choisi de faire en C++ mais je n’ai rien parallélisé, hors il y a moyen car il y a de la boucle imbriquée à profusion ! Par exemple pour trouver la meilleure ouverture, on doit examiner 4000 ouvertures, et pour chacun des 243 motifs, il faut voir si chacun des 4000 mots candidats est possible. Ca fait donc « 4000 x 243 x 4000 » itérations. Avec 5 lettres, la meilleure ouverture WORDLE est trouvée en environ 1 minute (une fois connue, évidemment je l’ai mise en dur). Une fois le premier coup passé, ça va très vite. Il y aurait un intérêt à tabuler les ouvertures SUTOM pour chacune des 26 lettres.

20 Comments

  1. Est-ce qu’il ne faudrait pas pour être plus précis, prendre en compte les possibilités qui découlent du choix du mot ?

    Par exemple si on a le mot ARBRE qui apporte 4 bits d’informations, et le mot FRUIT qui apporte 3 bits d’informations, on peut se dire qu’il vaut mieux jouer arbre. Oui mais si jouer arbre amène à une configuration où il ne reste plus que des possibilités qui ne donnent qu’un bit d’informations, alors que le mot fruit lui continu d’offrir des possibilités qui apportent 3 bits d’informations. Je serais plus tenter de finalement jouer le mot fruit car c’est ce qui est le plus rentable sur le long terme.

  2. Je suis très étonné que tu fasses cette vidéo sans jamais prononcer le mot « entropie ». Mais finalement c’est très clair comme ça et il y en a en fait pas besoin.

  3. Je donne des cours de prog si tu veux lol
    Pour generer une grille de mot croisé avec tout le dico francais je met trente seconde …en js….lol….m enfin ton truc marche.deja ca.sur de si petit volume….faut pas se prendre la tete.force brute…recursion aussi.faut pas avoir peur.

  4. Est ce qu’une solution plus efficace (même si beaucoup plus couteuse) ne serait pas de tester des mots qui existe mais bien toutes les situations existantes ? Par exemple pour le premier essai, la probabilité avoir bon est quasiment nulle et il se pourrait qu’il existe une solution donnant plus d’information que TARIE en premier essai mais qui n’est pas un mot français (comme ARTIE par exemple). Si on part du principe que la derniere lettre sera un E, il n’y a que 26^4 possibilités, ce qui reste raisonnable.

    • Bonjour Gaetan
      Ce n’est pas envisageable car les règles du jeu imose de jouer un mot existant dans la langue du mot à trouver

  5. Bonjour David,

    Où est passé le billet de blog (et peut-être la vidéo, je ne suis plus sûr) intitulé « Les études statistiques sont-elles hors de contrôle » ? J’ai voulu en parler à des proches mais j’ai l’impression qu’il y a eu « rétractation » sans le dire ?

    Merci beaucoup

  6. Intéressant, comme toujours, merci.

    Une remarque à propos du jeu consistant à chercher un entier entre 0 et 127 (sans parler du fait que de 0 à 127 il y a 128 possibilités, et qu’il faudra donc choisir 63 ou 64 à défaut de pouvoir prendre 63,5).

    Taper au milieu permet de réduire la liste des suspects de 50% environ… si le nombre est choisi de manière aléatoire.

    Si c’est un humain qui fait le choix, il va pouvoir intégrer des stratégies, et tenter un 70 ou un 126 en se disant que notre humain chercheur, qu’il a surpris en train de regarder ce blog, risque de taper très (trop) rationnellement au milieu. Sans parler du fait que celui qui cherche à deviner sait que celui qui a fait le choix de départ savait qu’il savait que….. bref, vous avez compris, le facteur humain change à mon sens la donne.

    C’est comme papier caillou ciseau. Joué par deux ordinateurs face à face c’est du hasard, joué par des humains un peu moins à en croire certaines statistiques et stratégies « psychologiques » (du genre : un ordinateur à une chance sur trois de jouer le même coup après quel que soit son coup précédent et quel que soit le choix fait en face et l’issue sortante bonne ou mauvaise du coup précédent, c’est moins vrai pour un humain).

    Transposé à Motus/Worlde, à voir si le mot du jour est déterminé par le hasard dans une liste avec tous les mots possibles dans la langue retenue, ou si un humain fait un choix pour le mot du jour (avec ou sans stratégies visant à perturber celles et ceux qui ont les bonnes stratégies théoriquement optimales…. ou à choisir des mots rigolos).

  7. Pourquoi la liste de mots de 5 lettres que tu mets sur GitHub contient plusieurs fois certains mots ?

    • J’ai récupéré la liste du site lexique, puis j’ai mis en capitales et remplacé les lettres accentuées, caractères spéciaux, etc. Ca a peut-être créé des doublons (par exemple « mangé » et « mange » deviennent « MANGE »). Mais je les élimine dans mon code au chargement.

  8. Matthieu FRYS Reply

    Merci pour cette vidéo c’est interessant de le voir d’un point de vue proba et scientifique.
    Par contre je suis étonné dans le code et la reflexion il ne cherche la meilleure combinaison que en prenant en compte la réponse précédente.
    Il ne pend pas en compte lors de la recherche du 3eme mot de la première réponse.
    Il ne serait pas amnésique ? 😀

  9. Bonjour, en prenant comme hypothèse:
    * mot choisi au hasard (pas d’histoire de mot plus courant) dans le dictionnaire de 2315 mots du wordle « officiel »
    existe-t-il un algo qui trouve à tous les coups (moins de 7) ?
    Par exemple, les mots (« shake » « shame » « shade » « share » « shape » « shale » « shave ») me semblent poser problème…

  10. Bonjour David,

    Aurriez-vous le meilleur mot d’entrée pour 6 et 7 lettres?

    Félicitation pour vos vidéos toujours trés instructives !

    Bàv

  11. Bonjour,

    Je sais que cela ne se fait pas de demander une vidéo spécifique et que ce n’est pas très poli, mais avec toute l’humilité que je puis formuler, pourriez-vous faire …

    … une vidéo sur DeepMind qui aide les physiciens à contrôler le plasma dans les tokamaks ?

    En effet, la fusion nucléaire est un de mes sujets scientifiques favoris, et cela s’ancrerait bien dans la série de vidéos sur cette chaîne Youtube sur les applications du machine learning (Jeu de go, reconnaissance des images, repliage des protéines, reconnaissance vocale etc.).

    Et puis qui sait, des progrès fulgurants en fusion nucléaire pourraient, peut-être, être une solution à nos problèmes écologiques ?

    Bravo encore pour l’ensemble de votre travail.

  12. Et le jeu « Glyph », colabellisé Max-Planck Inst. & CNRS, car opération de science collaborative sous forme d’un (super) jeu ? Je l’ai découvert grâce à Bénédicte Coudière (entre autre géniale autrice de SF), grand merci à elle, sur son Twitch cette semaine (session en replay, voir la fin), où l’on a découvert 3 « nouvelles » règles \o/, apparemment un « gros coup ». Ça fait penser à de la topologie « descriptive par l’exemple », Et j’ai encore des idées que j’espère innovantes (Kdo : inspirées de la théorie des n… 🙂 ), mais pas le temps, on verra la semaine prochaine, si qlq1 ne les a pas déjà eues, avant, ou d’ici là :-))).

  13. A un moment dans la video, tu décides de « passer les détails » du calcul de l’entropie. Peux-tu expliciter pouquoi on cherche à maximiser -log(x)/log(2) ? Pourquoi ne choisirait-on pas de maximiser 1/x2 ou 1/x3 ?

    (Note: naturellement, on a envie de dire que minimiser x, reviend à maximiser 1/x, mais comme 1/x à une probabilité x, en moyenne, ça voudrait dire que tous les coups se valent)

  14. Frank Wolff Reply

    Selon wikipédia l’objectif du jeu n’est pas de trouver le mot avec « le moins d’essais possible » mais en un maximum de 6 essais. Avez-vous la preuve que votre algorithme garantit cela ?

Write A Comment

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.