TLDR : J'ai écrit un bot de résolution Wordle avec Javascript et UIlicious. Vous pouvez réexécuter ou modifier cet extrait à tout moment pour obtenir votre solution Wordle quotidienne. Essayez et voyez si vous pouvez obtenir un meilleur score que le bot ! N'hésitez pas à le modifier et à optimiser l'algorithme du solveur !
Divulgation complète : je suis le cofondateur et directeur technique de Uilicious.com (présenté dans cet article)
Le solveur wordler est couvert en 3 parties, qui couvre le
- Code d'interaction de l'interface utilisateur (lié ici)
- Modèle statistique Wordle et les mathématiques derrière (cet article)
- Tests unitaires et benchmarking du solveur wordle (@todo)
Tous les exemples statistiques peuvent être trouvés sur le lien suivant : https://uilicio.us/wordle-statistics-sample Et sont générés via le code utilisé ici : https://github.com/uilicious/wordle-solver-and-tester
Avertissement, je ne prétends pas que ce soit la meilleure stratégie WORDLE (encore), mais c'est plutôt une bonne =)
Avant d'entrer dans les statistiques, couvrons d'abord notre stratégie WORLDE.
Une chose que les humains font vraiment bien et que les ordinateurs classiques sont mauvais, c'est de comprendre "intuitivement" les choses. À moins que je n'envisage de former un réseau de neurones, le programme informatique que je développe devra utiliser une liste de mots de dictionnaire classique pour faire ses suppositions.
Cependant, la seule chose que les ordinateurs font bien est de mémoriser des listes géantes de mots ou de données. Et effectuer des calculs dessus. Alors utilisons cela à notre avantage en faisant la séquence suivante.
Étant donné la liste de 2 mots, une pleine de réponses possibles (~2,3k mots), et une autre avec la liste complète de mots (13k mots)...
Filtrez les mots dans la liste de réponses possibles par rapport à l'état actuel du jeu à partir des suppositions passées.
Comptez le nombre de fois que chaque caractère apparaît dans la liste des mots de réponse dans leurs positions de mot respectives.
Dans la liste complète des mots, choisissez le mot qui est le plus susceptible de trouver une supposition de caractère correcte. Marquez-le indépendamment en préférant les mots qui donnent plus d'informations dans les 4 premiers tours avec une correspondance exacte ou partielle.
Choisissez le mot le plus élevé et essayez-le.
Répétez à partir du haut si nécessaire.
Aussi pour clarifier: Nous ne mémorisons pas les solutions Wordle précédentes (j'ai senti que c'était de la triche car le système pouvait finir par mémoriser la liste au jour le jour en séquence).
Alors que les détails exacts du score changent légèrement en fonction du tour - pour optimiser les choses. Cela ne change pas le concept global à un niveau élevé.
Alors, comment cela fonctionne-t-il en pratique ? Pour notre itération actuelle de la stratégie Wordle, nous verrons cela dans la pratique étape par étape (sans code).
Un alias de sain, signifiant: faire le signe de la croix sur (soi-même) afin de bénir ou de protéger du mal ou du péché
Il y a eu beaucoup de conseils sur les 2 premiers mots. Et il est logique que ce mot suive :
Mais découvrons pourquoi le solveur choisit ce mot en regardant les nombres.
Basé sur les statistiques. "SAINE" a la plus grande chance de trouver une correspondance exacte de caractère vert comme mot d'ouverture tout en ayant 3 des voyelles supérieures.
La lecture du tableau de distribution brut peut être naturellement difficile à digérer. Alors permettez-moi de recontextualiser ces chiffres ici. SAINE a un…
Il y a de très fortes chances d'obtenir au moins un ou 2 indices majeurs. Inversement, parce qu'il y a peu de mots sans A, I et E, l'absence de correspondance est un "indice énorme".
Pas mal pour une ouverture hein ?
Qu'en est-il des autres mots d'ouverture populaires tels que "CRANE" et "ADEPT" ?
Le seul avantage clé, pour "CRANE / ADEPT", est qu'ils ont tous les deux 0,04% de chances de réussir à deviner 1 mot. Je soupçonne que le défaut de l'analyse publique précédente était de savoir comment ils limitaient le mot d'ouverture à la liste de réponses connues. Je pense cependant que nous devrions plutôt utiliser la liste complète des mots, afin de maximiser les probabilités d'indices en faveur d'une chance très étroite de deviner un mot.
Plus important encore, SAINE a une chance significativement plus élevée (de ~ 7%) de deviner une correspondance exacte (vert) au premier essai. Ce qui est incroyablement utile comme indice.
Une fois le débat sur les mots de départ terminé, nous verrons comment le système réagit avec les différents résultats !
Voyons donc comment le 2ème mot est choisi pour la réponse "PAUSE" (côté gauche).
On nous donne les informations suivantes :
La lettre I & N n'est pas dans le mot.
A est le 2ème caractère, E est le 5ème caractère.
S est soit le 3ème soit le 4ème caractère (ce n'est pas le 1er caractère).
Seulement 12 réponses possibles sont dans la liste de mots
Des trucs Wordle assez standard. Mais regardons comment cela affecte les statistiques sur les réponses possibles restantes. Et comment "PLUTO" a été choisi.
Avec seulement 12 mots restants, trouvons le moyen le plus efficace d'éliminer nos options.
D'après les contraintes suivantes, le seul mot valide à essayer était PLUTON. Bien que nous sachions que la lettre O ne figure pas dans la réponse finale, il n'y a pas de mot pour « PLUTC ». De plus, alors que le mot PLUTO ne figurait pas dans la liste de réponses, il figurait dans la liste complète des mots, ce qui en faisait une supposition valable.
Après la soumission, le système sait maintenant ce qui suit :
Cela signifie que je n'ai plus besoin de statistiques car il n'y a qu'une seule vérité : PAUSE.
Le Mohur est une pièce d'or qui était autrefois frappée par plusieurs gouvernements, dont l'Inde britannique et certains des États princiers qui existaient à ses côtés.
Les statistiques ici sont évaluées en direct et les changements dépendent du résultat de chaque tour. Ainsi, le résultat différait où:
La lettre S, A, I, N n'est pas dans le mot.
La lettre E peut être en positions 1, 2, 3, 4 mais pas 5.
Le filtrage de la liste de réponses possibles conduit aux statistiques suivantes :
Cela peut ne pas avoir de sens au début car le mot ne commence pas par C ou B. Avec 187 mots restants, c'est là que les détails de la notation commencent à avoir de l'importance.
Ce n'est peut-être pas le choix le plus optimal compte tenu de la liste de réponses connue. Cependant, c'est intentionnel car nous voulons nous concentrer à nouveau sur l'information jusqu'à ce que nous ayons une très grande confiance dans un mot. Et dans ce processus, nous pénaliserions les lettres en double pour nous concentrer sur la réduction du nombre d'options. (Il y a sans doute de la place pour des améliorations ici)
Les résultats de la conjecture étaient intéressants.
Aussi étrange et déroutant que soit le mot MOHUR, le résultat a réduit la possibilité à 12 mots. Une fois de plus, il essaie de donner la priorité à l'essai de nouveaux personnages et lui donne le mot obscur de BLYPE.
BLYPE : un morceau ou lambeau de peau
Ce mot réduit la liste des possibilités à un seul mot - ULCÈRE, qui est la réponse finale.
Note latérale : si vous le remarquez, il est prêt à essayer des caractères qu'il sait qui ne figurent pas dans la liste de réponses officielle. C'est intentionnel. Tenez compte des clones de Wordle car si la réponse réelle choisie ne se trouve pas dans la liste de réponses d'origine, le système reviendra automatiquement à l'utilisation de la liste de mots complète à la place. Rendre cela plus résistant aux variantes de Wordle.
⚠️ Avertissement de code à venir : si vous n'étiez ici que pour les calculs et les statistiques, passez à la fin. Le reste du contenu de cet article est constitué de code JS.
La classe de résolution complète peut être trouvée ici .
Cet article se concentrera sur la fonctionnalité de base requise pour faire fonctionner ce processus et non sur toutes les parties du code. Si vous n'avez pas lu la partie 1, lisez-la ici .
Le code ici a été simplifié pour ignorer les trucs "passe-partout".
Le solveur doit effectuer les opérations suivantes :
Décomposons-le, morceau par morceau.
Pour chaque tour, l'état du jeu serait généré avec :
Ceci est généré en utilisant les informations sur l'écran dans la partie 1.
Cependant, pour notre cas d'utilisation, nous aurions besoin de normaliser une partie de l'ensemble de données commun dont nous aurions besoin. Grâce à la fonction _normalizeStateObj
, nous obtenons ce qui suit.
Ceci est facilement généré en itérant .history
et les données .pos
pour construire la bonne liste de caractères en premier. Ensuite, utilisez-le pour construire la liste des mauvais caractères inversement par rapport à la liste des mots historiques.
/** * Given the state object, normalize various values, using the minimum "required" value. * This does not provide as much data as `WordleSolvingAlgo` focusing on the minimum required * to make the current system work * * @param {Object} state * * @return {Object} state object normalized */ function _normalizeStateObj( state ) { // Setup the initial charset state.badCharSet = new Set(); state.goodCharSet = new Set(); // Lets build the good charset for(let i=0; i<state.wordLength; ++i) { if( state.pos[i].foundChar ) { state.goodCharSet.add(state.pos[i].foundChar); } for(let char of state.pos[i].hintSet) { state.goodCharSet.add(char); } } // Lets iterate history and build badCharSet for(let i=0; i<state.history.length; ++i) { const word = state.history[i]; for( let w=0; w<word.length; ++w ) { // check the individual char let char = word.charAt(w); // If char is not in good set if( !state.goodCharSet.has(char) ) { // its in the bad set state.badCharSet.add(char); } } } // Return the normalize state object return state; }
Maintenant que nous avons l'état actuel du jeu, examinons le filtrage de la liste de mots :
/** * Given the wordList, filter only for possible answers, using the state object. * And returns the filtered list. This function just returns the wordList, if state == null * @param {Array<String>} wordList * @param {Object} state */ function filterWordList( wordList, state ) { // Skip if its not setup if( state == null || wordList.length <= 0 ) { return wordList; } // Get the word length const wordLength = wordList[0].length; // Filter and return return wordList.filter(function(s) { // Filtering logic // .... // all checks pass, return true return true; }); }
Pour la logique de filtrage, nous supprimons d'abord les mots dans le badCharSET.
// filter out invalid words (aka hard mode) for(const bad of state.badCharSet) { // PS : this does nothing if the set is empty if(s.includes(bad)) { return false; } }
Suivi par le filtrage des mots avec des emplacements d'indice erronés :
// filter out words with wrong hint locations, for each character position for(let i=0; i<wordLength; ++i) { // Get the word character let sChar = s.charAt(i); // Check if the chracter, conflicts with an existing found char (green) if(state.pos[i].foundChar && sChar != state.pos[i].foundChar) { return false; } // Check if the character is already a known mismatch (yellow, partial match) // for each position for(const bad of state.pos[i].hintSet) { if(sChar == bad) { return false; } } }
Pour les mots suivants sans toutes les correspondances trouvées connues (exactes et partielles) :
// filter out words WITHOUT the hinted chars // PS : this does nothing if the set is empty for(const good of state.goodCharSet) { if(!s.includes(good)) { return false; } }
De plus, nous avons une variante pour filtrer les mots uniques pour filterForUniqueWordList
. Ceci n'a pas de doublons de personnage et est utilisé dans les premiers tours :
let wordCharSet = new Set(); // iterate the characters for(const char of s) { // Update the word charset wordCharSet.add(char); } // There is duplicate characters if( wordCharSet.size != s.length ) { return false; }
Après avoir filtré toutes les réponses possibles restantes, les statistiques sont générées via charsetStatistics( dictArray )
Cela se fait en créant un objet pour le type de statistiques. Itérer la liste de mots et incrémenter les nombres :
/** * Analyze the given dictionary array, to get character statistics * This will return the required statistics model, to be used in guessing a word. * * Which is provided in 3 major parts, using an object, which uses the character as a key, followed by its frequency as a number * * - overall : Frequency of apperance of each character * - unique : Frequency of apperance of each character per word (meaning, duplicates in 1 word is ignored) * - positional : An array of object, which provides the frequency of apperance unique to that word position * * Note that because it is possible for the dataset to not have characters in the list / positional location, * you should assume any result without a key, means a freqency of 0 * * @param {Array<String>} dictArray - containg various words, of equal length * * @return Object with the respective, overall / unique / positional stats **/ charsetStatistics( dictArray ) { // Safety check if( dictArray == null || dictArray.length <= 0 ) { throw `Unexpected empty dictionary list, unable to perform charsetStatistics / guesses`; } // The overall stats, for each character let overallStats = {}; // The overall stats, for each unique charcter // (ignore duplicates in word) let overallUniqueStats = {}; // The stats, for each character slot let positionalStats = []; // Lets initialize the positionalStats let wordLen = dictArray[0].length; for(let i=0; i<wordLen; ++i) { positionalStats[i] = {}; } // Lets iterate the full dictionary for( const word of dictArray ) { // Character set for the word const charSet = new Set(); // For each character, populate the overall stats for( let i=0; i<wordLen; ++i ) { // Get the character const char = word.charAt(i); // Increment the overall stat this._incrementObjectProperty( overallStats, char ); // Populate the charset, for overall unique stats charSet.add( char ); // Increment each positional stat this._incrementObjectProperty( positionalStats[i], char ); } // Populate the unique stats for( const char of charSet ) { // Increment the overall unique stat this._incrementObjectProperty( overallUniqueStats, char ); } } // Lets return the stats obj return { overall: overallStats, unique: overallUniqueStats, positional: positionalStats } }
C'est assez simple pour les boucles sur chaque mot et chaque incrément de caractère dans le décompte statistique respectif.
Le seul hic est que nous ne pouvons pas faire d'incrémentation ++ sur une propriété d'objet lorsqu'elle n'est pas initialisée. Cela entraînerait l'erreur suivante :
// This will give an exception for // TypeError: Cannot read properties of undefined (reading 'a') let obj; obj["a"]++;
Nous aurions donc besoin d'utiliser une simple fonction d'assistance pour incrémenter correctement notre cas d'utilisation nécessaire :
/** * Increment an object key, used at various stages of the counting process * @param {Object} obj * @param {String} key **/ _incrementObjectProperty( obj, key ) { if( obj[key] > 0 ) { obj[key]++; } else { obj[key] = 1; } }
Au cœur du solveur se trouve la logique de notation. Qui est classé sur chaque entrée de mot possible avec les statistiques et l'état donnés.
Avis de non-responsabilité : Je ne prétends pas qu'il s'agit de la fonction de notation de mots la plus optimale pour Wordle. Il peut certainement être amélioré, mais il est assez bon d'après mes tests jusqu'à présent. =)
/** * The heart of the wordle solving system. * * @param {Object} charStats, output from charsetStats * @param {String} word to score * @param {Object} state object (to refine score) * * @return {Number} representing the word score (may have decimal places) **/ function scoreWord( charStats, word, state = null ) { // Character set for the word, used to check for uniqueness const charSet = new Set(); // the final score to return let score = 0; // Wordle Strategy note: // // - Penalize duplicate characters, as they limit the amount of information we get // - Priotize characters with high positional score, this helps increase the chances of "exact green matches" early // reducing the effort required to deduce "partial yello matches" // - If there is a tie, in positional score, tie break it with "unique" score and overall score // this tends to be relevent in the last <100 matches // // - We used to favour positional score, over unique score in the last few rounds only // but after several trial and errors run, we found it was better to just use positonal score all the way // Lets do scoring math // ... // Return the score return score; }
Cela passe par différentes étapes : Tout d'abord, nous ajoutons un filet de sécurité pour éviter que le système ne suggère à nouveau un mot (énorme score négatif).
// Skip attempted words - like WHY ??? if( state && state.history ) { if( state.history.indexOf(word) >= 0 ) { return -1000*1000; } }
Nous itérons ensuite chaque caractère du mot, et les notons respectivement :
// For each character, populate the overall stats for( let i=0; i<word.length; ++i ) { // Get the character const char = word.charAt(i); // Does scoring for each character // ... }
Mots pénalisants avec des caractères répétés ou des caractères connus :
// skip scoring of known character matches // or the attempted character hints if( state ) { // Skip known chars (good/found) if( state.pos && state.pos[i].foundChar == char ) { score += -50; charSet.add( char ); continue; } // Skip scoring of duplicate char if( charSet.has( char ) ) { score += -25; continue; } // Skip known chars (good/found) if( state.goodCharSet && state.goodCharSet.has(char) ) { score += -10; charSet.add( char ); continue; } } else { // Skip scoring of duplicate char if( charSet.has( char ) ) { score += -25; continue; } } // Populate the charset, we check this to favour words of unique chars charSet.add( char );
Enfin, nous calculons le score pour chaque statistique de position avec le score de caractère unique utilisé comme bris d'égalité :
// Dev Note: // // In general - we should always do a check if the "character" exists in the list. // This helps handle some NaN situations, where the character has no score // this is possible because the valid list will include words, that can be inputted // but is not part of the filtered list - see `charsetStatistics` if( charStats.positional[i][char] ) { score += charStats.positional[i][char]*10000; } if (charStats.unique[char]) { score += charStats.unique[char] } // -- Loops to the next char -- //
Maintenant que nous avons la fonction de notation, nous pouvons commencer à assembler toutes les parties de la fonction "suggestWord".
Nous avons des statistiques qui peuvent ensuite être utilisées pour marquer des mots. Maintenant, rassemblons-le pour suggérer le meilleur mot de notation.
Nous commençons par recevoir l'état du jeu :
/** * Given the minimum state object, suggest the next word to attempt a guess. * * --- * # "state" object definition * * The solver, requires to know the existing wordle state information so this would consist of (at minimum) * * .history[] : an array of past wordle guesses * .pos[] : an array of objects containing the following info * .hintSet : set of characters that are valid "hints" * .foundChar : characters that are confirmed for the given position * * The above is compliant with the WordleAlgoTester state object format * Additional values will be added to the state object, using the above given information * --- * * @param {Object} state * * @return {String} word guess to perform */ suggestWord( state ) { // Normalize the state object state = this._normalizeStateObj(state); // Let'sLets get the respective wordlist let fullWordList = this.fullWordList; let filteredWordList = this.filterWordList( this.filteredWordList, state ); let uniqueWordList = this.filterForUniqueWords( this.uniqueWordList, state ); // As an object let wordList = { full: fullWordList, unique: uniqueWordList, filtered: filteredWordList }; // Lets do work on the various wordlist, and state // this is refactored as `suggestWord_fromStateAndWordList` // in the code base // .... }
Une fois que nous avons les différents états de jeu et listes de mots, nous pouvons décider de la "liste de mots statistiques", que nous utilisons pour générer le modèle statistique.
// Let's decide on which word list we use for the statistics // which should be the filtered word list **unless** there is // no possible answers on that list, which is possible when // the system is being used against a WORDLE variant // // In such a case, lets fall back to the filtered version of the "full // word list", instead of the filtered version of the "answer list". let statsList = wordList.filtered; if( wordList.filtered == null || wordList.filtered.length <= 0 ) { console.warn("[WARNING]: Unexpected empty 'filtered' wordlist, with no possible answers : falling back to full word list"); statsList = this.filterWordList( wordList.full, state ); } if( wordList.filtered == null || wordList.filtered.length <= 0 ) { console.warn("[WARNING]: Unexpected empty 'filtered' wordlist, with no possible answers : despite processing from full list, using it raw"); statsList = wordList.full; }
Une fois que nous avons décidé de la liste de mots statistiques, nous recevons les statistiques :
// Get the charset stats const charStats = this.charsetStatistics(statsList);
Maintenant, nous décidons de la liste de mots à utiliser pour décider d'un mot. Nous nous référons à cette liste sous le nom de "scoredList".
Au cours des premiers tours, nous visons à utiliser autant que possible des mots uniques. Ce qui n'inclurait pas les personnages que nous avons essayés précédemment. Cela peut inclure des mots dont nous savons qu'ils ne figurent pas dans la liste de réponses possibles.
Ceci est intentionnel car nous optimisons pour le gain d'informations, mais plutôt sur une petite chance aléatoire de succès précoce.
Cependant, lorsque celui-ci sera vidé ou que le jeu en sera aux derniers tours, nous reviendrons à la liste complète. Lors du tour final, nous devinerons toujours en utilisant la liste filtrée lorsque cela est possible : (donnez-lui simplement notre meilleure réponse).
// sort the scored list, use unique words in first few rounds let scoredList = wordList.unique; // Use valid list from round 5 onwards // or when the unique list is drained if( scoredList.length == 0 || state.round >= 5 ) { scoredList = wordList.full; } // Use filtered list in last 2 round, or when its a gurantee "win" if( wordList.filtered.length > 0 && // (wordList.filtered.length < state.roundLeft || state.roundLeft <= 1) // ) { scoredList = wordList.filtered; }
Une fois que nous avons décidé de la liste de notation pour appliquer les statistiques, notons et trions-la :
// Self reference const self = this; // Score word sorting scoredList = scoredList.slice(0).sort(function(a,b) { // Get the score let bScore = self.scoreWord( charStats, b, state, finalStretch ); let aScore = self.scoreWord( charStats, a, state, finalStretch ); // And arrange them accordingly if( bScore > aScore ) { return 1; } else if( bScore == aScore ) { // Tie breakers - rare // as we already have score breakers in the algori if( b > a ) { return 1; } else if( a > b ) { return -1; } // Equality tie ??? return 0; } else { return -1; } });
Et renvoyez l'élément ayant obtenu le score le plus élevé :
// Return the highest scoring word guess return scoredList[0];
Avec le code d'interaction de l'interface utilisateur effectué dans la partie 1. Appuyez sur le bouton "Exécuter" pour voir comment notre bot Wordle fonctionne !
Hé, pas mal, mon bot a résolu le Wordle d'aujourd'hui !
Car les bots vont utiliser une technique assez "inhumaine" de calcul de probabilités avec des dictionnaires géants.
La plupart des humains trouveront que c'est à la limite de faire des suppositions vraiment bizarres et folles. Croyez les maths parce que ça marche.
Lorsque vous jouez pour l'équipe humaine, ce que vous devez retenir de cet article, c'est que vous devez simplement commencer par le mot "SAINE", ou les mots que vous souhaitez.
C'est à vous de décider puisque c'est votre jeu après tout ! =) Amusez-vous.
Bonne Parole ! 🖖🏼🚀
Publié pour la première fois ici