Donald Knuth Algorithm Mastermind

Question

I'm working on a mastermind game that implements the Donald Knuth algorithm. The first five steps are clear. I have to create a set of permutations for each possible answer, use 1122 as my first guess, compare each possible answer from the set to 1122 and then remove any of the possible answers that does not return the same feedback as the current guess. The problem now lies in determining the next guess and how I'm supposed to implement step 6. The algorithm is shown below.

Mastermind-Five-Guess-Algorithm Donal Knuth's five guess algorithm for solving the game Mastermind.

In 1977, Donald Knuth demonstrated that the codebreaker can solve the pattern in five moves or fewer, using an algorithm that progressively reduced the number of possible patterns.

The algorithm works as follows:

1. Create the set S of 1296 possible codes (1111, 1112 ... 6665, 6666).

2. Start with initial guess 1122 (Knuth gives examples showing that other first guesses such as 1123, 1234 do not win in five tries on every code).

3. Play the guess to get a response of colored and white pegs.

4. If the response is four colored pegs, the game is won, the algorithm terminates.

5. Otherwise, remove from S any code that would not give the same response if the current guess were the code.
   
   For example, if your current guess is 1122 and you get a response of BW;
   If the code were 1111 you would get two black pegs (BB) with a guess of 1122, which is not the same as one black peg and one white peg (BW). So, remove 1111 from the list of potential solutions.
   
   F(1122,1112) = BBB≠BW →Remove 1112 from S
   
   F(1122,1113) = BB≠BW →Remove 1113 from S
   
   F(1122,1114) = BB≠BW →Remove 1114 from S
   
   F(1122,1314) = BW=BW →Keep 1314 in S
   
   

6. 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, calculate how many possibilities in S would be eliminated for each possible colored/white peg score. The score of a guess is the minimum number of possibilities it might eliminate from S.
   
   A single loop through S for each unused code of the 1296 will provide a 'hit count' for each of the possible colored/white peg scores; Create a set of guesses with the smallest max score (hence minmax).
   From the set of guesses with the minimum (max) score, select one as the next guess, choosing a member of S whenever possible.
   
   Knuth follows the convention of choosing the guess with the least numeric value e.g. 2345 is lower than 3456. Knuth also gives an example showing that 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.
   
   

7. Repeat from step 3
   
   Link to Wikipedia page

Answer 1

Take the set of untried codes, and call it T.

Iterate over T, considering each code as a guess, g.

For each g, iterate over T again considering each code as a possible true hidden code, c.

Calculate the black-white peg score produced by guessing g if the real code is c. Call it s.

Keep a little table of possible scores, and as you iterate over the possible c, keep track of how many codes produce each score. That is, how many choices of c produce two-blacks-one-white, how many produce two-blacks-two-whites, and so on.

When you've considered all possible codes (for that g) consider the score that came up the most often. You might call that the least informative possible result of guessing g. That is g's score; the lower it is, the better.

As you iterate over g, keep track of the guess with the lowest score. That's the guess to make.