Joe Seager / Public domain (source)31 juillet 2020
Joe Seager / Public domain (source)
Note : Cet article est largement inspiré de la vidéo hangman is a weird game par jan Misali. Il en constitue une synthèse ainsi qu'un complément spécifiquement d'un point de vue francophone. Sur sa chaîne YouTube l'auteur s'intéresse essentiellement à l'analyse des langues construites (dont le plus fameux représentant est l'Esperanto) mais se livre également à des essais très intéressants sur des sujets très divers n'ayant pas forcément trait à la linguistique.
Nous allons aujourd'hui nous intéresser au jeu du pendu, divertissement de salle de classe dont l'origine remonte à l'aube du commencement de la génèse de l'humanité (à la louche). Nous allons nous pencher sur l'analyse de ce jeu simple d'apparence, déconstruire sa mécanique, en chercher une stratégie gagnante et voir comment il serait possible de l'améliorer.
Comme dans une bonne dissertation de philosophie, commençons par définir les mots importants composant notre problématique. Le pendu est un jeu se pratiquant avec un crayon et une feuille de papier faisant s'affronter deux joueurs. Le premier joueur va chercher à faire deviner au second joueur un mot ou une locution. Il va pour cela disposer sur la feuille autant de traits qu'il n'y a de lettres dans l'expression à retrouver. Le joueur-chercheur va alors proposer séquentiellement des lettres, le maître du jeu répondant à chaque proposition soit en disposant la lettre proposée à son ou ses emplacements dans l'expression cible, soit en dessinant les traits formant l'illustration d'un homme pendu, d'où le nom du jeu. La partie s'arrête soit quand le mot a été trouvé, soit quand le dessin du supplicié est terminé.
À noter qu'il est commun d'assimiler les lettres adjointes de signes diacritiques à leurs cousines nues. Ainsi si le joueur propose E, le maître du jeu ne manquera pas de révéler également le cas échéant les variations É, È, Ê et Ë.
Il existe de nombreuses variantes sur le détail des traits composant la potence. Tandis que certains se limiteront à dessiner la personne pendue, considérant les bois de justice comme hors du cadre du jeu, d'autres prendront plaisir à multiplier les détails, allant jusqu'à dessiner individuellement chacun des doigts du condamné pour repousser la fin de la partie et aider leur camarade de jeu à la peine.
Exemple type d'un pendu complet en 11 traits
Une première remarque que l'on peut faire est que le jeu se nomme hangman en anglais (le bourreau, littéralement « l'homme qui pend »), en contradiction avec son adaptation française qui se met du côté du malheureux. Ces deux appellations peuvent être coïncidées avec les deux rôles occupés par les joueurs. Le maître du jeu exécute tandis que le joueur-chercheur voit sa fin approcher : il est le pendu. Le pendu n'est alors plus une tierce personne servant d'enjeu (« si tu échoues, il va mourir ») mais le joueur lui-même (« si tu échoues, tu vas mourir). Analyse qui interrogera d'autant plus que le jeu se veut à destination des enfants.
En dehors de ces considérations métaphysiques, on notera que le pendu n'est qu'un prétexte pour compter les points et n'intervient pas dans le fond du jeu. On pourrait tout autant compter les points en traçant des traits verticaux à la suite comme un jour d'élection et déterminer une limite arbitraire. À la pétanque le gagnant est le premier à treize points, pas le premier qui a fini son dessin. En cela, le pendu est fidèle à la tradition des jeux sur papier dont le nom n'a aucun rapport avec leur teneur, en bonne place entre le morpion et le cadavre exquis, tournant le dos à des activités plus terre à terre au nom plus explicite comme les fléchettes ou le lancer du poids.
L'asymétrie des rôles dans le jeu du pendu implique deux approches bien distinctes du jeu. En effet, le maître du jeu cherchera à choisir le meilleur mot cible, tandis que le joueur-chercheur devra faire preuve de discernement dans ses propositions de lettres. Plaçons-nous d'abord à la place de ce dernier.
Une stratégie usuelle pour le joueur qui cherche est de d'abord proposer les lettres les plus fréquentes en français, bien connues des cryptanalystes amateurs. Il proposera ainsi plus ou moins dans l'ordre les lettres E, A, S, I, N, R, T… avant de continuer plus ou moins à l'aveugle selon la chance qu'il a eu jusque là. Cette technique, parfaitement sensée, a cependant quelques défauts. D'abord, sur un corpus aussi court qu'un mot (voire une phrase), il est courant que l'analyse des fréquences d'apparition des lettres diffère grandement de ce qui a été observé en général. Ensuite et surtout, cette méthode a le défaut d'ignorer une indication d'importance : le mot en lui-même et les progrès faits. Savoir que la cible est constituée de dix lettres et finit par un N (par exemple) est une information d'importance et il serait bien sot de s'en passer. De même, savoir qu'une lettre ne fait pas partie du mot final est également à prendre en considération.
Une stratégie optimale au pendu serait donc, pour chaque étape : 1. Lister l'ensemble des mots encore possibles, sachant la longueur du mot-cible, les lettres qu'il contient et celles qu'il ne contient pas. 2. Parmi ces mots, repérer la lettre qui apparaît dans le plus de mots différents. 3. Proposer cette lettre. 4. Recommencer.
Testons cette stratégie et mettons là en concurrence avec d'autres approches, l'approche « aléatoire » (je dis des lettres au hasard) et l'approche « fréquentielle » (je dis les lettres les plus fréquentes dans l'absolu en premier). Dans le cadre de cette enquête, j'ai mis la main sur une liste de mots en français à partir de la base Lexique. À partir des 142 695 lignes qu'elle contient, j'ai opéré plusieurs traitements pour me simplifier la tâche et ne garder que des mots bien lisses : 1. J'ai retiré les doublons (trois lignes pour « a » c'est trop) 2. J'ai retiré les mots contenant des espaces, tirets et apostrophes (désolé « aujourd'hui », « entr'acte » et « rythm'n'blues ») 3. J'ai retiré les accents, trémas et cédilles des lettres qui en étaient munies 4. J'ai retiré les nouveaux doublons
Reste tout de même à la fin 105 571 mots, ce qui est plutôt honnête.
Je me suis donc armé de Python, mon allié de toujours, pour implémenter les stratégies décrites plus haut. Dans le détail, il s'est agi de sélectionner un grand nombre de mots au hasard et de les soumettre aux trois différents algorithmes. On en tire quelques statistiques sur le nombre d'erreurs commises, ci-dessous exposées, avec un échantillon de 1000 mots issus du corpus.
| Grandeurs | Stratégie aléatoire | Stratégie fréquentielle | Stratégie analytique | |-----------|---------------------|-------------------------|----------------------| | Moyenne | 16,46 | 8,89 | 1,52 | | Médiane | 17 | 9 | 1 | | Meilleur score | 0 | 0 | 0 | | Pire score | 24 | 22 | 13 |
La supériorité de notre stratégie d'analyse systématique de tous les mots possibles apparaît ici démontrée. Elle est très efficace et ne produit que très peu d'erreurs (moyenne à 1,52). Un défaut tout de même, il est peu probable que votre camarade de jeu vous permette de vous équiper d'un ordinateur lors de votre pendu-party du samedi soir et d'y faire tourner vos scripts maison. Il risque de se sentir floué.
À présent, après avoir aidé le joueur-chercheur à trouver la meilleure stratégie pour gagner, cherchons cette fois ci quel pourrait être le mot ultime pour optimiser les chances de victoire du maître du jeu. À quoi peut ressembler ce mot ? Quand vous jouez avec votre petit cousin au pendu, il est courant que ce dernier tente de vous avoir avec « anticonstitutionnellement ». Parce que tout le monde apprend assez jeune que « anticonstitutionnellement » est le plus long mot de la langue française (ce qui n'est pas loin d'être vrai tant qu'on se cantonne aux mots du vocabulaire commun et qu'on ignore par exemple les noms de molécule en chimie ; à noter qu'« intergouvernementalisation » est plus long également, d'une lettre). Sauf qu'à partir du moment où il commence à aligner sa vingtaine de traits d'un air machiavélique, vous savez qu'il essaie de vous embrouiller avec « anticonstitutionnellement » et vous n'avez plus qu'à lui faire avaler le goût de la défaite. Comme si vous n'aviez déjà vous-même par le passé tenté de la faire à l'envers à votre grand cousin.
Les mots longs sont donc à proscrire, d'autant plus qu'ils sont rares. Par ailleurs, plus un mot est long, plus il contient de lettres différentes, plus vous avez de chances de tomber juste en disant une lettre au hasard. Voyez d'ailleurs ci-dessous les mots de notre corpus répartis par longueur. Le mot le plus long est el famoso « anticonstitutionnellement », suivi de près par « électroencéphalographie ».
J'ai laissé tomber matplotlib, j'ai utilisé LibreOffice Calc ce coup ci (l'Excel du pauvre)
Penchons-nous de nouveau sur notre analyse statistique. Il apparaît que notre stratégie présentée comme optimale n'est pas imparable et qu'elle échoue parfois à trouver la solution en un nombre d'étapes raisonnables. En effet, on voit que dans le pire des cas l'algorithme a dû se tromper treize fois avant de venir à bout de l'énigme.
Mais quel est alors ce vocable du démon qui est parvenu à faire choir notre champion ? Eh bien c'est « o ». La lettre O. Comme dans « Ô toi que j’eusse aimée, ô toi qui le savais ! » de Baudelaire (ou « Ô Panoramix notre druide », selon vos références littéraires). Les autres mots récalcitrants sont « pope » (un prêtre orthodoxe), « ra » (« coup de baguettes frappé sur le tambour pour produire un roulement très bref », source TLFi) et « yack » (un animal, enfin ça vous devriez connaître).
Alors c'est ça la solution ? Jouer « o » ? Inutile de vous prévenir que votre petit cousin risque de vous faire la gueule si vous lui faites un coup comme ça. Pareil pour « ra ».
Pourquoi il va vous faire la gueule votre cousin ? Parce qu'il va vous accuser de tricherie et d'avoir juste choisi une lettre au pif au dernier moment qu'il n'avait pas encore proposé. Ce qui est une accusation qui se tient. Mais nous venons là de mettre le doigt sur un point d'importance : la possibilité de tricher au pendu. En effet, il ne vient à l'idée de personne de demander au maître du jeu d'écrire à l'avance son mot dans une enveloppe scellée. On se fait confiance globalement. Sauf qu'il nous est possible d'exploiter cette faiblesse justement pour optimiser notre partie. L'idée : changer le mot final au fur et à mesure des propositions de l'autre joueur, de manière à ce qu'elles soient fausses.
Comment faire ? Soit vous gardez votre ordinateur sous le coude pour vous assurer qu'il y a toujours des mots disponibles (ce qui encore une fois risque de ne pas être du goût de votre partenaire de jeu que vous avez déjà échauffé plus tôt dans la soirée), soit vous apprenez par cœur les mots suivants :
Ce sont sept mots de quatre lettres qui n'ont aucune lettre en commun. Ainsi, à votre tour de jeu, vous pouvez tracer quatre traits et refuser systématiquement les six premières lettres qui vous seront proposées. À partir de là, vous pouvez adapter la suite pour orienter vers l'un ou l'autre des mots, ou continuer de refuser des lettres si c'est toujours possible. À noter que tous ces mots sont dans le dictionnaire officiel du Scrabble, même l'onomatopée chelou au début. En dehors de cette coquetterie, la liste est construite en réservant une voyelle pour chaque mot.
Pour votre information, les mots en anglais proposés dans sa vidéo par jan Misali sont :
Je n'ai pas trouvé de mots de six lettres ne contenant que le Y comme voyelle. En cinq lettres, mon corpus ne contient que « lynch » mais on en trouve que peu de références (voir le TLFi). Et même si on tolère cette incartade, il est difficile de constituer une liste à partir de ça (et pourtant j'ai essayé).
Le pendu a inspiré d'autres jeux, et même des émissions de télévision. La plus connue est La Roue de la fortune, où les joueurs doivent tour à tour deviner les lettres constituant un mot ou une phrase. La principale différence avec la version papier est que les joueurs ne peuvent proposer que des consonnes et doivent « acheter » les voyelles à partir de leur cagnotte personnelle. Si on considère que les voyelles sont les lettres les plus communes en français (et en anglais, et dans la plupart des langues usant de l'alphabet latin), ça paraît une initiative intéressante. D'autant plus que la plupart des énigmes à trouver sont constituées de plusieurs mots dont parfois des noms propres, il paraît difficile d'établir une stratégie efficace autrement qu'en se contentant de s'appuyer sur la fréquence des lettres en français. Mais il y a fort à parier que les concepteurs du jeu prennent déjà ce paramètre en compte.
Une analyse sur le temps long des mots à trouver à La Roue de la fortune pourrait être intéressante. Aux États-Unis des études ont été faites sur leur version nationale du jeu, Wheel of Fortune. On en trouve une synthèse ici, sur la base de données brutes trouvables ici. Ils sont forts ces américains.
Une autre variante du pendu, bien connue de ce côté de l'Atlantique, est Motus. On s'éloigne ici un peu plus du concept original puisque les joueurs ne doivent plus proposer des lettres mais des mots entiers. À chaque essais, ils sont informés pour chaque lettre du mot proposé si elle est à la bonne place, si elle n'est pas à la bonne place, ou si elle est carrément absente du mot final. La mécanique du jeu n'est ici pas sans rappeler celle du jeu de société Mastermind, où un joueur dispose de manière dissimulée une combinaison ordonnée de quatre couleurs, et où l'autre joueur doit la retrouver en faisant des propositions de combinaisons. Comme à Motus, le maître du jeu indique ensuite le statut des pions de la combinaison, sans toutefois préciser lesquels sont présents, lesquels sont mal placés, etc.
Pour en finir enfin, sachez que j'avais réalisé dans mes jeunes années un jeu de Mastermind en C, avec une interface graphique, dont le code source est trouvable ici. Le jeu était doté d'un assistant (ne parlons pas d'intelligence artificielle, ce serait faire injure à l'intelligence des lecteurs) qui était capable de suggérer au joueur un coup à jouer, correct au regard des combinaisons déjà jouées et des retours obtenus. Le coup n'était pas forcément optimal, le programme se contentant de tirer au hasard une combinaison parmi celles encore possibles. Toujours est-il qu'en dépit de cet algorithme a priori très naïf, la solution était quasi-systématiquement trouvée en moins de six essais sur les dix possibles.
Certes, sûrement aurait-il été possible d'optimiser l'ensemble en choisissant une combinaison susceptible de fournir les renseignements les plus précis possibles et retirant le plus de combinaisons possibles à chaque fois. Disons que cette partie est laissée en exercice au lecteur. Et qui sait, peut-être j'en ferai un article un jour (ceci n'est pas une promesse).
Pour conclure enfin ce long laïus, nous avons vu qu'il était possible pour un joueur-chercheur d'optimiser son comportement de jeu au pendu, mais que l'algorithme était difficile à appliquer de tête sans assistance d'un programme dédié.
Par ailleurs, un maître du jeu qui cherchera à piéger son partenaire privilégiera les mots très courts, avec idéalement peu de lettres différentes et un peu exotiques (K, W, ce genre de choses). « Yack », « jazz » ou « vue » constituent des bons exemples. Prenez garde toutefois, des mots courts sont susceptibles de susciter l'ire des autres joueurs, d'autant plus s'ils perdent. Par ailleurs, si les questions d'éthique ne sont pas de nature à vous embarasser, la tricherie reste une option ouverte.
