Mastermind: reproducing the 5,625-guess optimum in two minutes of TypeScript, and why the entropy strategy's published score is a floating-point tie

I built Mastermind in the browser — four pegs, six colours, repeats allowed, 1,296 possible secrets — with five classic one-step strategies and an exact optimal one built in. The side panel shows, at every move, how many codes are still possible and what each strategy would play next.

Two results came out of it:

• A plain depth-first branch and bound in TypeScript finds Koyama and Lai's 1993 optimum — 5,625 guesses over all secrets, mean 4.3403 — in 107.9 seconds on one core. It also matches all 27 cells of Ville's 2013 table of optima that it was run on, and adds a few that are not in that table.
• Replaying the one-step strategies against every secret reproduces the published totals for Knuth (5,801), Irving (5,696) and Kooi (5,668). The entropy strategy does not match: 5,722 here against a published 5,723, and 11,378 against 11,382 on the seven-colour game. The gap is floating-point rounding. The strategy's score has hundreds of exact ties, and the order in which you add p log p decides who wins them.

Demo: https://sen.ltd/portfolio/mastermind/ · Source: https://github.com/sen-ltd/mastermind

The rules

• The code maker picks 4 pegs from 6 colours. Repeats are allowed, so there are 6⁴ = 1,296 secrets.
• After each guess the answer is one black for every peg of the right colour in the right place, and one white for every further peg whose colour is in the secret, with repeats counted only as often as they occur in both.
• Four blacks ends the game. Fewer guesses is better.
• There are 14 possible answers. Three blacks and one white can't happen.

Grading is a few lines, and it is worth tabulating once: a 1,296 × 1,296 Uint8Array of answer indices turns everything after it into table lookups.

let black = 0;
for (let k = 0; k < p; k++) {
  const x = pegs[a * p + k], y = pegs[s * p + k];
  if (x === y) black++;
  else { ca[x]++; cb[y]++; }
}
let white = 0;
for (let k = 0; k < c; k++) white += Math.min(ca[k], cb[k]);

Every strategy is about cutting a set

At any point there is a set S of codes consistent with every answer so far. A guess g cuts S into at most 14 parts, one per answer. A one-step strategy scores each of the 1,296 possible cuts and plays the best:

strategy	plays
consistent	the first code, lexically, that could still be the secret
maxsize (Knuth 1977)	the guess whose largest part is smallest
expsize (Irving 1979)	the smallest Σ n², i.e. the smallest expected part
entropy (Neuwirth 1982)	the cut with the most entropy
parts (Kooi 2005)	the most non-empty parts

Ties go to a guess that could itself be the secret, then to the lexically first. Because each strategy's next move depends only on S, playing it against all 1,296 secrets at once is a single walk over the decision tree it induces. Nothing is sampled; every average, histogram and worst case below is exact.

const walk = (set: number[], depth: number) => {
  const g = pick(set, depth);
  const buckets = game.grades.map(() => [] as number[]);
  for (const s of set) buckets[game.table[g * game.n + s]].push(s);
  buckets.forEach((b, r) => {
    if (!b.length) return;
    if (r === game.win) bump(depth);   // this secret is found on guess `depth`
    else walk(b, depth + 1);
  });
};

Reproducing the published numbers

strategy	first guess	total	mean	worst	found on guess 1 / 2 / 3 / …	possible codes only	worst
optimal (exact)	1123	5,625	4.340	6	1 / 8 / 102 / 630 / 548 / 7	—	—
consistent	1111	7,471	5.765	9	1 / 4 / 25 / 108 / 305 / 602 / 196 / 49 / 6	7,471	9
maxsize (Knuth)	1122	5,801	4.476	5	1 / 6 / 62 / 533 / 694	5,828	6
expsize (Irving)	1123	5,696	4.395	6	1 / 10 / 54 / 645 / 583 / 3	5,722	6
entropy	1234	5,722	4.415	6	1 / 4 / 71 / 612 / 596 / 12	5,786	6
parts (Kooi)	1123	5,668	4.373	6	1 / 12 / 72 / 635 / 569 / 7	5,701	7

Knuth's minimax opens with 1122 and always finishes within five guesses; the distribution 1 / 6 / 62 / 533 / 694 is the one in his paper. The rules that look at the whole cut win on average and lose at the tail: most-parts needs a sixth guess for 7 secrets. Restricting any rule to codes that could still be the secret costs 26 to 64 guesses in total, and costs Knuth's rule its five-guess guarantee (5,828, the figure Ville quotes).

On the seven-colour game MM(4,7) the same code reproduces Ville's Table 4: consistent 12,265, maxsize 11,613, expsize 11,409, parts 11,388.

The only mismatch is entropy: published 5,723 on MM(4,6) and 11,382 on MM(4,7); here 5,722 and 11,378.

The entropy strategy is not one number

It is full of exact ties

For a cut of N codes into parts of size nᵢ,

$$
H = \log N - \frac{1}{N}\sum_i n_i \log n_i ,
$$

so maximising entropy means minimising Σ nᵢ log nᵢ, which is the log of the integer ∏ nᵢ^nᵢ. Compare that integer as a BigInt and the comparison is exact:

export function entropyKey(sizes: Int32Array): bigint {
  let k = 1n;
  for (const x of sizes) if (x > 1) k *= BigInt(x) ** BigInt(x);
  return k;
}

Walking the exact tree: at 375 of its 404 decisions, more than one guess reaches the best score. And in none of them do the tied guesses cut S into different sizes (on MM(4,7): 687 of 726 decisions tied, again none across different sizes). Every tie is between guesses that leave the same multiset of part sizes, just attached to different answers.

Floats break those ties by rounding

The natural implementation sums p * Math.log(p) in answer order. Two tied guesses then add the same numbers in a different order, and the last bit can differ. The tie is no longer decided by the stated rule ("possible code first, then lexical order") but by rounding noise. I tried four ways of writing the sum:

MM(4,6): entropy computed as	total	decisions that differ from exact
exact (∏ n^n as a BigInt)	5,722	—
Σ n·log2 n	5,722	0 of 404
Σ p·log2 p	5,722	2 of 404
Σ p·ln p	5,723	4 of 404	published
Σ p·log2 p (float32)	5,722	4 of 404

MM(4,7): entropy computed as	total	decisions that differ from exact
exact (∏ n^n as a BigInt)	11,378	—
Σ n·log2 n	11,378	0 of 726
Σ p·log2 p	11,382	10 of 726	published
Σ p·ln p	11,380	5 of 726
Σ p·log2 p (float32)	11,381	8 of 726

On MM(4,7), four spellings of the same formula give four different totals. None of them ever picks a strictly worse cut along the exact tree; every difference comes from breaking a real tie by rounding instead of by the rule.

"Last in lexical order gives 5,722"

Ville's paper has a footnote: taking the last code in lexical order instead of the first gives 5,722. That can't be the tie order. Mapping every colour x to c + 1 − x preserves every answer and reverses lexical order, so the first-code tree and the last-code tree are mirror images with identical totals. My stats script checks first-vs-last for all five rules on both games and stops if they ever differ. The 5,722 / 5,723 split is the floats.

The general lesson: a greedy rule with many ties, written in floating point, is only reproducible up to the order of addition. If the score can be compared as an integer, compare it as an integer.

The exact optimum

The recurrence

Let cost(S) be the least possible total number of guesses, summed over every secret in S:

$$
\mathrm{cost}(S) = |S| + \min_g \sum_{r \neq \text{win}} \mathrm{cost}(S_r)
$$

|S| pays for this guess (if g is the secret, that one is done). Any code may be played, including ones that can no longer be the secret.

Four things keep the search small

1. A perfect-tree lower bound. A guess finishes at most one secret and has at most 13 non-winning answers, so m codes cost at least the external path length of a perfect 13-ary tree holding m nodes. A candidate's bound is the sum over its parts, and candidates are tried cheapest bound first.
2. Budgets. Each part is solved with whatever budget the candidate has left and gives up as soon as it goes over. A set that gave up records "at least this much" in the memo.
3. Symmetry. Candidates collapse under position × colour permutations that fix every guess made so far, under swaps of colours never played, and under swaps of colours known to be absent. Candidates that cut S identically are tried once.
4. Memo. Exact values and proven lower bounds per set.

At the root that leaves five first guesses: 1111, 1112, 1122, 1123, 1234. 1123 has the smallest bound, is tried first, and reaches 5,625. Most of the remaining time goes on proving the other four can't beat it.

for (const cand of cands) {                 // cheapest bound first
  if (cand.lb >= best) break;
  let running = cand.lb;
  for (const part of cand.parts) {          // biggest part first
    const plb = this.bound(part.length, depth - 1);
    const rest = running - plb;
    const v = this.solve(part, best - rest, depth - 1, history.concat(cand.g));
    running = rest + v;                     // swap the bound for the real value
    if (running >= best) break;             // this candidate lost
  }
  if (running < best) { best = running; bestGuess = cand.g; }
}

MM(4,6): 5,625 guesses, 43,712 sets expanded, 107.9 s in TypeScript on one core. The tree is saved as JSON, the tests replay it against all 1,296 secrets (5,625 total, worst 6), and the page's optimal hint walks it. Off the stored tree, the page searches live once 40 or fewer codes are left: over 262 random positions of that size the search took 3 ms at the median and 166 ms at worst, against 1,663 ms at worst for 41–80 codes, which is why the limit is 40.

A five-guess guarantee costs exactly one guess

The optimum needs a sixth guess for 7 secrets. Cap the depth at five — the perfect-tree bound takes a depth argument and prunes any part that can't fit in the guesses left — and the best total is 5,626. One guess more, over all 1,296 secrets.

Optimum after each first guess

Fixing the first guess and solving the rest exactly separates the opening from the play:

first guess	parts	largest part	optimal total after it	mean	with at most 5 guesses
1111	5	625	6,318	4.8750	impossible
1112	11	317	5,791	4.4684	5,808
1122	13	256	5,702	4.3997	5,702
1123	14	276	5,625	4.3403	5,626
1234	14	312	5,673	4.3773	5,676

Knuth's 1122, followed optimally, is worth 5,702. So of his strategy's 176 guesses over the optimum, 77 come from the opening and 99 from the one-step play after it. After 1111 a five-guess guarantee is impossible: the next guess can cut the 625 codes that answer (0,0) into parts of at most 120, but the search proves no continuation finishes all of them within four more guesses.

The ledger

The same search for other peg and colour counts; each cell is the optimal total over all cᵖ secrets.

pegs \ colours	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
2	8	21	45	81	132	198	284	388	517	667	847	1,051	1,290	1,556	1,862
3	18	73	206	451	854	1,474	2,359	3,596	5,242
4	44	246	905	2,463	5,625
5	97	816	3,954
6	224	2,649
7	496
8	1,104

The 27 plain cells are in Ville's Table 6 and all match. The two-peg row follows Chen and Lin's (and Goddard's) closed form all the way to c = 16. The bold MM(3,10) = 5,242 and MM(8,2) = 1,104 are outside Ville's table, and as far as I know unpublished; none of the three rows is in the OEIS. The slowest cell is MM(3,10) at 168.8 s. I did not run MM(4,7) (11,228 in Ville's table) to completion.

The stats script recomputes every cell that finishes within three seconds (27 of them) on each run and stops if any disagrees with the stored value, the published value or the closed form.

The page

• You break the code: click colours (or type 1–6, Backspace, Enter). The panel shows the codes still possible, the bits still missing, and each strategy's next guess with its largest part — and, for a guess you are composing, how it would cut the set.
• Watch a strategy break it: pick a strategy and a secret; Step, or Play to the end.
• Strategy lab: for each strategy, how many of the 1,296 secrets are found on each guess.

In the screenshot, after two guesses with 33 codes left, the optimum plays 6165, whose largest part is 9, while Knuth's rule plays 1563, whose largest part is 5. Minimising the worst case and minimising the total are different games.

What I'd tell you to steal

1. Evaluate a strategy as a tree, not by sampling. Run every secret at once and the mean, the histogram and the worst case are all exact.
2. Turn tie-heavy float scores into integer comparisons. Entropy reduces to comparing ∏ n^n. Left in floats, one rule gave four answers depending on how the sum was written.
3. Use a symmetry to rule out a suspected cause. Colour reversal makes "first" and "last" tie-breaks equivalent, so a first/last difference had to come from somewhere else.
4. Branch and bound is mostly the bound and the budget. A perfect-tree bound, budgets, symmetry and a memo bring a 1993 result to under two minutes of plain TypeScript.
5. Split an optimal tree to explain a gap. Fixing the first guess splits Knuth's 176-guess loss into 77 for the opening and 99 for the rest.

Every number here comes from npm run stats (and npm run optimal for the heavy cells), and the README and page prose are generated from src/stats.json by npm run notes. 20 tests.

References: Knuth, "The computer as master mind" (1976–77); Irving (1978–79); Koyama and Lai, "An optimal Mastermind strategy" (1993); Kooi, "Yet another Mastermind strategy" (2005); Ville, "An optimal Mastermind (4,7) strategy and more results in the expected case", arXiv:1305.1010 (2013).

Play it · Source