aboutsummaryrefslogtreecommitdiff
path: root/content/Informatique
diff options
context:
space:
mode:
Diffstat (limited to 'content/Informatique')
-rw-r--r--content/Informatique/2022-01-wordle.rst120
1 files changed, 120 insertions, 0 deletions
diff --git a/content/Informatique/2022-01-wordle.rst b/content/Informatique/2022-01-wordle.rst
new file mode 100644
index 0000000..c9260f6
--- /dev/null
+++ b/content/Informatique/2022-01-wordle.rst
@@ -0,0 +1,120 @@
+.. -*- mode: rst -*-
+.. -*- coding: utf-8 -*-
+
+===================================
+Une aide de jeu pour Wordle / Sutom
+===================================
+
+:date: 2022-02-01
+:tags: javascript
+:summary:
+ Les jeux de lettres sont un bon moyen d’occuper ses méninges. On peut aussi
+ se poser la question de savoir comment optimiser les réponses, et prendre le
+ temps de s’aider de l’informatique pour gagner à tous les coups !
+
+ Je suis parti du jeu Wordle, pour écrire une application autonome qui va
+ chercher à proposer à chaque coup le mot le plus intéressant.
+
+
+
+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.
+
+.. _Wordle: https://www.powerlanguage.co.uk/wordle/
+.. _article: https://www.francetvinfo.fr/replay-radio/l-etoile-du-jour/wordle-le-jeu-inspire-de-motus-qui-cartonne-sur-internet-au-grand-dam-de-son-createur_4898487.html
+.. _sutom: https://sutom.nocle.fr/
+
+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 :
+
+.. image:: {static}/images/motus/french_5.svg
+ :alt: Distribution des lettres dans les mots de 5 lettres
+ :align: center
+
+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_.
+
+.. _raise: https://fr.wiktionary.org/wiki/raise
+
+.. image:: {static}/images/motus/decision.gv.svg
+ :alt: Distribution des lettres dans les mots de 5 lettres
+ :align: center
+ :width: 75%
+
+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.
+
+.. _Claude Shannon: https://fr.wikipedia.org/wiki/Claude_Shannon
+.. _un mot de passe est faible ou non: https://fr.wikipedia.org/wiki/Robustesse_d%27un_mot_de_passe
+.. _gain d’entropie: https://fr.wikipedia.org/wiki/Entropie_de_Shannon
+
+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_ :
+
+.. __: {filename}/pages/motus/motus.rst
+
+.. class::
+ :center:
+
+ .. line-block::
+
+ 🟥🟦🟦🟡🟡🟡🟦
+ 🟥🟥🟥🟥🟥🟥🟥
+
+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.
+
+.. _arbres de décision: https://fr.wikipedia.org/wiki/Arbre_de_d%C3%A9cision
+
+Si vous souhaitez quelque chose de plus *manuel* cet article vous expliquera
+`comment jouer avec un terminal et grep`__ !
+
+.. __: https://opensource.com/article/22/1/word-game-linux-command-line
+