Un pendu en python

Publié le 6 mai 20199 mai 2019 par Herve Kabla

À la recherche d’exercices relativement simples pour l’apprentissage de la programmation, je me suis lancé avec un de mes enfants à développer un jeu du pendu. C’est un jeu assez classique, auquel nous avons tous joué un jour, et qui consiste à deviner toutes les lettres d’un mot caché par son adversaire, en faisant moins de x erreurs, x étant un nombre fixé à l’avance et correspondant au nombre de traits nécessaires pour dessiner un pendu sur l’échafaud (typiquement x=10).

L’exercice en lui-même n’a rien de très compliqué, et peut être envisagé sous deux versions. Il ne nécessite que des manipulations de listes, et un peu de logique. Le tout tient en 300 lignes.

Le premier exercice, c’est lorsque l’ordinateur cache le mot, et que le joueur humain doit le deviner. Il s’agit donc essentiellement de choisir un mot au hasard, de vérifier que les lettres proposées par le joueur apparaissent ou non dans le mot caché, et de compter le nombre d’erreurs commises. Arrivé à x erreurs, on déclare que le joueur a perdu. Pas trop dur à programmer.

La seconde version, c’est quand le joueur humain choisit un mot, et que l’ordinateur doit le deviner. La stratégie la plus simple et la plus efficace me semble-t-il, consiste à proposer, à chaque fois, la lettre la plus fréquente dans l’ensemble des mots encore possibles. On part d’un dictionnaire initial (je suis parti d’un dictionnaire disponible en ligne, et qui propose près de 300 000 termes français (récupéré sur le site d’un X87, Christophe Pallier), en autorisant les formes des verbes conjuguées). On commence par proposer la lettre la plus fréquente: il s’agit du ‘E’. S’il est présent, le programme demande à quelle(s) position(s) apparaît cette lettre, et filtre le dictionnaire initial, en ne gardant que les mots qui possède la lettre ‘E’ correctement placé. S’il n’est pas présent, on filtre le dictionnaire en ne gardant que les mots qui ne contiennent pas de ‘E’. Puis on cherche la lettre la plus fréquente dans l’ensemble de mots obtenu par filtrage, en prenant soin de ne pas compter les occurrences des lettres déjà utilisées. Et on recommence.

Cette technique permet d’assez rapidement converger vers la bonne solution, en moins de 10 coups. Cela pourrait paraître étonnant à première vue, mais c’est avec de petits mots de trois lettres qu’il a le plus de difficulté: DIX ou FEZ sont des mots qu’il trouve en 9 ou 10 coups juste. La raison en est que les lettres utilisées sont assez peu fréquentes (le X et le Z) et qu’il essaie de passer en revue les lettres les plus usuelles (N, T, S) en premier, après avoir trouvé la voyelle centrale. Les mots plus longs sont découverts assez rapidement, car le filtre sur les lettres présentes réduit assez rapidement le nombre de mots possibles.

Bien sûr, on pourrait pousser le vice à le faire tourner pour vérifier le nombre de coups nécessaires pour tous les termes du dictionnaire, et rechercher ainsi les mots les plus difficiles. Ce sera pour un autre après-midi pluvieux…

En attendant, si vous devez jouer au pendu, dites-vous bien que la stratégie qui consiste à faire deviner un mot long n’est pas la bonne. C’est d’ailleurs ce qu’expliquait cet épisode du podcast Freakonomics…