GitHub du projet : https://github.com/Romb38/autoCemantix

L’été touche à sa fin et je ne pouvais pas le terminer sans réaliser un petit projet et le pousser à bout. Cette fois, j’ai été inspiré par le jeu Cémantix que j’ai cherché à résoudre automatiquement.

C’est quoi Cémantix ?

Le principe du jeu Cémantix respose sur la base du jeu chaud/froid avec des mots. Chaque jour à minuit (heure française), le site choisit un mot mystère dans un dictionnaire et le joueur peut essayer de soumettre des mots. À chaque soumission, le site renvoie un score de ressemblance sémantique par rapport au mot mystère. Plus le mot est proche, plus le score est grand. Une fois le mot trouvé, le jeu s’arrête et on peut recommencer le lendemain.

À force de jouer à ce jeu, j’en suis venu à chercher une méthode optimale pour le résoudre, mais sans succès. J’ai alors implémenté un algorithme pour le résoudre à ma place.

Comment intéragir avec le jeu

Le jeu n’offre pas d’API ouverte, étudions alors le service. Un utilisateur normal interagit avec le jeu en entrant un mot dans la zone de texte prévue à cet effet. Ensuite, il obtient un score qui est affiché sur la page. Alors, en bon développeur, on ouvre la console et on regarde la requête envoyée lorsqu’on soumet un mot au site. La chance est de notre côté ! Elle est super simple :

# Headers fixes dont on se fiche une fois sauvegardé dans notre script
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:128.0) Gecko/20100101 Firefox/128.0
Content-Type: application/x-www-form-urlencoded
Origin: https://cemantix.certitudes.org
Host: cemantix.certitudes.org
Referer: https://cemantix.certitudes.org/

# Partie intéressante
POST https://cemantix.certitudes.org/score?n=1280
Data : word=test

En dehors des en-têtes inutiles (que j’ai rajoutés sinon la requête est refusée), on trouve une requête simple avec 2 paramètres :

  • Le numéro du puzzle du jour, dans notre cas 1280
  • Le mot à soumettre dans le body, dans notre cas test

En réponse à cette requête, on obtient les valeurs suivantes

{
  "s":0.0894, # Le score du mot soumis
  "v":809 # Le nombre de personnes ayant résolu le puzzle du jour
}

Super ! On a donc une partie simple de l’algorithme pour récupérer le score d’un mot.

# Les headers coresspondent à la partie fixe décrite plus haut

url = "https://cemantix.certitudes.org//score?n=1280"
resp = requests.post(url, headers=headers, data="word=test".encode("utf-8"), timeout=30)
resp.json()['s']

Il nous reste à trouver le numéro du puzzle du jour. Pour cela, un get simple de la page et un peu d’expression régulière et PAF, on obtient le numéro magique. En voici l’algorithme :

resp = requests.get("https://cemantix.certitudes.org/", headers=headers, timeout=30)
match = re.search(r'data-puzzle-number="(\d+)"', resp.text)
puzzle_number = int(match.group(1))

Gestion des erreurs de Cémantix

Quelques mots sur la gestion des erreurs : cette fois-ci encore, Cémantix est très gentil avec nous et nous propose une gestion simple des erreurs :

  • Si le site ne connais pas le mot, il renvoie {"e":"Je ne connais pas le mot <i>aaaaaa</i>."}
  • Si le numéro du puzzle ne coresspond pas, il renvoie {"r":true}. Je ne sais pas pourquoi exactement, mais cela nous facilite la gestion des erreurs

Donc, si lors de nos tests, la réponse donnée par le serveur contient un e ou r, on s’est planté quelque part.

Jouons !

Avec ces informations en place, on peut se lancer dans la résolution du jeu. Pour cela, on choisit un mot dans un dictionnaire de français au hasard et on le soumet. Et voilà, on peut jouer ! Mais je pense qu’on peut améliorer cela :

Le dictionnaire

Pour commencer, on va se concentrer sur le choix du dictionnaire. Pour cela, on à quelques pistes :

  • Le site de Cémantix mentionne la page de Jean-Philippe Fauconnier qui contient des modèles sémantiques. Ces modèles contiennent un grand nombre de mots et leurs ressemblances sémantiques les uns avec les autres.
  • À force de jouer, je me suis rendu compte que le site n’accepte pas les mots suivants :
    • Les pluriels
    • Les verbes conjugués
    • Les mots de 1 lettre
    • Les mots commençant par un caractère non alphanumérique
    • Les mots contenant un caractère alphanumérique différent de ‘-’

On va donc faire du filtrage ! Pour cela, j’ai récupéré ce lexique français (~ 140 000 mots) et je l’ai utilisé pour filtrer le plus petit modèle trouvable sur la page de Jean-Philippe Fauconnier (pesant 120mb et contenant ~155 000 mots). Les mots qui passent dans les filtres sont alors :

  • Les mots en commun entre le lexique français et le modèle
  • Les mots d’au moins 2 lettres
  • Les mots commençant par un caractère alphanumérique
  • Les mots ne contenant pas de caractère alphanumérique différent de ‘-’
  • Les mots dont la classe est “verbe”, “adverbe”, “nom”
  • Les mots dont la racine (donnée par le lexique) correspond au mot (pour empêcher les pluriels et les conjugaisons)

Grâce à ce filtre, on vient de diviser par 10 la taille du modèle avec environ 15 000 mots restant dans notre modèle de jeu. Il n’est pas parfait, mais nous le taillerons avec le temps.

Recherche du mot

Viens la partie intéressante de l’algorithme. Comment trouver un mot qui nous approche le plus possible de la solution ?

Au début, j’ai cherché en vain une manière de faire une boucle qui assurait mathématiquement un rapprochement minimal vers l’objectif, mais je n’ai rien obtenu de concluant. J’ai alors changé d’approche pour ajouter un laser.

Méthode beam : L’idée est la suivante :

  • On prend une liste de mots de départ, dans mon cas amour, travail, animal, maison, politique
  • Ensuite, on récupère leurs scores et on les place dans une pile (le laser) par ordre décroissant de score (le plus élevé en haut)

Vient maintenant la boucle principale :

  • On dépile le premier mot de la pile et on regarde les 20 voisins les plus proches qui n’ont pas été testés.
  • Pour chacun d’entre eux, on calcule leur score et on les remet dans la pile au bon endroit
  • On recommence jusqu’à trouver la solution

Cet algorithme permet une convergence rapide probable, car en mettant les mots avec le score le plus élevé en haut de la pile, on augmente avec une certaine probabilité le score petit à petit. La convergence lente est assurée, puisqu’on ne réutilise jamais les mots, donc on finira (au bout d’un certain temps) par utiliser tous les mots du dictionnaire.

Après quelques tests (sur plusieurs jours), on trouve le mot en ~450 essais, soit environ 4 minutes au rythme d'1 soumission toutes les 0,5 seconde.

Apportons des améliorations !

Maintenant que nous avons un algorithme qui tourne correctement, il est temps de lui apporter des améliorations !

Ntfy

J’avoue, cette amélioration ne sert à rien, mais elle est appréciable. Ce script tournant sur mon serveur à 3 h 00 du matin, je souhaitais avoir la confirmation qu’il a tourné et obtenir la réponse du jour. Pour cela, j’ai utilisé une instance de ntfy, un service permettant d’envoyer facilement des notifications push sur mobile, afin de m’envoyer la réponse du jour, le nombre de requêtes réalisées et le temps de résolution.

Retrait des mots invalides

Chaque jour, nous testons des dizaines de mots et certains d’entre eux ne sont pas valides pour Cémantix. Il ne sert alors à rien de les garder ! Ainsi, chaque jour, les mots invalides sont retirés du modèle et sont stockés dans un fichier pickle, un format permettant de stocker des objets sérialisés en binaires. Ce fichier pickle existe pour permettre de filtrer à nouveau un dictionnaire si jamais le besoin s’en faisait sentir et il est disponible sur le répertoire du projet.

Et si on piochait aléatoirement ?

Une possibilité, soumise par des amis, d’améliorer ce script est de lui permettre une certaine liberté. Pour cela, nous pouvons ajouter un peu d’aléatoire à deux endroits différents :

  • Au début du script, pourquoi ne pas laisser l’algorithme piocher un certain nombre de mots aléatoirement et les ajouter à la pile ? On pourrait ainsi tomber sur un bon score !
  • Durant la boucle principale, on pourrait ajouter des mots aléatoires de temps à autre afin de permettre une extension plus grande des champs de recherche

Je n’ai pas testé cela encore, car j’attends encore quelques jours pour obtenir plus de statistiques sur les recherches pour réellement comparer l’approche sans aléatoire et avec aléatoire.

Partager !

Une dernière amélioration possible est de partager mon projet, ce que je fais actuellement :D. En effet, plus nous testons de mots, plus nous trouvons de mots invalides et plus nous pouvons vider le dictionnaire. Pour le moment, je me refuse de tester tous les mots du dictionnaire un par un, car j’ai le temps, mais si quelqu’un souhaite le réaliser, je serai curieux de voir à quel point nous pouvons descendre ce modèle.

Conclusion

Ce projet n’est clairement pas fini, et j’écris ces lignes à 5 h 00 du matin, dans la fièvre du développeur. J’espère vous en redonner des nouvelles assez vite, une fois les données obtenues !

Nouvelles tierces

Je profite de ces quelques lignes pour donner quelques nouvelles de l’univers numérique Standouda :

  1. J’ai résolu le problème d’IPv6 de mon serveur, après avoir remonté la chaine nginx (serveur) -> nginx (proxy) -> routeur -> DNS. Je me suis rendu compte que mon routeur bloquait lesdites requêtes. C’est corrigé !
  2. L’instance d’Overleaf de Standouda est officiellement réparée (et malheureusement restreinte pour limiter les compilations). Je l’ai réparé le jour où j’ai entendu parler de Typst qui me fait un peu de l’œil.
  3. Fail2Ban a été configuré correctement sur mon proxy, captant des demandes d’accès régulièrement !
  4. Je vis toujours sous le joug terrible de changer d’adresse IP, il faudra que je songe à mettre en place un DNS dynamique

En espérant vous revoir bientôt dans ce petit coin de web,

Au plaisir,

Romb38 - Standouda