Wikipedia gives a description of Knuth’s Mastermind solver which I think could do with some refinement. Here is how I would describe the algorithm:

- Create the set S of 1296 guesses: 1111,1112,.., 6666.
- Start with initial guess 1122 (See Note 1 below) to get a response of colored and white pegs.
- If the response is four colored pegs, the game is won, the algorithm terminates.
- Otherwise, remove from S any guess that would not give the same response if it (the guess) were the code.
- Apply minimax technique to find a next guess as follows:
- For each possible guess, that is, any unused code of the 1296 not just those in S,
- for each possible colored/white peg score. (There are 14 possibilities)
- calculate how many possibilities in S would be eliminated

- The score of a guess is the minimum number of possibilities it might eliminate from S.

- for each possible colored/white peg score. (There are 14 possibilities)
- From the set of guesses with the maximum score, select one as the next guess, choosing a member of S whenever possible.(See Note 2 below)

- For each possible guess, that is, any unused code of the 1296 not just those in S,
- Repeat from step 3.

**Note 1:** Some other first guesses such as 1123, 1234 do not win in five tries on every code.

**Note 2:** By convention choose the guess with the least lexicographic order e.g. 2345 is lower than 3456. In some cases no member of S will be among the highest scoring guesses and thus the guess cannot win on the next turn, yet will be necessary to assure a win in five.

Advertisements