Pith. sign in

REVIEW 3 major objections 5 minor 14 references

Search Algorithms for Mastermind

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Consistency heuristic cracks Mastermind in 4.7 guesses on average

desk verdict A Mastermind heuristic paper with correct background math but a headline comparison built on a 'Knuth' baseline that cannot be Knuth as reported. read the letter →

arxiv 1908.06183 v1 pith:NBDWLPF6 submitted 2019-08-16 cs.AI

Anthony D. Rhodes This is my paper · ORCID
classification cs.AI
keywords Mastermindsimulatedannealingmaximumexpectedreductioninconsistencysetminimaxbaselinerandomsearchcombinatorial
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proposes two search algorithms for Mastermind and compares them against random guessing and the classic five-guess minimax baseline. The first, a simulated-annealing variant, scores candidate codes by how far their feedback departs from observed feedback and accepts inconsistent candidates with an annealed probability. The second, maximum expected reduction in consistency (MERC), always asks the code from the consistency set that promises the smallest expected remaining set of possible master codes. Across 5,000 simulated games on the standard four-peg, six-color game, MERC averages 4.714 queries and the annealing variant averages 5.7916, versus 639.9 for random search and 4.468 for the minimax baseline. The practical point is that a cheap heuristic can shrink hundreds of queries to under five, while the paper's own numbers show neither new method overtakes the minimax reference.

What carries the argument

The load-bearing object is the consistency set $S_i$, the set of all codes that produce the same feedback history as the hidden master code. MERC scores each candidate $c \in S_i$ by the expected size of the consistency set after asking $c$, computed by simulating every possible master code and counting survivors, and then asks the $c$ with the smallest expected size. The simulated-annealing variant instead forms an augmented set from $S_i$ plus Hamming-distance-one neighbors of the current query, scores neighbors by the sum of absolute differences in black and white peg counts, and accepts inconsistent neighbors with probability $2/(\text{score}+1)$.

What would settle it

Re-run the paper's algorithm for the minimax baseline, MERC, and simulated annealing on all 1,296 codes of MM(6,4), using the same initial code and feedback rules, and record query counts. If the baseline's maximum is five, the reported maximum of seven in Table III is an implementation or transcription error and the comparisons need re-checking; if the baseline's maximum really is seven, then it is not the five-guess minimax algorithm and the comparative claims stand only against an unverified stand-in.

Watch

Extended reading notes

Core claim

The paper's central claim is that a consistency-set reduction rule, MERC, and a simulated-annealing search each solve Mastermind far faster than random guessing, with MERC nearly matching the established minimax baseline. On the standard four-peg, six-color game (MM(6,4)), MERC's mean of 4.714 queries and maximum of 7 compare with a 4.468 mean and a reported maximum of 7 for the minimax baseline and 639.9 for random search; the annealing method trails at 5.7916 mean and 13 maximum. The paper also reports the same ranking for smaller variants: MERC averages 4.206 on MM(5,4) and 3.751 on MM(4,4), always far below random search but never below the minimax baseline.

Load-bearing premise

The comparison rests on the assumption that the minimax baseline in the experiment is the genuine five-guess minimax algorithm, even though the paper's own Table III reports a maximum of seven queries for that baseline while also stating the algorithm guarantees at most five.

Editorial extensions

If this is right

  • On the paper's data, MERC reduces the average guess count on MM(6,4) from 639.9 for random search to 4.714, suggesting that expected consistency-set reduction is a strong practical substitute when exhaustive minimax search is unavailable.
  • The simulated-annealing variant is the weakest informed method tested, averaging 5.7916 guesses, which indicates that adding stochastic neighborhood search to a consistency set does not by itself produce a competitive solver.
  • The ranking of methods is stable across smaller variants: MERC beats random search by roughly two orders of magnitude on MM(5,4) and MM(4,4) as well, while the minimax baseline remains best.
  • If the baseline is a faithful implementation, the paper's main comparative point is that neither novel method surpasses the 4.468-mean benchmark, so future work should measure against that benchmark rather than against random search.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A corrected baseline could change the paper's headline comparison: if the Table III minimax entry actually implements a different selection rule, the 4.468 mean may not reflect the true five-guess algorithm, and MERC's gap to the genuine benchmark could be larger or smaller than reported.
  • Because MERC restricts queries to the consistency set, it may throw away information that inconsistent but informative queries can provide, as the annealing variant's neighborhood does; a hybrid that occasionally tries such codes could lower MERC's worst-case maximum.
  • The expected-size criterion is essentially a one-step entropy minimization, so a direct comparison with an information-theoretic strategy on the same code variants would quantify how much of the gap to the minimax baseline comes from greedy lookahead and how much from the consistency restriction.
  • The reported standard deviations (around 0.9 guesses) make the 0.25-guess difference between MERC and the minimax baseline small; paired trials over the same random seeds would clarify whether that gap is statistically reliable.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper presents two search algorithms for Mastermind: a simulated-annealing variant (SA) and a heuristic called maximum expected reduction in consistency (MERC), and compares them with random search and with Knuth's minimax five-guess algorithm. Experiments on MM(6,4), MM(5,4), and MM(4,4) with n=5000 games per configuration report mean query counts, with the main numerical results in Table III (e.g., for MM(6,4): MERC mean 4.714, SA mean 5.7916, Knuth mean 4.468, random mean 639.9). The abstract claims novelty for the two approaches but does not claim superiority over prior art; the paper explicitly takes Knuth's 4.467 expected queries as the reference point.

Significance. If the empirical results are reproducible, the paper provides a modest but useful data point: MERC is a simple consistency-based heuristic that vastly outperforms random search and operates in the same range as, though slightly worse than, the classic Knuth baseline, while the SA variant is weaker in these experiments. The paper does not claim state-of-the-art performance, and the MERC idea is a natural, clearly motivated objective. The explicit pseudocode for all algorithms and the large sample size are strengths. However, the central comparative claim depends on the correctness of the implemented Knuth baseline, and the manuscript itself contains an internal inconsistency about that baseline; because of this, the main quantitative conclusion is not yet supported.

major comments (3)
  1. [Section III and Table III]
  2. [Section V and Algorithm 3]
  3. [Section VI, Table III]
minor comments (5)
  1. [Abstract]
  2. [Section II]
  3. [Section IV, Eq. (4)]
  4. [Section II]
  5. [Table III]

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the SA and MERC algorithms are evaluated against independently generated Mastermind codes, and their heuristics are not fitted to the query-count metric they are measured on.

full rationale

The paper's central quantitative claims are the mean query counts in Table III for MM(6,4), MM(5,4), and MM(4,4). These counts are measured over n=5000 randomly generated master codes, and neither SA nor MERC fits any parameter to the query-count objective. SA uses a fixed acceptance constant alpha=2 and a Hamming-distance neighborhood; MERC greedily minimizes the expected cardinality of the residual consistency set, which is a proxy for, not identical to, the number of remaining queries. The evaluation metric is therefore not definitionally equal to any fitted quantity. The paper cites Knuth's and Norvig's methods as external baselines and Knuth's 4.467 expected queries as an external benchmark, so the comparison does not reduce to a self-citation chain. The reported Knuth baseline is internally inconsistent with the stated five-guess guarantee (Table III reports maxima of 7 and 6 for MM(6,4) and MM(5,4)), and Algorithm 1's selection rule is not a clean statement of minimax; however, that is a correctness or reproducibility concern about the baseline implementation, not a circularity of the derivation. No equation in the paper is defined in terms of the quantity it is used to predict, and no fitted input is renamed as a prediction. Hence no circular step can be exhibited, and the appropriate score is 0.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The paper's positive content is empirical; the analytic results it states are either standard counting (Eq. 2 and 3) or cited prior results (Knuth's five-guess bound, Ville's m(c,2) bound). The experiments rest on the uniformity of master codes, the correctness of the response function, and protocol choices (initial codes, alpha=2) that are hand-set. No invented entities are introduced.

free parameters (3)
  • SA acceptance constant alpha = 2
    Section IV, acceptance probability alpha/(score(c)+1) for inconsistent candidate codes. Hand-chosen; no sensitivity analysis, so the SA means in Table III are conditional on this value.
  • initial query protocol = 1122 for Knuth and MERC; random for SA and random search
    Section VI. The asymmetric starting protocol disadvantages SA and random search in the comparison; not flagged by the paper as a confound.
  • SA neighborhood radius = Hamming distance 1
    Section IV. The neighborhood of the current query is defined as all codes at Hamming distance one, a hand-chosen design choice with no stated motivation or sensitivity check.
assumptions (4)
  • standard math The Mastermind response function q(a,b) is symmetric in its two arguments
    Used implicitly in MERC (Section V, Algorithm 3) where the consistency condition is written as q(m',c') = q(c,m'); the symmetry of exact and color matches is elementary and unstated.
  • domain assumption Knuth's five-guess guarantee for MM(6,4), cited to [3]
    Section II and III. Background result used to frame the baseline; the paper's own Table III contradicts it (max 7), so the baseline's fidelity to this assumption is in question.
  • domain assumption Lower bound m(c,2) = floor(c/2) + 2 and m(c,p) >= floor(c/2) + 2, cited to [2]
    Section II. The proof leaves the decisive step as 'one can show'; not load-bearing for the experimental claims but stated as a theorem.
  • domain assumption Master codes are drawn uniformly at random in the simulations
    Section VI (n=5000 simulated games). Standard evaluation convention for Mastermind; affects the mean/median/max statistics reported.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Search Algorithms for Mastermind." pith.science (2026). https://pith.science/paper/NBDWLPF6

@misc{pith2026190806183,
  author       = {Pith},
  title        = {Pith review of: Search Algorithms for Mastermind},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NBDWLPF6}},
  note         = {Machine review of arXiv:1908.06183}
}
read the original abstract

his paper presents two novel approaches to solving the classic board game mastermind, including a variant of simulated annealing (SA) and a technique we term maximum expected reduction in consistency (MERC). In addition, we compare search results for these algorithms to two baseline search methods: a random, uninformed search and the method of minimizing maximum query partition sets as originally developed by both Donald Knuth and Peter Norvig.

Figures

Figures reproduced from arXiv: 1908.06183 by the authors.

Figure 1
Figure 1. Mastermind game schematic, including decoding board, code pegs and key pegs. A completed game is shown. search algorithms. With four pegs and six colors (which we henceforth denote MM(6, 4)) there are 6 4 = 1296 possible codes. One of the most essential properties surrounding efficient search in mastermind is the notion of code consistency: if q(m) = q(c) and q(m) = q(c 0 ), then c ∼ c 0 (1) where above q(·) connote… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

  1. [1]

    Mastermind Revisited

    Goddard, Wayne. Mastermind Revisited. 2004

    work page 2004

  2. [2]

    An Optimal Mastermind (4,7) Strategy and More Results in the Expected Case, 2013

    Ville, Geoffroy. An Optimal Mastermind (4,7) Strategy and More Results in the Expected Case, 2013

    work page 2013

  3. [3]

    The Computer as Mastermind

    Knuth, D.E. The Computer as Mastermind. Journal of Recreational Mathematics, 1976-77, 16

    work page 1976

  4. [4]

    Peter Norvig. 1984. Playing Mastermind optimally. SIGART Bull. 90 (October 1984), 33-34

    work page 1984

  5. [5]

    Mastering Mastermind with MCMC

    Blair, Nathan, et al. Mastering Mastermind with MCMC. 2018

    work page 2018

  6. [6]

    A Heuristic Hill-Climbing Algorithm for Mastermind

    Temporel, Alexandre, et al. A Heuristic Hill-Climbing Algorithm for Mastermind. 2004

    work page 2004

  7. [7]

    Efficient Solutions for Mastermind Using Genetic Algorithms

    Berghman, Lotte, et al. Efficient Solutions for Mastermind Using Genetic Algorithms. Computers and Operations Research, V olume 36, Issue 6, June 2009

    work page 2009

  8. [8]

    ICGA Journal

    Kooi, Barteld.Yet another Mastermind strategy. ICGA Journal. 28. 10.3233/ICG-2005-28105. 2005

    work page doi:10.3233/icg-2005-28105 2005

Show all 14 references
  1. [9]

    Heuristic Solution Methods for the 1-Dimensional and the 2-Dimensional Mastermind Problem

    Singley, Andrew. Heuristic Solution Methods for the 1-Dimensional and the 2-Dimensional Mastermind Problem. 2005 (MS thesis)

    2005

  2. [10]

    Solving Mastermind Using Genetic Algorithms

    Kalisker, Tom, et al. Solving Mastermind Using Genetic Algorithms. GECCO 2003, LNCS 2724. 2003

    2003

  3. [11]

    NP-completeness of Master Mind and Minesweeper

    Bondt, Michiel. NP-completeness of Master Mind and Minesweeper. Journal of Physical Chemistry A - J PHYS CHEM A. 2004

    2004

  4. [12]

    Mastermind is NP-Complete

    Stuckman, J., and Zhang, G. Mastermind is NP-Complete. ArXiv. 2005

    2005

  5. [13]

    Playing Mastermind Logically

    Shapiro, Ehud. Playing Mastermind Logically. SIGART Bull. 85 (July 1983)

    1983

  6. [14]

    Thomas.Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)

    Cover, Thomas and Joy A. Thomas.Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, New York, NY , USA. 2006

    2006

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.