This may be a common problem after learning programming for a long time. After playing Wordle a few times, I started to think about whether there is an optimal algorithm for this game, but due to my own level, I did not do too in-depth research. Until I saw 3Blue1Brown's video on the optimal solution of Wordle on YouTube. After watching it four or five times to understand all the principles, I also hope to explain to readers how to obtain this optimal algorithm.

Initial data

By checking the source code of Wordle, we learned that the game provides a total of 12,972 words as input words, and we also found that the possible correct answers are 2,315. However, because this information was only learned after viewing the source code, we still did not know these 2,315 words by default when designing the algorithm, thinking that all 12,972 words may become the final correct answer.

Algorithm

The optimal solution sought by the algorithm is actually to find the best word input order that can filter out the correct answer as quickly as possible. How to judge the quality of a word? Simply put, if a word can help eliminate more possibilities, it means the word is better. This can only be said to be a general idea. In order to find the optimal words, quantification still needs to be done.

For each word, there are 12972 possible correct answers, and each word has a total of three to the fifth power of possible patterns (each letter column has three possibilities: gray, yellow, green, a total of five columns).

Each pattern corresponds to a possible correct answer word list, then the number of words contained in these possible correct answer word lists divided by the total number of words is the probability that each pattern may appear under the current input word.

The probability of each pattern appearing is multiplied by the quality standard it gives to judge, and then the sum is the quantitative quality score of a word. This criterion is the information entropy that the current word can bring.

Information Entropy

In order to explain clearly, here is an example to briefly explain the two concepts of "information entropy" and "information content" in information theory. Suppose there are 64 balls in a basket, and A and B play a ball guessing game. A is told one of the 64 balls in advance, and then tells B the information so that B can find the target ball as soon as possible. If A says: "The target ball is on the left side of the basket", then this information helps B filter out half (32/64) of the small balls; if A says: "The target ball is the one in the upper left corner", then this information helps B filter out 63 small balls. The second information helps B to locate one of the 64 balls. According to the "information content" formula, the information content of this information is 6 bits. In fact, it means that this information needs to have 6 bits (2 to the 6th power is equal to 64) before it can be saved, because it is necessary to find 1/64 of the ball. In the same way, the first information only helps determine half of all the balls, so this information only contains 1 bit of information content.

The probability of each possible pattern is multiplied by the information content conveyed by the pattern to get the expected information content that a word can bring, which is information entropy. The higher the information entropy, the higher the information content that the word brings under various circumstances.

With the criteria for judging the quality of words, the algorithm only needs to calculate the information entropy of 12972 words, and then select the word with the highest information entropy as the starting word. After each input, you only need to follow the same steps according to the prompts given by the game to maximize the information entropy for each input.

Word frequency

So is this the optimal algorithm? The answer is no, because after each word is entered, the word with the highest information entropy is selected from the optional list, but it ignores whether the word is a commonly used word. Some words may have high information entropy, but the word itself is unlikely to be the final correct answer, or when the information entropy of two words is the same, the algorithm cannot select the word that is more likely to be the answer, but can only choose according to the alphabetical order.

In order for the algorithm to take into account the commonness of words, the algorithm needs to consider the frequency of words. Although some words are relatively common words, the frequency of occurrence is still quite different. If you rely solely on word frequency, the probability of the two words will be 1000 times different, so you choose to use the sigmoid function to make the probability of a word that may be the answer close to 1 or to make the probability of a less common word close to 0.

When making choices in subsequent algorithms, you need to consider the possibility brought by the frequency of words. Each word still has an information entropy as before, and also has a probability of being the correct answer obtained through frequency. The purpose of the algorithm is to improve the final score, that is, to improve the expected score. Assume that after three inputs, we calculate through the algorithm that "words" may become the final correct answer: the information entropy of "words" is 1.27, and the frequency probability is 0.58. At this time, the algorithm needs to calculate the expected score after inputting this word. The frequency probability tells that there is a 58% probability that this word may become the correct answer, that is, it can succeed in the fourth time. The remaining 42% probability will make the final result at least 4 times, which is 4 plus a possible expected number of times.

The calculation of this expected number of times requires a comprehensive judgment based on the information that the current word can provide and the information remaining in the current game. If the current game still requires a large amount of information, that is to say, there are many possibilities, but the information provided by the words is not enough, then the expected number of times will be relatively high, but if the current amount of information is similar to the amount of information provided by the words, then the expected number of times will be very low. That is, there is a function between the difference between the information required by the game and the information provided by the words and the expected number of times. This function is obtained by modeling the data obtained after simulating the game, that is, to see how many guesses are needed when the information difference is. Assuming that the remaining information in the current game is 1.44 bits, the final expected number of times to enter this word is as follows:

At this point, the algorithm can select the optimal word "SALET" to play the game by calculating the word's information entropy and word frequency probability. Some people say that this algorithm will ruin the game, but after seeing this, do you still think this is a discussion of the game? Forget what the best starting word is, experience how to find information content, find information entropy, and design a greedy algorithm. This is the meaning of this article. It starts with games and ends with learning. (If you want to experience this algorithm, you can click on the Wordle Solver below to experience it)

Related reading:

  • 3Blue1Brown Original video one
  • 3Blue1Brown Original video two
  • Wordle Solver