Wordle Solver with Information Theory — Full Breakdown & Transcript

[00:01] the last month or two, and never one to overlook an opportunity for a math makes for a very good central example in a lesson about information theory, and in particular a topic known as entropy. You see, like a lot of people, I got

[00:15] a lot of programmers, I also got sucked into trying to write an algorithm that could. And what I thought I'd do here is just talk through with you some of my math that went into it, since the whole algorithm centers on this idea of

[00:30] algorithm centers on this idea of entropy. two birds with one stone here, while we go through the rules of the game, let me

[00:45] this, which is to develop a little algorithm that will basically play the game for us. So, I haven't done today's Wordle, this is February 4th, and we'll see how the bot does. The goal of Wordle is to guess a mystery five-letter word,

[00:58] to guess. For example, my Wordle bot suggests that I start with the guess crane. Each time that you make a guess, you get some information about how close your guess is to the true answer. Here, the gray box is telling me there's no C

[01:12] in the actual answer. The yellow box is telling me there is an R, but it's not telling me that the secret word does have an A, and it's in the third position. And then there's no N, and there's no E. So, let me just go in and

[01:25] tell the Wordle bot that information. We started with crane, we got gray, yellow, Don't worry about all the data that it's showing right now, I'll explain that in due time, but it's top suggestion for our second pick is stick. And your guess

[01:39] does have to be an actual five-letter word, but as you'll see, it's pretty you guess. In this case, we try stick. And all right, things are looking pretty good. We hit the S and the H, so we know

[01:52] there's an R. And so, it's going to be like S H A something R, or S H A R And it looks like the Wordle bot knows that it's down to just two possibilities, either shard or sharp. Now, it's kind of a toss-up between them

[02:06] cuz it's alphabetical it goes with shard. we got it in three. If you're wondering if that's any good, the way I heard one person phrase it is that with Wordle four is par and three

[02:19] is birdie. Which I think is a pretty apt analogy. You have to be consistently on your game to be getting four, but it's certainly not crazy. But, when you get So, if you're down for it, what I'd like to do here is just talk through my

[02:33] how I approach the Wordle bot. And like I said, really it's an excuse for an is to explain what is information and is to explain what is information and what is entropy.

[02:50] frequencies of different letters in the English language. guess or an opening pair of guesses that hits a lot of these most frequent letters? And one that I was pretty fond of was doing other followed by nails.

[03:03] you know, you get a green or a yellow. That always feels good. It feels like you're getting information. But, in these cases, even if you don't hit and giving you a lot of information since it's pretty rare to find a word that

[03:15] doesn't have any of these letters. But, even still, that doesn't feel super nothing to consider the order of the letters. Why type nails when I could type snail? Is it better to have that s at the end? I'm not really sure.

[03:29] to open with the word wee-wee, which kind of surprised me cuz it has some the y. But, who knows? Maybe that is a better opener. Is there some kind of quantitative score that we can give to

[03:42] judge the quality of a potential guess? Now, to set up for the way that we're back and add a little clarity to how exactly the game is set up. So, there's a list of words that it will allow you to enter that are considered valid

[03:55] long. But, when you look at it, there's a lot of really uncommon things, things like ahead or ali and arg, the kind of words that bring about family arguments the game is that the answer is always going to be a decently common word. And

[04:10] in fact, there's another list of around 2,300 words that are the possible answers. And this is a human-curated list, I I think specifically by the game creator's girlfriend, which is kind of fun. But, what I would like to do, our

[04:23] we can write a program solving Wordle that doesn't incorporate previous knowledge about this list. For one thing, there's plenty of pretty common that list. So, it would be better to write a program that's a little more

[04:36] resilient and would play Wordle against anyone, not just what happens to be the official website. And also, the reason that we know what this list of possible answers is is because it's visible in the source code. But, the way that it's

[04:48] specific order in which answers come up from day to day. So, you could always be. So, clearly there's some sense in which makes for a more interesting puzzle and a richer information theory lesson is to

[05:02] instead use some more universal data, like relative word frequencies in having a preference for more common words. So, of these 13,000 possibilities, how should we choose the opening guess? For

[05:16] example, if my friend proposes weary, how should we analyze its quality? Well, the reason he said he likes that unlikely W is that he likes the long shot nature of just how good it feels if you do hit that W. For example, if the

[05:28] like this, then it turns out there are only 58 words in this giant lexicon that match that pattern. So, that's a huge reduction from 13,000. But, the flip very uncommon to get a pattern like this. Specifically, if each word was

[05:44] equally likely to be the answer, the probability of hitting this pattern would be 58 divided by around 13,000. Of course, they're not equally likely to obscure and even questionable words. But at least for our first pass at all of

[05:58] equally likely and then refine that a bit later. The point is the pattern with a lot of information is by its very nature unlikely to occur. In fact, what it means to be informative is that it's unlikely.

[06:11] A much more probable pattern to see with this opening would be something like this, where of course there's not a W in it. Maybe there's an E, and maybe Y. In this case, there were 1,400 possible

[06:24] it works out to be a probability of about 11% that this is the pattern you would see. So the most likely outcomes are also the least informative. show you the full distribution of probabilities across all of the

[06:39] different patterns that you might see. So each bar that you're looking at corresponds to a possible pattern of colors that could be revealed, of which And they're organized from left to right, most common to least common.

[06:52] So the most common possibility here is that you get all grays. That happens about 14% of the time. And what you're hoping for when you make a guess is that you end up somewhere out in this long tail, like over here where

[07:04] there's only 18 possibilities for what matches this pattern that evidently look Or if we venture a little farther to the left, you know, maybe we go all the way Okay, here's a good puzzle for you. What are the three words in the English

[07:17] language that start with a W, end with a Y, and have an R somewhere in them? see. Wordy, wormy, and Riley. So to judge how good this word is overall, we want some kind of measure of

[07:31] the expected amount of information that you're going to get from this pattern and we multiply its probability of occurring times something that measures how informative it is, that can maybe give us an objective score.

[07:45] Now, your first instinct for what that something should be might be the number of matches. You know, you want a lower average number of matches. But instead, measurement that we often ascribe to information and one that will be more

[07:58] probability assigned to each of these 13,000 words for whether or not they're 13,000 words for whether or not they're actually the answer.

[08:12] formula but is really intuitive if we just look at examples. If you have an observation that cuts your space of possibilities in half, we In our example, the space of possibilities is all possible words and

[08:26] five-letter words have an S, a little less than that but about half. So, that observation would give you one bit of information. space of possibilities by a factor of four, we say that it has two bits of

[08:40] information. For example, it turns out about a quarter of these words have a T. factor of eight, we say it's three bits of information and so on and so forth. Four bits cuts it into a 16th, five bits cuts it into a 32nd.

[08:54] moment and pause and ask for yourself, what is the formula for information, for the number of bits, in terms of the probability of an occurrence? basically that when you take 1/2 to the number of bits, that's the same thing as

[09:08] as saying two to the power of the number of bits is one over the probability, information is the log base two of one divided by the probability. rearrangement still where the information is the negative log base two

[09:23] Expressed like this, it can look a little bit weird to the uninitiated but it really is just a very intuitive idea of asking how many times you've cut down your possibilities in half. Now, if you're wondering, you know, I

[09:36] game, why are logarithms entering the picture? One reason this is a nicer unit very unlikely events. Much easier to say that an observation has 20 bits of probability of such and such occurring is 0.00000095.

[09:54] logarithmic expression turned out to be a very useful addition to the theory of probability is the way that information adds together. For example, if one information, cutting your space down by four, and then a second observation,

[10:07] like your second guess in Wordle, gives you another three bits of information, chopping you down further by another factor of eight, the two together give same way that probability likes to multiply, information likes to add.

[10:21] something like an expected value, where we're adding a bunch of numbers up, the Let's go back to our distribution for weary and add another little tracker on here showing us how much information there is for each pattern. The main

[10:35] higher the probability, as we get to those more likely patterns, the lower gain. The way we measure the quality of this guess will be to take the expected value of this information. Where we go through

[10:48] each pattern, we say, how probable is it? And then we multiply that by, how many bits of information do we get? And in the example of weary, that turns out to be 4.9 bits. So, on average, the information you get from this opening

[11:00] guess is as good as chopping your space of possibilities in half about five times. By contrast, an example of a guess with a higher expected information guess with a higher expected information value would be something like slate.

[11:13] distribution looks a lot flatter. In particular, the most probable occurrence of all grays only has about a 6% chance of occurring. So, at minimum, you're getting evidently 3.9 bits of information. But that's a minimum. More

[11:26] than that. And it turns out, when you crunch the numbers on this one and you add up all of the relevant terms, the average information is about 5.8. So, in contrast with weary, your space of possibilities will be about half as

[11:41] big after this first guess, on average. There's actually a fun story about the name for this expected value of information quantity. You see, Claude Shannon, who was working at Bell Labs in the 1940s, but he was talking

[11:54] ideas with John von Neumann, who was this intellectual giant of the time, very prominent in math physics and the beginnings of what was becoming computer didn't really have a good name for this expected value of information quantity,

[12:08] von Neumann supposedly said, so the story goes, "Well, you should call it entropy." And for two reasons. In the first place, your uncertainty function under that name, so it already has a name. And in the second place, and more

[12:21] important, nobody knows what entropy really is. So, in a debate, you'll So, if the name seems a little bit mysterious, and if the story is to be believed, that's kind of by design. Also, if you're wondering about its

[12:34] thermodynamics stuff from physics, there definitely is a connection, but in its origins, Shannon was just dealing with pure probability theory. And for our entropy, I just want you to think the expected information value of a

[12:48] particular guess. You can think of entropy as measuring two things simultaneously. The first one is how flat is the distribution. The closer a distribution is to uniform, the higher that entropy will be. In our

[13:01] case, where there are three to the fifth total patterns, for a uniform distribution, observing any one of them would have information log base two of three to the fifth, which happens to be 7.92.

[13:13] you could possibly have for this entropy. But, entropy is also kind of a are in the first place. For example, if you happen to have some word where there's only 16 possible patterns, and each one is equally likely. This

[13:28] entropy, this expected information, would be four bits. But, if you have patterns that could come up, and they're all equally likely, then the entropy would work out to be six bits. So, if you see some distribution out in

[13:42] the wild that has an entropy of six bits, it's sort of like it's saying there's as much variation and uncertainty in what's about to happen as outcomes. For my first pass at the Wordle bot, I

[13:56] basically had it just do this. It goes through all of the different possible guesses that you could have, all 13,000 words. It computes the entropy for each one, or more specifically, the entropy of the distribution across all patterns

[14:08] that you might see for each one, and then it picks the highest, since that's space of possibilities as much as possible. about the first guess here, it does the same thing for the next few guesses. For

[14:21] that first guess, which would restrict you to a smaller number of possible words based on what matches with that, you just play the same game with respect proposed second guess, you look at the distribution of all patterns that could

[14:35] words. possibilities, and you find the one that maximizes that entropy. let me just pull up a little variant of Wordle that I wrote that shows the

[14:50] margins. So, after doing all its entropy showing us which ones have the highest expected information. Turns out the top answer, at least at the moment, we'll refine this later, is "tares",

[15:04] um, of course, "avetch", the most common Each time we make a guess here, where maybe I kind of ignore its recommendations and go with "slate" cuz I like slate. We can see how much

[15:17] the right of the word here, it's showing us how much actual information we got given this particular pattern. So, here it looks like we were a little unlucky. happened to get something with less than that. And then on the left side here,

[15:31] it's showing us all of the different possible words given where we are now. The blue bars are telling us how likely it thinks each word is. So, at the equally likely to occur, but we'll refine that in a moment.

[15:43] And then this uncertainty measurement is telling us the entropy of this distribution across the possible words, which right now, because it's a uniform distribution, is just a needlessly complicated way to count the number of

[15:55] possibilities. For example, if we were to take 2 to the power of 13.66, that should be around the 13,000 possibilities. Um a little bit off here, but only because I'm not showing all the decimal places. At the moment, that

[16:07] overly complicating things, but you'll see why it's useful to have both numbers suggesting the highest entropy for our second guess is ramen, which again just second guess is ramen, which again just really doesn't feel like a word. So,

[16:21] to take the moral high ground here, I'm going to go ahead and type in reins. little unlucky. We were expecting 4.3 bits, and we only got 3.39 bits of So, that takes us down to 55 possibilities.

[16:34] with what it's suggesting, which is cambu, whatever that means. And okay, this is actually um a good chance for a puzzle. It's telling us this pattern gives us 4.7 bits of information. But over on the left, before we see that

[16:48] pattern, there were 5.78 bits of uncertainty. So, as a quiz for you, what does that mean about the number of remaining possibilities? Well, it means that we're reduced down to one bit of uncertainty, which is the

[17:01] same thing as saying that there's two possible answers. It's a 50/50 choice. which words are more common, we know that the answer should be abyss, but as doesn't know that. So, it just keeps going trying to gain as much information

[17:15] as it can until it's only one possibility left and then it guesses it. strategy, but let's say we call this version one of our Wordle solver and then we go and run some simulations to see how it does.

[17:31] playing every possible Wordle game. It's going through all of those 2315 words that are the actual Wordle answers. It's basically using that as a testing set. considering how common a word is and just trying to maximize the information

[17:46] at each step along the way until it gets down to one and only one choice. average score works out to be about 4.124, which you know, it's not bad to be honest. I kind of expected to do worse,

[17:59] you that they can usually get it in four. The real challenge is to get as many in three as you can. It's a pretty big jump between the score of four and The obvious low-hanging fruit here is to somehow incorporate whether or not a

[18:11] word is common and how exactly do we do that?

[18:24] of the relative frequencies for all of the words in the English language. And I just used Mathematica's word frequency data function, which itself pulls from the Google Books English Ngram public data set. And it's kind of fun to look

[18:36] most common words to the least common words, evidently these are the most common five-letter words in the English language. Or rather, these is the eighth most common. First is which, after which there's there and there. First itself is

[18:49] not first, but ninth and it makes sense that these other words could come about more often. Where those after first are after, where and those being just a little bit less common. Now, in using this data to model how

[19:01] final answer, it shouldn't just be proportional to the frequency cuz, for proportional to the frequency cuz, for example, which is given a score of 0.002 in this data set, whereas the word braid is in some sense about a thousand times

[19:14] common enough words that they're almost certainly worth considering. So we want more of a binary cut-off. The way I went about it is to imagine taking this whole sorted list of words and then arranging it on an x-axis and

[19:28] which is the standard way to have a function whose output is basically binary. It's either zero or it's one, but there's a smoothing in between for So essentially the probability that I'm assigning to each word for being in the

[19:42] final list will be the value of the sigmoid function above wherever it sits Now, obviously this depends on a few parameters. For example, how wide a space on the x-axis those words fill determines how gradually or steeply we

[19:57] drop off from one to zero. And where we situate them left to right honest, the way I did this was kind of just licking my finger and sticking it sorted list and tried to find a window where when I looked at it I figured,

[20:11] more likely than not to be the final answer." and used that as the cut-off. Now, once we have a distribution like this across the words, it gives us another situation where entropy becomes this really useful measurement. For

[20:24] game and we start with my old openers, which were other and nails, and we end up with a situation where there's four possible words that match it. And let's say we consider them all equally likely. Let me ask you, what is the entropy of

[20:38] this distribution? Well, the information associated with each one of these possibilities is going to be the log base two of four, since It's two bits of information, four possibilities. All very well and good.

[20:54] But what if I told you that actually there's more than four matches? In reality, when we look through the full word list, there are 16 words that match it. But suppose our model puts a really low probability on those other 12 words

[21:06] Something like one in a thousand cuz they're really obscure. Now, let me ask you, what is the entropy of this distribution? If entropy was purely measuring the number of matches here, then you might

[21:19] expect it to be something like the log base two of 16, which would be four, two more bits of uncertainty than we had before. But of course, the actual from what we had before cuz just because there's these 12 really obscure words,

[21:32] more surprising to learn that the final answer is charm, for example. here and you add up the probability of each occurrence times the corresponding each occurrence times the corresponding information, what you get is 2.11 bits.

[21:46] bits. It's basically those four possibilities, but there's a little more uncertainty because of all of those highly unlikely events. Though, if you information from it. So, zooming out, this is part of what

[21:58] makes Wordle such a nice example for an information theory lesson. We have these two distinct-feeling applications for entropy. The first one telling us what's the expected information we'll get from a given guess. And the second one

[22:10] saying, can we measure the remaining uncertainty among all of the words that And I should emphasize in that first case where we're looking at the expected unequal weighting to the words, that

[22:23] example, let me pull up that same case we were looking at earlier of the distribution associated with weary, but this time using a non-uniform distribution across all possible words. So, let me see if I can find a part here

[22:36] So, let me see if I can find a part here that illustrates it pretty well. we have two adjacent patterns that are about equally likely, but one of them we're told has 32 possible words that match it. And if we check what they are,

[22:50] these are those 32, which are all just very unlikely words. As you scan your find any that feel like plausible answers. Maybe yells? But if we look at distribution, which is considered just about as likely, we're told that it only

[23:05] quarter as many matches, but it's about as likely. And when we pull up those matches, we can see why. Some of these are actual plausible answers, like ring or wrath or wraps. To illustrate how we incorporate all

[23:19] that, let me pull up version two of the Wordle bot here, and there are two or one that we saw. First off, like I just said, the way that we're computing these entropies, these expected values of information, is now using the more

[23:32] patterns that incorporates the probability that a given word would actually be the answer. Uh as it happens, tears is still number one, though the ones following are a bit different. Second, when it ranks its top

[23:45] the probability that each word is the actual answer, and it'll incorporate that into its decision, which is easier to see once we have a few guesses on the Again, ignoring its recommendation because we can't let machines rule our

[23:59] and I suppose I should mention another thing different here is over on the left, that uncertainty value, that number of bits, is no longer just matches. Now, if we pull it up and you

[24:11] know, we calculate, say, 2 to the 8.02, which should be a little above 256, I guess uh 259, what it's saying is even though there are 526 total words that actually match this pattern, the amount of uncertainty it has is more akin to

[24:25] what it would be if there were 259 equally likely outcomes. You can think of it like this. It knows borks is not the answer, same with yorts less uncertain than it was in the previous case. This number of bits will

[24:38] And if I keep playing the game, I'm refining this down with a couple guesses that are apropos of what I would like to explain here.

[24:50] its top picks, you can see it's no longer just maximizing the entropy. seven possibilities, but the only ones with a meaningful chance are dorms and words. And you can see it ranks choosing both of those above all of these other

[25:03] values that strictly speaking would give more information. added up these two numbers to measure the quality of each guess, which suspect. But it really didn't feel systematic, and I'm sure there's other

[25:16] the one I landed on. If we're considering the prospect of a next guess, like in this case words, what we really care about is the expected score of our game if we do that. And to calculate that expected score, we say

[25:30] what's the probability that words is the actual answer, which at the moment it describes 58% to. We say with a 58% chance, our score in this game would be And then with the probability of one minus that 58%, um our score will be

[25:44] How much more we don't know, but we can estimate it based on how much uncertainty there's likely to be once we get to that point. Specifically, at the moment there's 1.44 bits of uncertainty. If we guess words, it's telling us the

[25:57] expected information we'll get is 1.27 bits. So if we guess words, this difference represents how much uncertainty we're likely to be left with after that happens. What we need is some kind of function, which I'm calling F

[26:10] here, that associates this uncertainty with an expected score. And the way I went about this was to just plot a bunch of the data from previous games based on version one of the bot to say, "Hey, what was the actual score after various

[26:23] points with certain very measurable amounts of uncertainty?" For example, these data points here that are sitting above a value that's around like 8.7 or so are saying for some games after a point at which there were 8.7 bits of

[26:35] uncertainty, it took two guesses to get the final answer. For other games it took three guesses. For other games it took four guesses. the points over zero are saying whenever there's zero bits of uncertainty, which

[26:48] is to say there's only one possibility, then the number of guesses required is always just one, which is reassuring. Whenever there was one bit of just down to two possibilities, then sometimes it required one more guess,

[27:01] sometimes it required two more guesses, and so on and so forth here. Maybe a slightly easier way to visualize this data is to bucket it together and For example, this bar here is saying among all the points where we had one

[27:14] bit of uncertainty, on average the number of new guesses required was about number of new guesses required was about 1.5. point the uncertainty was a little above four bits, which is like narrowing it

[27:29] down to 16 different possibilities, then on average it requires a little more forward. And from here I just did a regression to fit a function that seemed reasonable to this. And remember the whole point of doing any of that is so

[27:42] that we can quantify this intuition that the more information we gain from a be. So, with this as version 2.0, if we go back and we run the same set of simulations having it play against all

[27:55] 2,315 possible Wordle answers, how does it do? it's definitely better, which is reassuring. All said and done, the average is around 3.6. Although, unlike the first version, there are a couple

[28:08] times that it loses and requires more than six in this circumstance, it's making that trade-off to actually go for the goal rather than maximizing information. So, can we do better than 3.6?

[28:21] We definitely can. Now, I said at the start that it's most fun to try not answers into the way that it builds its model. But, if we do incorporate it, the best performance I could get was around 3.43.

[28:35] than just using word frequency data to choose this prior distribution, this 3.43 probably gives a max at how good we good I could get with that. That best performance essentially just uses the

[28:48] but it goes a little farther. Like it does a search for the expected information two steps forward rather than just one. Originally I was planning realize we've actually gone quite long as it is. The one thing I'll say is

[29:01] then running a couple sample simulations in the top candidates, so far for me at least it's looking like crane is the best opener. Who would have guessed? Also, if you use the true word list to determine your space of possibilities,

[29:14] then the uncertainty you start with is a little over 11 bits. And it turns out just from a brute force search, the maximum possible expected information after the first two guesses is around 10 bits.

[29:26] Which suggests that best case scenario, after your first two guesses with perfectly optimal play, you'll be left with around one bit of uncertainty. Which is the same as being down to two possible guesses. But I think it's fair

[29:38] that you could never possibly write an algorithm that gets this average as low available to you, there's simply not room to get enough information after only two steps to be able to guarantee the answer in the third slot every

[29:52] the answer in the third slot every single time without fail.