Black-peg Mastermind solver and simulator

How the solver works

The solver keeps track of every code that still fits all answers so far, without ever listing them. For each code, the number of matches with each past guess forms a tally. Going position by position, a dynamic program counts how many codes reach every possible tally, and only the codes whose tally equals the answers exactly are kept. That gives the exact number of remaining codes, even when it is in the billions.

The same counts let it draw remaining codes uniformly at random and give the chance of each symbol at each position. To choose a guess, it looks for the one whose answer is the least predictable over those codes, i.e. carries the most information (entropy). It starts from several random and frequency-weighted guesses and improves each by hill climbing: repeatedly applying the single-symbol change that raises the information most.

The best guess is often not a possible answer. Placing symbols already known to be wrong in some positions makes the count speak only about the others. Near the end, when few codes remain, the solver prefers guesses that could also win.

How many guesses does it take?

There are K^N possible codes, so finding one takes log₂(K^N) bits of information. An answer from 0 to N can carry at most log₂(N + 1) bits, so no strategy can always succeed in fewer than log₂(K^N) / log₂(N + 1) answered guesses.

For 10 positions and 12 symbols that is 35.85 bits, with at most 3.46 bits per answer: about 10.4 guesses. Real answers are far from evenly spread. Against a fresh code each position matches with probability 1/12, so the first answer carries only about 1.70 bits, whatever the first guess is. Measured averages at 10 × 12:

For other sizes, run Compare strategies above; every strategy plays the same secrets.

The strategies

Max information recommended

Each turn, picks the guess whose answer splits the remaining codes as evenly as possible across all possible answers, found by the hill climb described above.

Any possible code

Each turn, guesses a random code that still fits every answer. Simple and surprisingly strong, but it never uses the more informative "impossible" probes.

Count, then halve

First counts each symbol with guesses like AAAA, BBBB, and picks an absent symbol as a blank filler. Then finds each symbol's positions by binary search: put it in half of the open positions, blanks elsewhere, and split again. The best method that is easy to run by hand.

Count, then one by one

Counts each symbol the same way, then fills the positions in turn, trying the most frequent remaining candidate with blanks everywhere else until the answer confirms it.

Both count methods need a symbol that is certainly absent, which is only guaranteed when there are more symbols than positions. With K ≤ N they are unavailable.

Known results

For classic 4 × 6 Mastermind with white pegs, Knuth (1976) showed every code can be found in at most five guesses. For black-peg Mastermind the research is about how the number of guesses grows with very large codes:

• Doerr, Spöhel, Thomas and Winzen, Playing Mastermind with Many Colors, give bounds that hold even with black pegs only.
• Martinsson and Su, Mastermind with a Linear Number of Queries, settle the randomised query complexity of black-peg Mastermind: Θ(n log k / log n + k).

None of these gives the optimal strategy for a specific size like 10 × 12, which is far beyond exhaustive search. A greedy one-step method like Max information is the practical approach.