This content originally appeared on Level Up Coding - Medium and was authored by Rebecca
Using alpha-beta pruning to solve wordle
tl;dr
I created a solver for wordle that you can play with here: https://bekyblog.tech/wordle-solver/
Code is available at https://github.com/bec-ca/botle
Intro
When I ran into wordle, I had all sorts of questions. What is the best strategy? What is the most difficult word? I heard people talking about some strategies such as picking the first word based on the distribution of letters in English. I knew that was very approximate and didn’t really answer my question. I wanted to know the best strategy possible. And by best strategy, I mean the strategy that minimizes the number of guesses in the worst case. Are all English words guessable in 6 attempts? To answer those questions, I decided to write a program that can find the best strategy.
Maybe some people would say that this ruins the game, but I find a lot more fun at this kind of approach to the game. The actual best strategy depends on the words that you personally know, which I can’t possibly know.
The puzzle
If you are living under the rock and haven’t played wordle yet, go check it out here.
Word list
First step is to define what is the set of words that are valid guesses and what is the set of the words. There are many sources of all English words available, we could just pick one of those. However, if we inspect wordle’s javascript, we can find the list of valid words. We can even find the list of secret words which is a separate list. It is worth noting that the list of valid guesses is very comprehensive and contains extremely unusual words that most people probably don’t know. However the list of secret words contains words that are a lot more familiar. My understanding for having separate list of words is that, they would like to accept absolutely any word that someone might wanna try as a guess, but, picking some obscure word as the secret word, would make the game a lot less fun.
I’m not sure if exploiting the fact that the list of valid guesses words and secret words are different would be considered cheating. A human player, doesn’t even have access to either list, they have to rely on their own knowledge of the English language. I think the most fair thing to do would be to pick a list of words that are more likely for an average player to know. But, constructing such a list is a bit tedious and I’m not very interested on that part of the problem. I attempted using the most frequent words on wikipedia, but that ended up working that well since even the 10k most common words still leaves out some of the words in the list of secrets.
Initial greedy approach
First we need some data. What are even the words that we can guess? It turns out that the list of possible words are embedded on the page’s javascript. If you look carefully, even the secrets are listed in order the appear. Although that can tell you the answer, that says nothing about the best strategy. So I just took the list of words from the javascript.
Once we have the list of words we can guess, my initial idea was a greedy approach as follows:
- Pick a word from the list as a potential guess
- Pick a second word from the list as a potential secret
- Compute what would be the pattern we would get if that pair of guess and secret word.
- Now, for every word on the list, we compute the pattern we would get assuming that word is the secret, if that is different from step 3., we eliminate that word from the list of possible secrets.
- Take note of the number of secrets left
- Repeat steps 2 to 5 for every word on the list as a potential secret, and take the potential secret that results in the least amount of eliminations, that is the worst secret for that guess, let’s call this the number of remaining secrets
- Now repeat steps 1 to 6, picking a different words for potential guess, and choose the word that yields the least number of remaining secrets.
So that gives us some reasonable guess to make at any point. That is, we make a guess that eliminate the most number of possible secrets in the worst case. But, that is still a greedy solution and probably not optimal if we look at how many eliminations we make after 2 guesses.
2 player game approach
Next, I decided to model wordle as a 2 player game. On one hand we are trying to find the secret word with fewer guesses as possible, but on the other hand we want to make sure the most difficult secret don’t take extra guesses. Therefore we can think about it as a game where we are trying to find the secret word to minimize the number of guesses, meanwhile our opponent is trying to pick the secret that will maximize the number of guesses and they can do so at every guess we make as long as the secret word is compatible with the guesses made so far. This model doesn’t lose any generality comparing to picking a fixed secret at the beginning of the game.
This modeling is cool because we can apply the same approaches used on other 2 player games such as chess. That is, we can perform a mini-max search to find the best solution with alpha-beta pruning and so on.
The downside of this modelling is that, a mini max search grows exponentially with the number of steps by a factor of the number of choices we can make. And we have 12 thousands different words to pick from. Unlike chess, where usually there are a few dozen moves that are legal at any position. But, ultimately, that turned out not to be a big problem. With some careful optimizations, I was still able to find the best strategy within reasonable running time.
Many of the optimizations were very similar to what is done on chess engines, which I happen to be a bit familiar with. Plus there were some optimizations that exploited special properties of wordle. Here is a list of some of them:
- Alpha-beta pruning, this is the most basic optimization for a mini-max search
- Cache, aka, transposition table. Different choices can lead us to the same state, eg, picking a word X followed by Y is the same as picking Y followed by X, a cache can be used to void recomputing that state
- Precompute pattern matching words, although pattern matching that is not terribly slow and speeding it up only gives us a constant factor speed up, I still found out that the program was spending most of its time computing the pattern matches, so that ended up being well worth it
- Note that the opponent doesn’t really need to pick a secret word, they only need to pick a pattern, since multiple secret words will yield the same pattern, we only need to pick one secret for each distinct pattern.
- Sorting, alpha-beta pruning works best if we try the best choice first. Of course, we don’t know that yet, but an approximate best first is also much better. So, at each step, I sort the words based on the greedy approach above.
With these optimizations, and maybe a few more things, my program ran fast enough to find the optimal strategy.
I also implemented the “hard mode” that wordle offers, where each guess has to be compatible with the guesses made so far, that changes the algorithm very little though.
Results
To create the results table bellow, I simulated the game with every secret and every possible starting word, and at each step from the second step I picked the word recommended by the solver. It took a few days to run everything, using no secret list made things much slower, also hard mode was even slower than normal mode. The meaning of the columns are:
- Dictionary : Which set of words were allowed as valid guesses
- Secrets : Whether I used the separate list of secret words, if not, I assume any word in the dictionary can be a secret.
- Hard : Whether the game was running in the hard mode.
- Best : The starting word that yielded the lowest average number of guesses for all secrets
- Avg : The average number of guesses for the word in the Best column
- Worst : The number of guesses required for the most difficult secret when starting with the word from the column Best
| Dictionary | Secrets | Hard | Best | Avg | Worst |
|---------------|---------|------|-------|------|-------|
| Wordle | Yes | No | crate | 3.53 | 5 |
| Wordle | No | No | tares | 4.23 | 8 |
| Wordle | Yes | Yes | leant | 3.65 | 7 |
| Wordle | No | Yes | tromp | 4.52 | 12 |
| Wikipedia 10k | No | No | tiles | 4.01 | 6 |
| Wikipedia 10k | No | Yes | trims | 4.23 | 12 |
Browser version
I compiled the engine to wasm and made it available online for anyone to play around with it. You can see the top words suggested by the engine and pick any one of them. The starting words are all precomputed because those take a long time. The remaining guesses are computed locally, which I find very satisfying to watch as it goes. Check it out: https://bekyblog.tech/wordle-solver/
Code
I made the code available for both the site and the engine on github: https://github.com/bec-ca/botle. By the way, it is named botle because it is a portmanteau of bot and wordle. Yeah, I know, I’m not a very funny person.
Wordle solver was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Rebecca
Rebecca | Sciencx (2022-03-09T02:31:31+00:00) Wordle solver. Retrieved from https://www.scien.cx/2022/03/09/wordle-solver/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.