Mastermind

Five one-step strategies, replayed against every secret

A one-step strategy looks at how each of the 1,296 codes would cut the set of secrets still possible into at most 14 parts — one per answer — scores the cut, and plays the best. Ties go to a code that could itself be the secret, then to the lexically first code. Playing a strategy against all 1,296 secrets at once is a walk over the decision tree it induces, so every number below is exact, not sampled.

Knuth's minimax rule opens with 1122 and finds every secret within 5 guesses, 5,801 guesses in all (mean 4.476), found on guesses 1 to 5 as 1 / 6 / 62 / 533 / 694 — his published distribution. The rules that look at the whole cut do better on average and worse at the tail: most-parts reaches 5,668 but needs a sixth guess for 7 secrets. Restricting any of them to codes that could still be the secret costs between 26 and 64 guesses in total; for Knuth's rule it also costs the five-guess guarantee.

Every total matches the tables of Kooi (2005) and Ville (2013) — except one. The published entropy figure is 5,723; this implementation gets 5,722. The next section is about that one guess.

The entropy strategy is not one number

Maximising the entropy of a cut of N codes into parts n_i means minimising Σ n_i log n_i, which is the logarithm of the integer ∏ n_i^(n_i). Compare that product exactly and ties are exact. Then walk the 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 the set into different sizes (on MM(4,7): 687 of 726 tied, none across different sizes). Every tie is between guesses that leave the same multiset of part sizes, in different answers.

A float sum of p log p adds those same sizes in answer order, so two tied guesses add the same numbers in a different order and can differ in the last bit. Along the exact tree the float rules never pick a worse cut, but they break a real tie by rounding noise rather than by the stated rule, and the tree changes from there. On MM(4,6), p·ln p disagrees with the exact choice at 4 decisions and totals 5,723, the published figure. On MM(4,7) the four float rules give four different totals, from 11,378 to 11,382; the exact rule gives 11,378, and Ville's published 11,382 is what Σ p·log2 p gives.

Ville notes that choosing the last code in lexical order instead of the first gives 5,722. That cannot be the tie order: mapping every colour x to c + 1 − x preserves every answer and reverses lexical order, so first-code and last-code tie-breaks produce mirror-image trees with identical totals. The script checks this for all five rules on both games. The difference is the floats.

The exact optimum, and what a five-guess guarantee costs

The optimal strategy minimises the total over all secrets. A depth-first branch and bound finds it: 5,625 guesses (mean 4.3403), opening with 1123, found on guesses 1 to 6 as 1 / 8 / 102 / 630 / 548 / 7 — Koyama and Lai's 1993 value. The search expanded 43,712 sets and took 107.9 s in TypeScript on one core. The tree it found is stored, replayed against every secret by the tests, and drives the optimal hint on this page. Off that 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.

The optimum needs a sixth guess for 7 secrets. Forbid that — cap the depth at five — and the best total is 5,626: one guess more over all 1,296 secrets (1 / 8 / 102 / 622 / 563). The cap is enforced inside the search with the same perfect-tree bound, so a part too big to finish in the guesses left is pruned at once.

Fixing the first guess and solving the rest exactly separates the opening from the play. Knuth's 1122 is worth 5,702 when followed optimally, so of his 176 guesses over the optimum, 99 come from the later moves and 77 from the opening. After 1111 the five-guess cap is impossible: the next guess can cut the 625 codes that answer (0,0) into parts of at most 120, but the search proves that no way of continuing finishes all of them within four more guesses.

The ledger: every optimum the search reaches

The same search, run for other peg and colour counts. Each cell is the optimal total over all c^p secrets. 27 cells are in Ville's 2013 table (MM(4,6) also in Koyama and Lai), and the search matches every one of them; for two pegs the closed form of Chen and Lin and of Goddard holds for every c computed, including the 7 cells past Ville's table. The cells not in that table — MM(2,10) = 517, MM(2,11) = 667, MM(2,12) = 847, MM(2,13) = 1,051, MM(2,14) = 1,290, MM(2,15) = 1,556, MM(2,16) = 1,862, MM(3,10) = 5,242, MM(8,2) = 1,104 — are, as far as this project knows, not published; none of the three rows is in the OEIS.

The stats script recomputes every cell that takes under three seconds on each run (27 of them) and stops on any disagreement with the stored value, the published value or the closed form. The slowest cell is MM(3,10) at 168.8 s. MM(4,7), 11,228 in Ville's table, was not run to completion here.

How the search stays small

cost(S) = |S| + min over guesses g of Σ cost(part), over the parts g leaves other than the win. Four things keep it tractable. A guess finishes at most one secret and has at most 13 non-winning answers, so a set of m codes costs at least the external path length of a perfect 13-ary tree with m nodes; a candidate's bound is the sum over its parts, and candidates are tried cheapest bound first. Each part is solved with the budget the candidate has left, and gives up as soon as it exceeds it. Guesses that differ only by a permutation of positions and colours fixing every guess made so far, by a colour never played, or by a colour known to be absent are tried once; so are guesses that cut the set identically. Exact values and proven lower bounds are memoised per set.

At the root that leaves the five first guesses 1111, 1112, 1122, 1123, 1234, and 1123 is tried first because its parts have the smallest bound. Most of the time goes on proving that the other four cannot beat it.