Solving Wordle: Part I

Around 4 years ago, I created a robot friend to conquer Sudoku called Bernard. I didn’t know it then, but I had created a monster. Bernard’s prowess at this game, once described as ‘the worst ever to be invented’, was so formidable that a publication detailing his aforementioned prowess soon captivated literally dozens of readers. Bernard’s 15 seconds of fame catapulted him into a new social elite, one that no longer required his master.

This all changed in early 2022, when his faithful devotees became consumed to the point of madness with a new phenomenon. Betraying his pathological need to be liked, Bernard faced a choice. He could either plunge into the gutter of obscurity, or he could choke down his ego and come crawling back to his master. I can’t say I wasn’t a little pleased when he chose the latter, entering my metaphorical office with his metaphorical cap in his hand: begging me to teach him Wordle.

Wordle is the bastard offspring of Guess Who and a rogue dictionary, refined by Welsh software engineer Josh Wardle. The aim of the game is to guess a hidden five letter word in six tries, with each incorrect guess giving information to the player about which letters are in the answer. You can use this information to narrow the list of possible words and deduce the answer.

Figure 1: Rules of the game

Rules of the Game

Let’s start by coding the game and its rules. As usual, I won’t be sharing the full project until the end and I encourage you to have a go at building this yourself, along with this blog.

The first thing we need is a function that will return the hint for a given guess for a known answer. With the rules above, this looks pretty easy:

But there’s a catch. Some words have the same letter appear more than once and the number of occurrences can differ between our guess and the answer. For example what if the answer was ALGAE and our guess was KEEPS?

guess_hint("KEEPS", "ALGAE")
⬛🟨🟨⬛⬛

Intuitively, this might suggest to the player that there are 2 ‘E’s in the answer, and thus ALGAE was not possible. The eager beavers over at NerdChalk have explained brilliantly how Wordle handles this.

The game returns 🟨 for the first ‘E’ and ⬛ for the second, telling the player there is only one E in the answer. If the answer has multiple occurrences of the letter, it will indicate that with the hint.

Figure 2: Repeated letters in guess

Our simple code is works for the first case, but is incorrect for the others. The third example shows another specific snag. The first occurrence of S is shown to be incorrect because the second S is the exact position in the answer.

These may seem like tiny details but they are the butterflies that precede the hurricanes that will eventually topple your program’s empire. The code for correction is a bit ugly, but it works:

get_hint_from_guess('TABLE', 'LOBBY')
⬛⬛🟩🟨⬛
get_hint_from_guess('KEEPS', 'ALGAE')
⬛🟨⬛⬛⬛
get_hint_from_guess('SLOSH', 'GHOST')
⬛⬛🟩🟩🟨

Now you may just be learning to code and are heading into it with the deluded self confidence of a journeyman boxer. But it is at this point I would urge you to take a pause, prepare a stiff drink, and write some unit tests. These are snippets of code that run small, discrete parts of your program and check that a certain result has been achieved. The reason we write them is related to the butterflies I mentioned earlier. Our last improvement may have vanquished them, but the unit tests allow us to easily check that they haven’t reappeared. Or not just reappeared, but started multiplying. Or not just multiplying, but forming insular groups of like minded individuals that gradually nurture increasingly radical dreams of revolution.

One more rule of the game is that the guesses have to be a real five letter word. Checking for this is easy, we just download a freely available list of UK English words.

Constructing the Game

The game is quite simple, we just create a class with some helper properties and a method for the player to make guesses.

This enables a simple interface for human players:

game = Game('plant')
while not game.is_over:
    guess = input()
    print(game.make_guess(guess))

E.g.
crane
⬛⬛🟩🟩⬛
table
🟨🟨⬛🟨⬛
plant
🟩🟩🟩🟩🟩

Teaching Bernard

The fun for us squishy humans is figuring out the constraints and then trying to think of a word that fits them. The better human players think about words that use the most common letters, or vowels to try to constrain the possible answers quickly. It works elegantly because you don’t need to buy a board of badly drawn caricatures to guess attributes from, every English speaker already has a database of words stored in their head. That list of words we downloaded earlier will do just nicely for our robot.

The first step is to teach Bernard how to remove possible words when given information. For the simple rules, this should be quite straight forward:

• When we know a letter with exact position, remove any words with a different letter in that position.
• When we know a letter in an incorrect position, remove any words without that letter and those with that letter in the incorrect position.
• When we know a letter is wrong, remove any words without that letter.

We also want to make sure we can aggregate the information across multiple guesses.

game = Game('olive')
game.make_guess('crane')
game.make_guess('pious')
for w in game.possible_words:
    print(w)

OLDIE
OLIVE
OXIDE

In the spirit of full disclosure, the solution I’ve written above is actually incorrect and won’t work correctly for all cases. Those of you who have seen the bug, should proudly help themselves to a cookie whilst they implement the fix. For the rest of you — also have a cookie, because cookies are great and everyone should have them — and then try to figure out what needs to be fixed. For a clue, check the possible words for an answer of OLIVE after guessing EXILE.

Now Bernard is adept at narrowing down possibilities, so if he had the above game, he’d know that there were only 3 possibilities left. But without a strategy for choosing guesses, he’d be at the whims of cosmic probability. We can see how kind the cosmos is:

QUIRE
⬛⬛🟩⬛🟩
TWINE
⬛⬛🟩⬛🟩
OLIVE
🟩🟩🟩🟩🟩

Quite kind, as it so happens. Right, now I’ve finished investing my savings in lottery tickets, we should test a bit more thoroughly. Averaging across all 2250 possible answers, he scores 4.36. He also failed to solve 88 words. This is actually surprisingly good for random guessing, but it’s not exactly mastery of the game and his overall average is above the widely recognised par score of 4. It’s also not deterministic, so we’re leaving it up to the cosmos as to how well he’ll solve a puzzle on a given day, so not really great there either. Please patient whilst I try to refund my lottery tickets.

Getting Smart

Claude Shannon, a talented mathematician with the brain the size of a galaxy, is often credited as being the father of information theory. His theory is so good that its most basic principles are sufficient to train the optimal player in a game taking the world by storm 70 years later. I was going to explain how this works, but it transpires that when I first had the idea to use Wordle as a thinly veiled excuse to teach programming, Grant Sanderson’s idea to use Wordle as a thinly veiled excuse to teach information theory was already graduating from MIT and getting it’s first job at Google. So I recommend that you stop reading this right now and watch 3BlueBrown’s marvellous explanation of how to use information theory to solve Wordle. Then come back, and I’ll show you how to build it as well as improve upon it.

Welcome back, I’m assuming you’re now equipped with knowledge about bits, information value and entropy. The two components of entropy are the probability of a hint occurring and the number of possibilities that hint eliminates.

The probability of a hint occurring for a given guess can be calculated by looping over all the answers and counting the number of times each hint appears. Then you can divide this frequency by the total number of words for the probability of it occurring.

Figure 3: Hint probability

Now we have the probability, we can calculate information value and expected value:

Figure 4: Information value and entropy equations

To find the best opener, we simply compute the entropy for all possible words. Like 1Blue3Brown, the top result is TARES. Obviously I know that that refers to the plural of the common vetch, a widely distributed scrambling herbaceous plant of the pea family. Unfortunately Bernard had hired a laminated weasel for a publicist who insisted on using a more common opener lest we alienate the public. So we’ll try the next best iteration, RATES.

Entropy isn’t just useful for picking an opener, but we can use this calculation to choose the best guess at any given point in a game. Also, the answers chosen for the official Wordle game are not selected at random from all possible words, they are an arbitrary set of words chosen that tend to be commonly known words. It’s slightly cheating, but we can give Bernard this list to improve the quality of his guesses. I thought perhaps my student would balk at this idea, but it seems his time amongst the landed gentry rather loosened his morals.

That gives us a score of 3.58 with 10 failures, across all games, which is considerably better, completely nearly all games in 6 tries with a below par score on average. Let’s have a closer look at one of the failures, when trying to guess WATCH:

CRANE
🟨⬛🟨⬛⬛
YACHT
⬛🟩🟨🟨🟨
BATCH
⬛🟩🟩🟩🟩
HATCH
⬛🟩🟩🟩🟩
LATCH
⬛🟩🟩🟩🟩
MATCH
⬛🟩🟩🟩🟩

We can see that Bernard runs into a classic Wordle problem. After the first two guesses, there are only 6 possible words remaining: BATCH, HATCH, LATCH, MATCH, PATCH and WATCH. All of our clever mathematics is useless here, as none of the guesses are able to eliminate any other option, which leaves us once again at the mercy of fate. Many humans have found themselves in this situation, and a common trick is employed where the player is willing to ‘waste’ a go on a word they know isn’t the answer, but has a chance of eliminating more options. This is a balancing act though, as we also want to ensure we guess the correct answer in as few turns as possible.

This small tweak allows us to control how eager Bernard is to sacrifice a turn. I’ve found (mostly through trial and error) that it’s best to narrow options further as long as there are more than 4 possible answers remaining. Now when Bernard plays again:

CRANE
🟨⬛🟨⬛⬛
MOIST
⬛⬛⬛⬛🟨
HABLE
🟨🟩⬛⬛⬛
PATCH
⬛🟩🟩🟩🟩
WATCH
🟩🟩🟩🟩🟩

Success! Testing across all games, Bernard is now able to solve every single one, with an average score of 3.47. Now all that’s left is for Bernard to show off his talents to the world.

Join us next time where we teach Bernard how to play the game for real, instead of just running simulations in his head.