In Mastermind, the codemaker hides a code of pegs (classically ), each one of colours (); colours may repeat. The codebreaker guesses codes and receives, for each guess, a number of black pins (right colour in the right position) and white pins (right colour in the wrong position). The board has ten rows.
The app is meant for the table. Someone else picks a secret, the app proposes every guess, and the user taps in the pins the codemaker places. The aim is to show that a principled strategy reliably cracks the code in four or five moves. The app also shows, at every move, the quantities that make the strategy legible: the number of codes still possible, the remaining uncertainty in bits, the expected information gain of the proposed guess, its probability of being the secret, and the exact expected number of remaining moves.
Three questions shaped the design. Can the app use Bayesian adaptive experimental design (Lindley 1956; Chaloner and Verdinelli 1995) literally, with an explicit hypothesis table? How far is information-greedy play from optimal play? And how much of optimal play can a phone afford? SectionΒ 2 derives the information-gain criterion and its cost. SectionΒ 3 develops the decision policy, SectionΒ 4 the app, and SectionΒ 5 the analysis.
Let be the set of codes, . A guess against a secret yields the feedback . The feedback alphabet consists of all with except , so , which is 14 for .
Posterior. Under a uniform prior and noise-free feedback, the posterior after a history is uniform on the consistent set
The app stores as a list of code indices; the remaining uncertainty is bits (10.34 bits at the start of the classic game).
Expected information gain. A guess partitions into classes with sizes , . Since the posterior after observing is uniform on , the expected information gain (Lindley 1956) is
the entropy of the partition induced by . A guess that cannot be the secret still has positive EIG if it splits . Such probe guesses are often the most informative.
Cost. One might expect a quadratic sum over pairs of feasible codes. Because the feedback is a deterministic function of , a single pass over that counts class sizes suffices. Scoring every possible guess therefore costs table look-ups: 1.7 million for the first move of the classic game. Up to the app precomputes the full feedback table (one byte per entry); above that it scores on the fly.
Symmetry. If a colour has not appeared in any guess so far, all such colours are interchangeable: permuting them maps onto itself. It therefore suffices to consider canonical guesses, in which unused colours appear in increasing order of first occurrence. This reduces the 1296 first guesses to 15, one per set partition of the positions, and it is exact, not a heuristic.
Displayed statistics. For the current guess : if and otherwise; the EIG as above; and the expected number of remaining moves , where is the total number of guesses the appβs own policy needs, summed over all (the winning guess included). The app computes exactly by simulating the policy against every consistent secret (SectionΒ 4).
The objective of the game is the number of guesses, not information. The optimal expected-moves policy satisfies the Bellman recursion
which charges one guess to every remaining secret and stops for the secret that was hit. Information-greedy play maximises a one-step proxy for this objective. The proxy is good, but it ignores, for instance, that guessing a feasible code may win immediately.
Exact search. The app solves the recursion exactly by depth-first branch and bound when is small. Any guess yields at most non-winning classes, so a set of size needs at least
total guesses, where is a balanced split of into parts. This bound is valid because is convex (verified numerically for all in the test suite), so a balanced split minimises the sum. At each node:
On small games the search agrees with an unpruned exhaustive search over all guesses.
Rollout. For medium-sized sets, exact search is too slow for a phone. The app then applies one step of policy improvement (Bertsekas et al. 1997) to a base policy , which is the EIG-greedy rule plus exact search on small sets. Among the guesses with the highest EIG, it picks the one minimising , where each childβs total is obtained by simulating to the end. SectionΒ 3.1 states the operator precisely and shows that the resulting policy is never worse than , at any point of the game.
Tiers. The policy is deterministic, and its tier depends on only: exact search if (i.e. for the classic game), rollout if , and plain max-EIG otherwise (only the first move or two of the largest games). The constant is 1 when the feedback table is available and 3 otherwise, which reflects the cost of scoring on the fly. In hard mode the candidates are restricted to , and replaces . Rollout uses candidates for games with , decreasing as for larger games. Exact search has one more shortcut: if a feasible guess splits the remaining codes into singletons, it meets the bound and is accepted immediately. This avoids scanning all candidates on the many tiny sets that rollout simulations visit. Because the policy is deterministic, its first two moves for every configuration can be precomputed into a 28 kB opening book (5 kB compressed). A test checks that the book is a cache, not an approximation: recomputing its entries reproduces them exactly.
Background. Rollout is policy iteration cut down to one improvement step, carried out on line at the states actually reached (Bertsekas et al. 1997; Bertsekas 2020). At the current state it tries each admissible decision, follows a base policy from the resulting state, and takes the decision with the lowest total cost. It was introduced to improve heuristics for combinatorial optimisation, with conditions under which the result is never worse than the base (Bertsekas et al. 1997). It needs no training, only a base policy that can be simulated; the price is many simulations per decision.
The operator. The solverβs state is , where is the set of colours used so far; fixes the canonical candidates ( in hard mode). Guess leads to the states , with its classes and its colours; we keep writing . For a deterministic policy , let be the total for guessing once and following afterwards, so . On rollout-tier states the app plays
where holds the candidates of highest EIG and ties go to the higher-ranked guess; elsewhere . The base is the app with rollout switched off (βMax EIG + exact endgameβ in TableΒ 1): the branch-and-bound optimum on exact-tier states, where , and the max-EIG guess on all other states, rollout-tier ones included, with ties broken in favour of feasible codes, then of the smaller code index. baseTotal evaluates over all children without sampling, so the compared values of are exact.
Restricting the candidates. Improvement rests on the one-step inequality
(1)
which needs only , not that the best guess is a candidate: the filter limits how much rollout gains, not whether ( gives back ). At a rollout-tier state, is the max-EIG guess, and rankByEig uses the same candidates, score and tie rule as greedy. So the base guess is ranked first and lies in for every , up to one floating-point caveat: both treat EIG values within as equal. In the classic game, its hard variant, and the , and games, the base guess was ranked first at all 50 rollout-tier states the policy visits. The guarantee would fail if filter and base disagreed, e.g. if used exact search where candidates are still filtered by EIG.
Over the whole game. EquationΒ 1 covers one deviation followed by , but deviates again at every later rollout-tier state. In the terminology of rollout algorithms (Bertsekas et al. 1997; Bertsekas 2020), is sequentially consistent: after one step it continues exactly as it would have anyway, because its guess is a deterministic function of , and because tiers depend on alone and grow with , so exact-tier states have exact-tier children and is the cost of actually following there. With , the restricted rollout is then sequentially improving, meaning that EquationΒ 1 holds at every rollout-tier state, and follows on every state by induction on . Children are strictly smaller, since a guess that neither splits nor can win has , which EquationΒ 1 excludes for , and the max-EIG guess has positive EIG for . On exact-tier states and agree on the whole subtree; on greedy-tier states they make the same guess, and the induction hypothesis applies child by child; on rollout-tier states, with ,
The feedback is random from the codebreakerβs point of view, but sums over all children exactly, so the deterministic argument carries over. Two qualifications remain. An exact search that exceeds its work cap ( units) falls back to the greedy guess, and whether it does depends on the memo, so would no longer be a function of the state; the cap was never reached in the runs above. And the guarantee is a weak inequality relative to only: it does not make optimal, nor comparable with rollout on another base, as the non-monotone exact-threshold ablation in FigureΒ 2 shows.
Cost. A rollout decision scores all candidates ( look-ups) and then, for each of the candidates, simulates to the end on every child: a max-EIG step on every non-exact set below, at most look-ups per code and level, and memoised exact searches on the small sets at the bottom. That is about look-ups plus the exact searches, where is the number of non-exact levels below , against for a greedy decision. A candidate is dropped once its partial total reaches the best so far, so cost grows more slowly than : the full-tree times in TableΒ 2 rise from 1.19 s at to 5.94 s at . Computing for the displayed expected moves repeats this at every rollout-tier state of the tree.
The app consists of static files with no dependencies and no build step: index.html, styles.css and app.js for the interface, solver.js (about 600 lines) for the solver, which runs unchanged in Web Workers and in Node, worker.js, the generated book.js, and a service worker and manifest that make it installable and usable offline.
Two workers. A suggest worker returns the hypothesis-set size, the proposed guess, its EIG and its answer distribution. An expected worker simulates the policy against every consistent secret to obtain . A new request can supersede an expected-moves simulation that is still running; the app then simply terminates and respawns that worker, so the interface never waits for stale work. If the user overrides the guess, the simulation starts from the userβs guess.
Interaction. The answer pad is a triangular grid of the valid outcomes, drawn as pins and annotated with the appβs predicted probability , so the prediction can be checked against what happens. Answers with probability zero are disabled: they would contradict an earlier answer, so the codemaker must have mis-scored a row, and Undo is one tap away. Any peg of the proposed guess can be changed through a palette, and the statistics update for the userβs guess. This shows directly how a plausible-looking alternative costs expected moves. State is kept in local storage.
Testing. The Node test suite covers:
policyStats with step-by-step play of every secret;A headless-Chrome test plays complete games through the interface. It covers undo, persistence, overrides, settings, offline reload, and the absence of horizontal scrolling at 320β390 px widths.
All numbers below were produced by tools/analyze.mjs on a 32-thread AMD Ryzen 9 7950X3D 16-Core Processor with Node v23.4.0. Each policy is evaluated exactly, by following it against every one of the secrets, with no sampling.
| Strategy | Total | Max | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|---|---|
| Max EIG (entropy) | 4.4151 | 5722 | 6 | 1 | 4 | 71 | 612 | 596 | 12 | |
| Most parts | 4.3735 | 5668 | 6 | 1 | 12 | 72 | 635 | 569 | 7 | |
| Min. expected size | 4.3951 | 5696 | 6 | 1 | 10 | 54 | 645 | 583 | 3 | |
| Minimax (Knuth) | 4.4761 | 5801 | 5 | 1 | 6 | 62 | 533 | 694 | ||
| Max EIG + exact endgame | 4.3989 | 5701 | 6 | 1 | 5 | 76 | 620 | 582 | 12 | |
| App: EIG + rollout + exact | 4.3403 | 5625 | 6 | 1 | 8 | 82 | 665 | 538 | 2 | |
| Max EIG, hard | 4.4645 | 5786 | 6 | 1 | 13 | 103 | 502 | 620 | 57 | |
| Minimax, hard | 4.4969 | 5828 | 6 | 1 | 12 | 99 | 468 | 662 | 54 | |
| App, hard | 4.4429 | 5758 | 6 | 1 | 13 | 100 | 514 | 633 | 35 | |
| Optimum (Koyama and Lai 1993) | 4.3403 | 5625 | 6 |
TableΒ 1 places the app within the classic heuristics. Three entries serve as checks. The entropy strategy reproduces the published total of 5722 (4.415). The minimax strategy reproduces Knuthβs five-guess worst case and his total of 5801 (Knuth 1976). The appβs total of 5625 equals the minimum over all strategies established by exhaustive search (Koyama and Lai 1993). No strategy can do better, so the appβs policy is an optimal strategy for the expected number of guesses, although it never searches the full game tree. It is 0.075 guesses per game better than pure information-greedy play.
The exact endgame alone recovers only about a fifth of the gap between greedy and optimal play. Most of the gap comes from the first two guesses, and that is where rollout matters. Its first decision illustrates this. The most informative opening is 1234 (3.0567 bits), but rollout prefers 1123 (3.0437 bits). The pair of identical pegs costs 0.013 bits of information, but 1123 leads to better-balanced follow-ups. Because the policy that opens with 1123 attains the optimum, 1123 is an optimal opening for the expected-moves objective.
The app optimises the mean, not the worst case. Only 2 of the 1296 secrets need six guesses, whereas Knuthβs minimax strategy needs at most five, at the price of 0.136 extra guesses per game. Hard mode, which only ever plays codes that could be the secret, costs 0.103 guesses per game.
| Setting | Total | Full-tree time (s) | |
|---|---|---|---|
| 4.3989 | 5701 | 1.19 | |
| 4.3526 | 5641 | 1.69 | |
| 4.3488 | 5636 | 2 | |
| 4.3434 | 5629 | 3.19 | |
| 4.3418 | 5627 | 4.57 | |
| 4.3403 | 5625 | 5.94 | |
| 4.3403 | 5625 | 7.8 | |
| exact | 4.3449 | 5631 | 1.51 |
| exact | 4.3465 | 5633 | 1.17 |
| exact | 4.3434 | 5629 | 2.22 |
| exact | 4.3403 | 5625 | 5.79 |
| exact | 4.3403 | 5625 | 14.26 |
FigureΒ 2 and TableΒ 2 show that a single rollout candidate (, which is plain greedy with an exact endgame) leaves most of the gain on the table. Two or three candidates already capture most of it. Reaching the optimum takes ; more candidates change nothing. The optimum is therefore always among the 20 most informative guesses in the positions where rollout operates. Information ranking is an excellent filter, even where it is a poor final criterion. The exact threshold matters less once rollout is in place, and its effect is not monotone. Raising it changes the base policy whose cost rollout uses to rank candidates, so a slightly better base can lead to a slightly worse choice higher up. With , thresholds of 60 or more reach the optimum.
FigureΒ 3 shows the information budget of a typical game. The first two guesses each remove about three bits, roughly 23, that is, an eight-fold reduction of the hypothesis set. By move three the set is small (on average 17.6 codes, geometric mean) and the exact search takes over; from then on the guesses are chosen for winning rather than for information. Averaged over uniformly drawn secrets, the information actually obtained equals the expected information gain exactly, because the posterior is correct, so it is not plotted separately. The decision tiers used per move were: move 1: rollout 1296; move 2: rollout 1180, exact 115; move 3: exact 1287; move 4: exact 1205; move 5: exact 540; move 6: exact 2.
| Bound | Max EIG | App | Max | App hard | Max | Opening | |||
|---|---|---|---|---|---|---|---|---|---|
| 2 | 3 | 8 | 1.875 | 2.250 | 2.250 | 3 | 2.250 | 3 | 112 |
| 3 | 3 | 27 | 2.630 | 2.704 | 2.704 | 4 | 2.704 | 4 | 112 |
| 4 | 3 | 64 | 2.844 | 3.250 | 3.219 | 4 | 3.219 | 4 | 112 |
| 5 | 3 | 125 | 3.336 | 3.624 | 3.608 | 5 | 3.640 | 5 | 123 |
| 6 | 3 | 216 | 3.616 | 3.981 | 3.954 | 5 | 4.000 | 6 | 123 |
| 7 | 3 | 343 | 3.758 | 4.338 | 4.297 | 6 | 4.382 | 7 | 123 |
| 8 | 3 | 512 | 3.838 | 4.678 | 4.607 | 6 | 4.764 | 8 | 123 |
| 9 | 3 | 729 | 4.084 | 4.996 | 4.933 | 6 | 5.143 | 9 | 123 |
| 10 | 3 | 1000 | 4.332 | 5.310 | 5.247 | 7 | 5.529 | 10 | 123 |
| 2 | 4 | 16 | 2.063 | 2.750 | 2.750 | 4 | 2.750 | 4 | 1112 |
| 3 | 4 | 81 | 2.815 | 3.086 | 3.037 | 4 | 3.049 | 4 | 1123 |
| 4 | 4 | 256 | 3.227 | 3.563 | 3.535 | 4 | 3.547 | 5 | 1123 |
| 5 | 4 | 625 | 3.683 | 3.962 | 3.941 | 5 | 3.962 | 5 | 1123 |
| 6 | 4 | 1296 | 3.847 | 4.415 | 4.340 | 6 | 4.443 | 6 | 1123 |
| 7 | 4 | 2401 | 3.926 | 4.739 | 4.712 | 6 | 4.759 | 7 | 1234 |
| 8 | 4 | 4096 | 4.371 | 5.051 | 5.021 | 7 | 5.095 | 8 | 1234 |
| 9 | 4 | 6561 | 4.607 | 5.323 | 5.303 | 7 | 5.408 | 9 | 1234 |
| 10 | 4 | 10000 | 4.742 | 5.621 | 5.602 | 8 | 5.740 | 10 | 1234 |
| 2 | 5 | 32 | 2.344 | 3.313 | 3.031 | 4 | 3.031 | 4 | 11122 |
| 3 | 5 | 243 | 2.914 | 3.358 | 3.358 | 4 | 3.391 | 5 | 11123 |
| 4 | 5 | 1024 | 3.607 | 3.884 | 3.866 | 5 | 3.889 | 6 | 11223 |
| 5 | 5 | 3125 | 3.871 | 4.350 | 4.328 | 6 | 4.349 | 6 | 11223 |
| 6 | 5 | 7776 | 4.017 | 4.769 | 4.760 | 7 | 4.769 | 7 | 11223 |
TableΒ 3 extends the analysis to all 23 supported configurations. The appβs advantage over pure max-EIG is largest for mid-sized games, where rollout operates on the first moves. For the largest games the first moves are still chosen by max EIG, and the gap narrows. The counting bound is loose (it assumes that every guess splits the set into equal classes), but it shows how the difficulty grows: roughly plus a constant.
| Game | States | Sampled | Suggest p50 | p95 | max | Expected p95 | max |
|---|---|---|---|---|---|---|---|
| 7Γ3 | 35 | 35 | 0.1 | 0.5 | 4.2 | 0.7 | 0.8 |
| 7Γ3 hard | 34 | 34 | 0 | 0.1 | 0.3 | 0.1 | 0.3 |
| 8Γ3 | 37 | 37 | 0.1 | 5.9 | 9.3 | 1 | 1.1 |
| 8Γ3 hard | 35 | 35 | 0 | 0.7 | 0.9 | 0.2 | 0.3 |
| 9Γ3 | 36 | 36 | 2.1 | 24 | 100 | 1.3 | 1.5 |
| 9Γ3 hard | 35 | 35 | 0.1 | 1.3 | 3.5 | 0.2 | 0.2 |
| 10Γ3 | 56 | 56 | 1 | 88 | 151 | 5.6 | 14 |
| 10Γ3 hard | 35 | 35 | 0.4 | 17 | 26 | 0.4 | 0.6 |
| 4Γ4 | 58 | 58 | 0 | 0.1 | 0.1 | 0 | 0.2 |
| 4Γ4 hard | 59 | 59 | 0 | 0 | 0 | 0 | 0.2 |
| 5Γ4 | 91 | 91 | 0 | 0.4 | 1.5 | 0 | 0.3 |
| 5Γ4 hard | 90 | 90 | 0 | 0.1 | 0.1 | 0 | 0.3 |
| 6Γ4 | 102 | 102 | 0.3 | 2.4 | 21 | 0.3 | 1.3 |
| 6Γ4 hard | 94 | 94 | 0 | 0.2 | 2.9 | 0 | 0.4 |
| 7Γ4 | 336 | 114 | 0.9 | 63 | 135 | 6 | 9 |
| 7Γ4 hard | 105 | 105 | 0 | 2 | 14 | 0.1 | 11 |
| 8Γ4 | 856 | 103 | 1.2 | 110 | 179 | 26 | 104 |
| 8Γ4 hard | 108 | 108 | 0.1 | 18 | 130 | 0.2 | 0.5 |
| 9Γ4 | 1931 | 101 | 1.8 | 78 | 92 | 247 | 480 |
| 9Γ4 hard | 247 | 109 | 0.9 | 49 | 207 | 2 | 19 |
| 10Γ4 | 3091 | 102 | 2.6 | 28 | 68 | 469 | 1336 |
| 10Γ4 hard | 352 | 103 | 0.8 | 107 | 236 | 8.8 | 63 |
| 4Γ5 | 175 | 108 | 0 | 0.5 | 2.7 | 0 | 0.4 |
| 4Γ5 hard | 165 | 103 | 0 | 0.1 | 0.2 | 0 | 2.1 |
| 5Γ5 | 640 | 100 | 1 | 37 | 74 | 2 | 8.2 |
| 5Γ5 hard | 213 | 127 | 0 | 0.2 | 4.3 | 0 | 0.4 |
| 6Γ5 | 2062 | 102 | 2.4 | 130 | 146 | 59 | 110 |
| 6Γ5 hard | 318 | 110 | 0.1 | 23 | 30 | 0.3 | 0.8 |
| Game | Moves | First | Suggest | Expected |
|---|---|---|---|---|
| 6Γ4 | 4.5 | 61 | 32 | 33 |
| 6Γ4 hard | 4.5 | 37 | 33 | 34 |
| 7Γ4 | 4.75 | 72 | 33 | 96 |
| 8Γ4 | 5 | 168 | 132 | 330 |
| 10Γ4 | 5.75 | 20 | 34 | 629 |
| 5Γ5 | 4.5 | 141 | 33 | 146 |
| 6Γ5 | 4.25 | 22 | 82 | 113 |
TableΒ 4 and TableΒ 5 show that the hybrid policy fits a phone budget. No decision in any configuration takes longer than 236 ms on the desktop, and the classic game never exceeds 21 ms. We could not measure phone latency directly. Chromeβs CPU throttling applies to the page thread only, not to the Web Workers that run the solver. Assuming the usual factor of 3β5 between desktop and phone single-thread JavaScript performance, the slowest decision stays around one second, and the classic game stays instantaneous. Thanks to the opening book, the expensive first two decisions are free, and so is the expensive initial expected-moves figure (several seconds of computation for the classic game). Later decisions involve sets that the tiers keep small. The slowest positions are mid-sized sets in the largest games, where rollout simulations score many candidates without a feedback table.
What the app demonstrates. The explicit hypothesis table makes the Bayesian reading concrete: the board shows how many codes are left after each answer, and the answer pad shows the predicted distribution of the next answer. Information gain explains most of good play. The remaining few hundredths of a guess come from planning: preferring guesses that leave well-structured follow-ups and, late in the game, guesses that can win.
Limitations. Optimality is established for the classic game only, by comparison with the published optimum. For other sizes, the policy is guaranteed only to be no worse than its greedy base (SectionΒ 3.1), and the cost-aware tiers deliberately give up up to 0.01 guesses per game in the largest games to keep every decision under a second on a phone. Full exact optimisation from the first move remains out of reach in a browser for general , and the app does not attempt it. The symmetry reduction exploits colour permutations only. Adding position permutations would shrink the candidate sets further and would be the first step towards computing optimal opening books offline. The app assumes the codemaker scores correctly. It detects impossible answers but does not reason about noisy feedback, which would require a likelihood model instead of hard elimination.
Dimitri P. Bertsekas (2020). Rollout, Policy Iteration, and Distributed Reinforcement Learning. Belmont, MA: Athena Scientific. |
Dimitri P. Bertsekas, John N. Tsitsiklis, and Cynara Wu (1997). Rollout Algorithms for Combinatorial Optimization. In Journal of Heuristics 3.3, pages 245β262. |
Kathryn Chaloner and Isabella Verdinelli (1995). Bayesian Experimental Design: A Review. In Statistical Science 10.3, pages 273β304. |
Donald E. Knuth (1976). The Computer as Master Mind. In Journal of Recreational Mathematics 9.1, pages 1β6. |
Kenji Koyama and Tony W. Lai (1993). An Optimal Mastermind Strategy. In Journal of Recreational Mathematics 25.4, pages 251β256. |
Dennis V. Lindley (1956). On a Measure of the Information Provided by an Experiment. In The Annals of Mathematical Statistics 27.4, pages 986β1005. |