J’ai entendu parler du jeu Wordle récemment, dans un article qui abordait le phénomène. Le jeu, consiste à deviner un mot, à l’aide d’indices sur le placement des lettres. J’ai depuis découvert qu’une version française existe également : sutom, et je vais continuer l’article sur la base des mots français.
Comme nous avons un nombre de coups limités, il nous faut trouver des propositions qui nous donnent le plus d’informations sur les coups suivants. On est d’accord pour dire que yoyos n’est pas le meilleur coup à jouer : déjà il ne contient que trois lettres différentes, c’est pas top, en plus, il y a de forte chance que le y soit déclaré comme absent, ce qui ne nous donne pas beaucoup d’information pour la suite.
Mais si l’on est capable de déterminer qu’un mot n’est pas le plus pertinent, est-ce qu’il est possible de trouver le meilleur mot possible ? Celui qui nous donne le maximum d’information ?
Si l’on regarde la distribution des lettres parmi les mots de cinq lettres, on se rend compte que certaines lettres sont à privilégier parmi d’autres :
Partant du principe que l’on ne connait pas le mot à trouver, si l’on choisit un mot contenant un A lors de notre première proposition, quel que soit le résultat, valide ou non, on élimine d’emblée la moitié des mots possibles. Dans l’ordre, les lettres les plus intéressantes pour proposer un premier mot sont les suivantes : { a, e, s, i, r }. Nous pouvons donc proposer siéra, serai ou raise.
En prenant seulement trois lettres (sur les cinq de la proposition), on se rend compte que même dans le pire des cas, on divise le nombre de mots par 5, en passant de 7470 mots à 1398 ! À chaque proposition, nous réduisons les mots possibles et la seconde proposition sera déjà plus précise. Comme la distribution des lettres va changer, nous allons pouvoir présenter une nouvelle proposition qui va de nouveau diviser le nombre de mots restants, et ainsi de suite jusqu’à arriver à une proposition unique : le résultat.
Note
J’ai utilisé ici les lettres qui identifiées au moment de la répartition générale sur l’ensemble des mots. Si l’on refait le calcul à chaque branche de l’arbre ci-dessus, nous allons obtenir une répartition finale plus équilibrée (mais qui nécessite un recalcul des fréquences à chaque fois).
S’il est possible de préparer des tables (ou de les apprendre !), il est plus efficace de laisser l’ordinateur calculer de lui-même quelle est la fréquence de chaque lettre, et donc de nous proposer le mot à chaque coup.
Si l’on comprend intuitivement comment choisir chaque lettre, on peut aller plus loin en cherchant comment calculer le mot contenant le plus d’information. C’est Claude Shannon qui a posé les bases de cette approche mathématique, et ses calculs sont encore utilisés aujourd’hui (par exemple pour identifier si un mot de passe est faible ou non). Je n’irai pas ici dans le détail du calcul du gain d’entropie, l’idée étant d’expliquer le mécanisme de manière simple.
J’ai mis en place une application en ligne qui fait ces calculs et permet de trouver le mot en quelques coups (parfois en deux coups !), exemple avec une partie de sutom :
Il n’y a pas de mécanisme d’apprentissage dans cette application, tout est statistiquement explicable et entièrement reproductible, pour autant le principe des arbres de décision est à la limite de l’intelligence artificielle de part l’aide qu’il apporte à l’analyse. On le voit ici, que ce soit en termes de temps de traitement, ou en nombre de propositions : il ne s’agit pas seulement d’évaluer toute une liste de propositions rapidement, mais également d’aiguiller la décision le plus rapidement possible.
Si vous souhaitez quelque chose de plus manuel cet article vous expliquera comment jouer avec un terminal et grep !