Wordle Player Simulator
Information Theory
Project Overview
In this project, we built a “Wordlebot” – a fake player who is super good at word guessing basedon the rule of Wordle. We also built a wordle simulator to test the bot. The algorithm of theplayer is based on entropy. It would pick the word with the highest entropy as the next guess.
My Contributions
In addition to summarizing the principles and logic behind the robot guesser, I took charge of designing the user interface (UI) interface, ensuring an intuitive and visually appealing experience for users. Furthermore, I compiled a comprehensive report, documenting the project's methodology, instructions, and oberservations.
k : the number of letters in each word (5 for Wordle)
n : the number of legitimate words
m : the number of possible answers
1. Complexity of filterList(String word, List<String> list, int[] info)
O(list.size() * word.length())
So complexity filtering the answerList = O(nk).
2. Complexity of computing the maxEntropy of all legitimate words:
m * (average size of filtered lists + complexity filtering the answerList)
Given average entropy E, average size of filtered lists = n / 2^ESo the complexity of computing the max entropy is: O(m * (n / 2 ^ E + nk))
3. Complexity of getting next best word:
We can just substitute m and n with sizes of filtered lists and E with the new average entropy, k stays the same.
Mathematical Analysis
Nov 2022
Here are the representative screenshot of the running results.
This is how we calculate the entropy of a word:
For each block of a word, there are 3 colors: gray, yellow, and green, so after a valid guess, there are 3^5 possible outcomes. Each of these outcomes(patterns) will give us some bits of information.
First, we need to know what 【PATTERN】is. It includes 3^5 patterns of all possibilities. We use【filterList】to get the remaining list of possible answers.
Then calculate the p of each word in the list of the possible word. p is the division of qualified possibilities and possible answers.
Finally, we calculated the entropy of each word using【entropy += p * (Math.log(1 / p) / Math.log(2.0))】and update the maxEntropy using the 【Math.max】 function.
Here are the average score of highest 3 words of brute force simulation:
According to the brute force simulation from the below video, We should use SALET as the first guess because it’ll give us more information.
Since we know how to compute the entropy for a given wordList and a given answerList, picking the next word will be easy. After every move, we call filterList() method to filter both answerList and wordList, then we call bestRemainWord() using the filtered lists to get the next optimal guess.
