## Knuth’s Algorithm for Master Mind

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:

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