Le pendu et l’intelligence artificielle : comment un algorithme devine vos mots
Le jeu du pendu semble si simple qu’on pourrait croire qu’il n’intéresse pas les chercheurs en intelligence artificielle. Après tout, il s’agit « juste » de deviner un mot lettre par lettre. Pourtant, derrière cette simplicité apparente se cache un problème algorithmique riche et subtil. Construire une IA capable de jouer au pendu de manière optimale mobilise des concepts avancés de théorie de l’information, d’apprentissage automatique et de linguistique computationnelle. Plongeons dans les mécanismes qui permettent à une machine de deviner vos mots avec une efficacité déconcertante.
Le problème vu par une machine
Pour un humain, le pendu est un jeu d’intuition linguistique. On « sent » que le E est fréquent, que le W est rare, que les mots français commencent souvent par C ou P. Pour une machine, le problème se formule différemment : à chaque étape, l’algorithme dispose d’un état partiel (les lettres déjà révélées, leur position, et les lettres essayées sans succès) et doit choisir la prochaine lettre à proposer pour maximiser ses chances de trouver le mot en un minimum de tentatives.
Ce problème appartient à la catégorie des problèmes de décision séquentielle sous incertitude, un domaine au cœur de la recherche en IA moderne.
Niveau 1 : l’approche fréquentielle
L’algorithme le plus basique pour jouer au pendu consiste à classer les lettres par fréquence dans la langue française et à les essayer dans cet ordre : E, A, S, I, N, R, T, O, L, U, etc. Cette approche naïve fonctionne étonnamment bien : elle permet de deviner correctement environ 55 % des mots du dictionnaire français en moins de 6 erreurs.
Mais ses limites sont flagrantes. Cet algorithme ne tient pas compte du contexte : une fois que l’on sait que le mot fait 3 lettres et commence par Q, proposer le E en premier n’a plus aucun sens - la quasi-totalité des mots de 3 lettres commençant par Q sont de la forme QU_. Un algorithme intelligent devrait adapter ses choix en fonction de l’information déjà obtenue.
Niveau 2 : le filtrage par dictionnaire
L’approche suivante consiste à charger un dictionnaire complet en mémoire et, à chaque étape, à filtrer les mots compatibles avec l’état actuel de la partie. Si le mot fait 7 lettres, que la troisième est un A et que le E a été exclu, l’algorithme ne conserve que les mots de 7 lettres ayant un A en troisième position et ne contenant pas de E.
Parmi les mots restants, l’algorithme calcule la fréquence de chaque lettre non encore essayée et choisit celle qui apparaît dans le plus grand nombre de mots candidats. L’idée est que cette lettre a la plus forte probabilité d’être présente dans le mot mystère, réduisant ainsi au maximum l’espace de recherche.
Ce filtrage dynamique fait bondir le taux de réussite à environ 80 %. C’est une amélioration spectaculaire, obtenue sans aucune technique d’IA sophistiquée - juste du bon sens algorithmique appliqué systématiquement.
Niveau 3 : la théorie de l’information
Le véritable saut qualitatif survient lorsqu’on applique la théorie de l’information au choix des lettres. Plutôt que de choisir la lettre la plus fréquente parmi les mots candidats, l’algorithme choisit celle qui maximise l’entropie - c’est-à-dire celle dont la réponse (présente ou absente, et si présente, à quelles positions) apporte le plus d’information.
La distinction est subtile mais cruciale. Imaginons que parmi 100 mots candidats, la lettre R apparaît dans 90 mots et la lettre T dans 50 mots. L’approche fréquentielle choisirait R. Mais si R apparaît toujours à la même position dans les 90 mots, la réponse « R est présent » n’élimine que 10 candidats. En revanche, si T apparaît à des positions variées, la réponse à « T » peut diviser les 100 candidats en groupes beaucoup plus petits, accélérant considérablement la convergence.
Avec cette approche, le taux de réussite dépasse 90 %, et la plupart des mots sont trouvés en 4 à 5 erreurs maximum. On retrouve ce même principe d’optimisation de l’information dans d’autres jeux de déduction, comme l’algorithme optimal du Mastermind, où chaque proposition vise également à maximiser l’information obtenue.
Niveau 4 : l’apprentissage automatique
Les approches précédentes supposent l’accès à un dictionnaire exhaustif. Mais que se passe-t-il si le mot mystère n’est pas dans le dictionnaire de l’IA ? C’est là que l’apprentissage automatique entre en jeu.
Les réseaux de neurones récurrents (RNN) et les transformers peuvent apprendre les patterns statistiques de la langue française sans avoir besoin d’un dictionnaire explicite. En s’entraînant sur des millions de mots, ces modèles développent une compréhension implicite des bigrammes (paires de lettres fréquentes comme QU, CH, OU), des trigrammes (ENT, ION, AIT) et des structures morphologiques (préfixes, suffixes, radicaux).
Un réseau de neurones entraîné au pendu apprend par exemple que si le mot se termine par « -TION », la lettre précédente est probablement un A, un I ou un U. Il apprend aussi que les mots de 4 lettres commençant par « PH- » sont très rares en français, et que « -MENT » est un suffixe extrêmement courant pour les mots longs. Ces connaissances implicites lui permettent de deviner des mots qu’il n’a jamais vus pendant l’entraînement.
Le défi des mots piégés
Même les IA les plus performantes ont leur talon d’Achille : les mots pièges. Les mots empruntés à d’autres langues (WHISKY, FJORD, BUZZ), les mots techniques (QUARTZ, LYNX) et les mots à structure inhabituelle (OXYGÈNE, avec son Y entre deux voyelles) mettent les algorithmes en difficulté.
Face à ces mots, l’IA se comporte comme un humain dérouté : elle épuise les lettres fréquentes sans résultat, puis doit se rabattre sur des lettres rares en espérant tomber juste. C’est précisément pour ces cas limites que les techniques d’apprentissage profond montrent leur supériorité : un modèle ayant intégré des patterns multilingues pourra « deviner » qu’un mot commençant par WH est probablement d’origine anglaise et adapter sa stratégie en conséquence.
L’arbre de décision : planifier plusieurs coups à l’avance
Les algorithmes les plus sophistiqués ne se contentent pas de choisir la meilleure lettre immédiate : ils planifient plusieurs coups à l’avance. En construisant un arbre de décision complet, l’algorithme explore toutes les séquences possibles de lettres et leurs réponses, jusqu’à trouver la stratégie qui minimise le nombre maximum d’erreurs dans le pire cas.
Cette approche, appelée minimax dans la théorie des jeux, est la même que celle utilisée par les IA jouant à Othello ou aux échecs. La différence est que l’adversaire au pendu n’est pas un joueur rationnel mais la langue elle-même, avec ses régularités et ses exceptions.
Le coût computationnel de cette approche est énorme : pour un dictionnaire de 100 000 mots avec 26 lettres possibles, l’arbre de décision complet contient des millions de nœuds. Des techniques d’élagage permettent de réduire cette complexité, mais le calcul reste intensif. C’est pourquoi les implémentations pratiques combinent généralement un arbre de décision partiel (2-3 coups à l’avance) avec une heuristique basée sur l’entropie pour les niveaux plus profonds.
Ce que l’IA nous apprend sur notre propre jeu
Étudier les algorithmes de pendu révèle à quel point notre intuition linguistique est à la fois remarquable et limitée. Les humains excellent à reconnaître les patterns familiers : un cruciverbiste expérimenté devine souvent le mot après seulement 2-3 lettres révélées, grâce à une mémoire lexicale construite sur des décennies de lecture. Mais nous sommes sujets à des biais cognitifs que l’IA évite : nous suresimons la fréquence des lettres rares mais mémorables (Z, X), nous oublions de considérer systématiquement toutes les positions possibles, et nous nous fixons parfois sur un mot candidat en ignorant les alternatives.
La leçon pratique ? Avant de proposer une lettre au pendu, posez-vous la question que se poserait un algorithme : « Parmi tous les mots encore possibles, quelle lettre apparaît dans le plus grand nombre d’entre eux, aux positions les plus variées ? » Cette approche systématique ne remplacera jamais complètement l’intuition, mais elle peut considérablement améliorer votre taux de réussite sur les mots difficiles.
En définitive, le pendu est bien plus qu’un divertissement innocent gribouillé sur un coin de cahier. C’est un laboratoire miniature où se rencontrent linguistique, théorie de l’information et intelligence artificielle. Et la prochaine fois qu’un ami vous défiera au pendu, vous saurez que derrière chaque lettre proposée se cache un univers algorithmique d’une richesse insoupçonnée.
