Priors, two-step search, and what "optimal" actually means

Transcript: this stretch, timestamped

The previous page built a scoring rule for guesses: bucket the remaining candidates by the colour pattern a guess would produce, read the bucket sizes as a probability distribution, and take its entropy. That rule got a working bot averaging about 4.1 guesses. This page is where the model stops pretending all words are equally likely and starts being honest — first about the answer distribution, then about the objective itself. It closes with the measured numbers and a bound on how well any algorithm could ever do, and it hands off to P18, where Grant finds the bug that moves those numbers.

Outline, with timestamps

• 17:48 — Where we left off: version 1 averages about 4.124 guesses, and the obvious missing ingredient is how common a word is.
• 18:23 — A prior from data: relative word frequencies via Mathematica's WordFrequencyData, itself drawn from the Google Books English Ngram corpus.
• 19:23 — The soft cut-off: lay the frequency-sorted list along an axis and read the prior off a sigmoid.
• 20:56 — The toy case: sixteen words match, but twelve of them are junk with probability about one in a thousand.
• 21:27 — The weighted entropy comes out at 2.11 bits — essentially the four-word answer, not the sixteen-word one.
• 22:27 — Two adjacent patterns of nearly equal probability, one of them holding 32 words that are all implausible.
• 24:29 — By the fourth guess the bot openly stops maximising entropy and plays a candidate answer instead.
• 25:30 — The expected-score arithmetic: 58% chance of ending now, 1.44 bits of uncertainty, 1.27 bits expected gain.
• 26:00 — Fitting f: turning "bits of remaining uncertainty" into "guesses still to come".
• 28:01 — Version 2 averages about 3.6 — and, unlike version 1, it sometimes loses.

Why a uniform prior is simply the wrong model

The version-1 bot treats every one of the roughly 13,000 allowed guesses as an equally likely answer. That is not a neutral or conservative choice; it is a false one, and you can see it losing games. The allowed list exists so the game can be permissive about what you type — it is padded with Scrabble-dictionary detritus. The answers, by contrast, were hand-picked by a person to be words a normal player would recognise. A model that assigns the same probability to a common noun and to a five-letter string nobody has said out loud since 1890 will spend guesses distinguishing between possibilities that were never live.

You can watch it cost him a game. Version 1 narrows to two candidates, one of which any human would instantly discount, and still refuses to gamble — it keeps harvesting information until exactly one possibility remains. That is optimal play for the game it thinks it is in, and wasteful for the game actually in front of it.

So the fix is a prior: a probability p(w) that word w is the sort of word this game uses as an answer. The self-imposed constraint of the project is that this prior must not be built from the real answer list — that list is sitting in the page source in day order, so using it is both cheating and boring. The prior has to come from outside the game. Grant uses relative word frequency, pulled through Mathematica's WordFrequencyData, which is itself built on the Google Books English Ngram corpus (18:23).

From a frequency ranking to a probability: the soft cut-off

The obvious move — make the prior proportional to the frequency — is wrong, and it is worth being precise about why. Word frequencies are roughly Zipfian: they span orders of magnitude. In this dataset which scores about 0.002, while braid is roughly a thousand times rarer (18:53). But braid is not a thousand times less likely to be a Wordle answer — it is a perfectly ordinary word, and the curator would happily have used it. Frequency is a good ordering of plausibility and a terrible scale for it. What we actually believe is close to binary: above some fuzzy familiarity threshold a word is a candidate, below it it is not.

So use the ranking, discard the magnitudes. Sort all the allowed words by frequency, lay them out evenly along an x-axis, and define the prior as the logistic function evaluated at each word's position:

p(w) = σ(x_w),   σ(x) = 1 / (1 + e^(−x))

x_w = evenly spaced over an interval of width W,
      positioned so that the n most common words land at x > 0

Two parameters control everything. W, the width of the interval, sets how sharp the cut-off is — a narrow window makes the sigmoid a near step function, a wide one makes it a gentle ramp. The horizontal offset sets where the cut-off falls, i.e. how many words are counted as answer-plausible. In the published code the values are W = 10 and n = 3000, chosen the way Grant describes with admirable frankness:

"And to be honest, the way I did this was kind of just licking my finger and sticking it into the wind."— Grant Sanderson, 19:55

He scrolled the sorted list until he found a window where about half the words looked more likely than not to be answers, and put the cut-off there — a defensible way to set a hyperparameter you have one noisy signal about.

My addition, from the repository code rather than the video: with the roughly 12,970 frequency-ranked words, W = 10 and n = 3000, the interval runs from roughly x = −7.69 to x = +2.31, and the arithmetic works out like this.

Note the ceiling: even the most common word gets 0.91, not 1. That is a side effect of a symmetric squash on a finite interval, and it does no harm — these numbers are normalised into a distribution before use, so only their ratios matter.

What the prior does to the entropy calculation

Under a uniform prior, the probability of seeing pattern k after guessing g is just a count: how many surviving candidates fall in bucket k, over how many survive in total. With a prior it becomes a weighted sum. Normalise the priors over the surviving candidates to get weights w(a), then

P(pattern = k | guess g) = Σ_{a : pattern(g,a) = k} w(a)

H(g) = Σ_k P(k)·log₂(1/P(k))

Same formula, different bucket masses. Twelve junk words in a bucket now contribute about as much as one plausible word does. And this changes both of the ways entropy is used in this project, which are worth keeping separate in your head (21:57): the entropy of the pattern distribution scores a candidate guess (expected information gained), while the entropy of the weight distribution over surviving words measures how much uncertainty is left. Under a uniform prior the second is a needlessly baroque way of writing log₂(number of candidates). Under a real prior it stops being redundant and starts being informative.

The clean demonstration is the toy case at 20:25. Four equally likely candidates give log₂4 = 2 bits exactly. Now reveal that sixteen words actually match, the extra twelve being obscurities each carrying probability about 0.001. A count-based reading says log₂16 = 4 bits — the uncertainty has doubled. It has not. Work it through: the twelve junk words take 0.012 of the mass, the four real ones split the remaining 0.988 at 0.247 each, and

H = 4 · 0.247 · log₂(1/0.247)  +  12 · 0.001 · log₂(1/0.001)
  = 4 · 0.247 · 2.0174         +  12 · 0.001 · 9.9658
  = 1.993                      +  0.120
  = 2.11 bits

which is the figure Grant reports (21:27). The video gives the junk probability only as "something like one in a thousand"; taking that literally, as an absolute probability rather than a ratio, reproduces his 2.11 exactly — that reading of the numbers is mine. The junk adds a tenth of a bit, not two bits. That tenth is real and correctly priced: those outcomes are wildly surprising, so if one occurred you would learn a great deal, but you should barely brace for it. This is exactly the trade-off p·log₂(1/p) is built to make, and it is why entropy — rather than "number of possibilities" — is the right meter once the possibilities are not equally likely.

The same effect shows up in the real bot in two places. In the pattern distribution for a guess, two neighbouring patterns can be about equally probable while one covers 32 matching words (22:27) and the other only 8 (22:57) — because the 32 are all implausible strings while the 8 include real candidates. And in the remaining-uncertainty readout: at one point 526 words formally match the pattern on the board, but the weighted entropy is 8.02 bits, and 2^8.02 ≈ 259 (23:59). The bot is as uncertain as it would be facing 259 equally likely answers, because it knows a couple of hundred of those 526 strings are not the kind of thing anyone puts in a puzzle. Reading 2^H as an effective number of possibilities — the perplexity — is the right intuition, and it is only interesting once the distribution is non-uniform.

The proxy and the objective

Here is the conceptual heart of the whole stretch, and the part most worth carrying away from the video.

Maximising expected information was never the goal. The goal is minimising the expected number of guesses. Information maximisation is a proxy — a good one, because bits are roughly fungible with guesses, but a proxy. And you can say exactly where it fails.

Entropy scores a guess purely by the shape of the partition it induces on the candidate set. It is blind to which bucket contains the answer, and in particular it gives no credit for the one outcome that matters most: the all-green pattern, which does not merely narrow the search, it ends the game. A word that cannot possibly be the answer will never produce that outcome. A word that has a 58% chance of being the answer produces it 58% of the time. To entropy, those two guesses are comparable on partition quality alone — so a pure information maximiser will cheerfully play a non-answer word that splits the space beautifully, forgoing a coin-flip-or-better chance of just winning. You can watch this happen: by the fourth guess of a version-2 game there are technically seven possibilities but only two with meaningful probability, and the bot ranks those two above alternatives that would strictly yield more information (24:29).

The first fix Grant tried was to add the two numbers — entropy plus probability-of-being-the-answer — which worked better than it has any right to but is not derived from anything (24:59). The principled version is to write down the expected score directly. Let p(g) be the probability that guess g is the answer, H₀ the current uncertainty in bits, H(g) the expected information the guess yields, and f a function taking bits of remaining uncertainty to expected guesses still needed. Then, counting from now:

E[guesses from here | g] = p(g)·1  +  (1 − p(g))·(1 + f(H₀ − H(g)))

Read it left to right: with probability p(g) this guess is the answer and costs one guess, full stop. Otherwise it costs one guess and leaves you facing H₀ − H(g) bits of residual uncertainty, which will cost about f of that more. Pick the g minimising this. The video walks a concrete instance (25:30): p = 0.58, H₀ = 1.44 bits, H(g) = 1.27 bits, so the residual is 0.17 bits — very nearly a certainty either way.

Turning bits into guesses: fitting f

That leaves f. It is not derived; it is fit to data (26:00). Grant ran the version-1 bot over many games, and at every point in every game recorded a pair: how many bits of uncertainty remained, and how many further guesses the game actually took. Scatter those. At zero bits the answer is always one more guess, which is a reassuring sanity check on the whole apparatus. At one bit — two live possibilities — it is sometimes one more, sometimes two (26:31). Bucket by bits and average: one bit gives about 1.5 further guesses; a little over four bits, roughly sixteen possibilities, gives a little over two (27:01). Then regress a reasonable curve through it (27:31).

My addition: the published code makes the fitted shape explicit, and it is more interpretable than "a regression". It is an analytic floor plus a linear correction:

f(H) = [ 2^(−H) + 2·(1 − 2^(−H)) ]  +  1.5·H / 11.5
     =   2 − 2^(−H)                 +  1.5·H / 11.5

The bracketed term is the expected score under the optimistic assumption that you will certainly finish on the guess after next: treat H bits as 2^H equally likely options, so you win immediately with probability 2^(−H) and otherwise need two. That is a genuine lower bound. The linear term is the fudge that admits you usually will not, calibrated by a single anchor point — the constants make f(11.5) ≈ 3.5, matching the observed average score from a full-uncertainty start. Sanity-check it against the video's reported bucket averages:

It slightly overestimates at one bit and is otherwise in the right place. Feeding the earlier instance through it: residual 0.17 bits gives f = 1.13, so the expected cost from that point is 0.58·1 + 0.42·(1 + 1.13) = 1.48 further guesses — a total expected score of about 4.48, since three guesses were already spent.

Two-step lookahead, and what it costs

The last refinement is depth. Everything so far is greedy: score each guess by what happens on the next turn only. Two-step lookahead scores a guess by simulating one turn further — for each pattern the guess might produce, work out what the best follow-up would be in that bucket, and average the resulting scores over the pattern distribution (28:31).

The cost is easy to estimate and worth doing, because it explains why the video does not go further. One greedy pass compares every allowed guess against every surviving candidate: about 13,000 × 2,300 ≈ 3·10⁷ pattern evaluations. Looking one step deeper multiplies that by the number of first guesses you expand — a full two-step search over all first guesses is another factor of 13,000, around 4·10¹¹ evaluations. The code sidesteps this by expanding only the top 25 candidates from the greedy pass, making the search roughly 25× a greedy pass instead of 13,000×. A source comment on the two-step routine notes it is slow and could be optimised, and asks, reasonably, why bother. Three steps would be another factor of thousands, for a payoff that is already thin at two.

The general point: lookahead in this game buys a little, and the greedy-plus-expected-score rule is close enough that most of the remaining gap is not about depth at all. It is about the prior.

The measured numbers — and the asterisk on all of them

All figures below are simulated over the full official answer list used as a test set, and all of them changed in the follow-up video. They are reported here as the video reported them.

Two things to notice. First, v2 sometimes loses — takes more than six guesses — which v1 never did. That is not a regression, it is the objective working as designed: a rule that trades information for a chance of winning now will occasionally take the gamble and lose it. Optimising the mean buys you a worse tail. Second, the jump from 3.6 to 3.43 conflates two separate changes — swapping the frequency prior for the true answer list, and adding lookahead. The video does not isolate them, so do not attribute that 0.17 to two-step search.

Finally, a genuine bound, and the nicest bit of reasoning in the stretch (29:01). Starting from the true answer list, the initial uncertainty is a little over 11 bits — indeed log₂(2315) = 11.18. A brute-force search puts the maximum expected information obtainable from the first two guesses at about 10 bits. So even under perfect play you expect roughly one bit left after two guesses: two live possibilities, a coin flip, on average. Some of those flips go wrong, so you cannot always finish on the third.

"I think it's fair and probably pretty conservative to say that you could never possibly write an algorithm that gets this average as low as three."— Grant Sanderson, 29:32

That is an information-theoretic argument about a word game, and it holds regardless of the bug: it depends only on the entropy of the answer list and the best achievable two-guess information, not on the simulation harness. Exhaustive decision-tree searches by others have since landed close to the 3.4 region, which is consistent with the bound and a long way from three.

Where people get stuck

"The prior is just word frequency, so common words are more likely answers." Not quite — the prior is a function of frequency rank, deliberately flattened. Two words a thousand-fold apart in corpus frequency can get near-identical priors if both sit above the cut-off. The sigmoid's whole job is to destroy the magnitude information and keep only the ordering, because the thing being modelled ("would a human curator pick this?") is close to a threshold decision, not a proportionality.

"More matching words means more uncertainty." Only under a uniform prior. Once words carry weight, entropy measures effective possibilities, not possibilities: 526 formal matches can carry 8.02 bits, the same uncertainty as 259 equally likely ones. If you want a count, use 2^H, and remember it is generally not an integer and does not correspond to any particular subset of words.

"Maximising information and minimising guesses are the same thing." They agree on every guess that cannot be the answer, and disagree exactly on the ones that can — see the callout above. If you only ever remember one thing from this page, make it that. The failure is not a bug in the entropy calculation; entropy is computing precisely what it claims to. It is a mismatch between what was measured and what was wanted.

"So f is part of the theory." It is not. f is an empirical curve fit to one bot's simulated games, with a hand-set anchor. It is the least principled component in the system, and it is doing load-bearing work in every comparison the bot makes. If you rebuild this, that is the first thing to replace — with a proper dynamic-programming value function over the candidate set, at which point you are no longer approximating and no longer need entropy as a proxy at all.

"These are the real numbers." They are the numbers as first published. The colouring rule for guesses containing a repeated letter was subtly wrong, which perturbed bucket membership in a small fraction of cases and therefore every downstream statistic. See P18.

Going deeper, verified

• Code for the Wordle video — Grant Sanderson (2022) · simulations.py is the whole argument in 900 lines; read get_frequency_based_priors, entropy_to_expected_score and get_expected_scores in that order.
• Wordle solver improvements — addendum — 3Blue1Brown (2022) · the bug, the corrected conclusion, and more detail on how the opening guess was chosen. Covered on P18.
• Optimal Wordle Solutions — Jonathan Olson (2022) · explicit decision trees rather than a greedy heuristic; reports solving 99% of puzzles within four guesses at an average around 3.42, which is the right yardstick for "optimal" here.
• The best strategies for Wordle — sonorouschocolate.com (2022) · exhaustive-search notes on optimal play, linked from Grant's addendum; useful for seeing how much machinery genuine optimality requires.
• WordFrequencyData — Wolfram Language reference · the exact source of the frequency numbers, and worth skimming for what a corpus frequency does and does not measure.

Exercises

1. Reproduce 2.11 bits, then break it — Confirm the toy calculation: four candidates sharing 0.988 of the mass and twelve at 0.001 each give H = 2.113 bits. Now sweep the junk probability from 10⁻⁶ to 1/16 and plot H. A good answer identifies the value at which H reaches 3 bits and explains why the curve is so flat at the low end — the p·log₂(1/p) term vanishes faster than log₂(1/p) grows.
2. Find the disagreement — Build the smallest endgame where the two rules split. Three candidates remain: one with probability p, the other two with (1−p)/2 each. Option A is to guess the top candidate, which wins outright with probability p and otherwise leaves the other two indistinguishable. Option B is a non-candidate word that separates all three perfectly. Information maximisation always picks B. Using f(H) = 2 − 2^(−H) + 1.5H/11.5, show that B has expected cost exactly 2 for every p, write A's expected cost as a function of p, and solve numerically for the crossover. A good answer reports a threshold near p ≈ 0.31 and says in one sentence why the rules can never disagree when p = 0.
3. Cost out the third step — Given roughly 13,000 allowed guesses and 2,300 candidates, count pattern evaluations for greedy, for two-step over the top 25, and for a full three-step search over the top 25 first guesses and top 25 second guesses per bucket. A good answer gives three orders of magnitude and one sentence on which of them is feasible on a laptop, plus a note on how precomputing the full guess-by-candidate pattern matrix changes the picture.