1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
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
|
