grantsanderson
Solving Wordle using information theory
synopsis
The video builds a Wordle solver around entropy, the expected number of bits a guess will reveal. A version that also weights common words and trades information against the chance of winning now averages about 3.6 guesses. Under perfect play an average of 3 is out of reach, because two guesses cannot supply the roughly 11 bits needed.
Scoring a guess. Rules of thumb like "hit frequent letters" ignore letter position, so he wants a number. Hitting a rare W with "weary" can cut about 13,000 allowed words to 58, but informative patterns are by nature unlikely. Information is defined as log₂(1/p), the count of halvings. Averaging it over all 243 patterns gives the guess's entropy: 4.9 bits for "weary", 5.8 for "slate".
Version one. The first bot picks the highest-entropy guess at every step, with every word equally likely. Over the 2,315 real answers it averages 4.124. It plays the endgame poorly, chasing information even when two candidates remain.
Weighting common words. A sigmoid over Google Books frequency rankings gives each word a probability of being the answer. Entropy then also measures the uncertainty that remains: four plausible words among sixteen matches come to 2.11 bits, not 4.
Version two. For each candidate, the bot weighs the probability that it is the answer (58% for "words" in the example) against the uncertainty left if it is not. The remaining guesses come from a function fitted by regression to version-one games; one bit, for example, needed about 1.5 more guesses on average. The average falls to about 3.6, with occasional losses.
The ceiling. Using the true answer list and a two-step search, he reaches about 3.43, with "crane" as the best opener. Two guesses yield at most about 10 bits, which leaves about one bit of uncertainty.
- Information measures surprise: count how many times possibilities are halved. An observation with probability p carries log₂(1/p) bits, so a fact true of about half of five-letter words (containing an S) is 1 bit and one true of a quarter (a T) is 2. The log is used because information adds where probabilities multiply: a 2-bit guess followed by a 3-bit guess gives 5 bits.
- A guess is scored by its entropy, the expected information over patterns. Each of the 3⁵ = 243 colour patterns is weighted by its probability times its bits. "Weary" gets 4.9 bits, since all-grey turns up about 14% of the time; "slate" gets 5.8, with all-grey at about 6%. Entropy rewards a flat distribution and many outcomes; a uniform spread over all 243 patterns would give the 7.92-bit maximum.
- The same entropy measures remaining uncertainty once common words are weighted. He builds a prior from Google Books word frequencies, passed through a sigmoid on the sorted list so that common words all count as plausible rather than in proportion to frequency. Four likely words plus twelve one-in-a-thousand words give 2.11 bits, not 4. Likewise 526 matches at 8.02 bits behave like about 259 equally likely answers.
- Maximising information alone loses to minimising the expected score. The pure entropy bot averaged 4.124 guesses over all 2,315 real answers. Version 2 adds the chance of winning outright: "words", at 58% likely, is valued as a win on that guess, otherwise as a later finish. The extra guesses are estimated by a function fitted to version-1 games. It averages about 3.6, but occasionally needs more than six.
- Two guesses cannot supply enough information to average three. Using the true answer list and a two-step lookahead, his best average was about 3.43, and "crane" came out as the best opener. The list starts with a little over 11 bits of uncertainty, but brute force finds at most about 10 bits from two guesses. That leaves about one bit, so he argues an average of 3 is unreachable.