MM Phase II

In this phase we implement the strategy from Knuth’s 1977 paper “The Computer as Master Mind” (J. Recreational Mathematics, Vol 9(1), 1976-77).

This strategy is to choose a guess that minimizes the “worst case” outcome. Since a lot of people have questions about how this strategy works, his page will include a lot of details.

Step 1: Score a single guess

Your solver should remember all of the possibilities for the secret code based on the information gathered so far. To score a guess:

  • Find out the number of exact and approximate matches for each possible secret.
  • Total the number of each type of response that occurs. The maximum of these numbers is the score for the guess.

Step 2: Choose a guess

  • Score all possible guesses.
  • Select a guess that gives the smallest maximum score. (This is why this method is considered a “minimax” approach.)

Step 3: Update the possible secrets

Get feedback and reduce the set of all possible guesses to only those codes that would give the same feedback that you received.

Example

Suppose that you have narrowed down the search space so that the possible codewords are 1123, 3151, 1141, and 6544.

Step 1 gives you the ability to score a single guess, like 4113, giving (exact,approximate) matches of (2,1), (1,2), (1,2) and (0,0) respectively. The worst case scenario would be a response of (1,2), which happens with 2 of the codewords. Score 4113 as two points because the maximum number of codewords it can leave in the search space is two.

In Step 2, you repeat this process for every possible guess and pick one of the ones with the minimum “worst case scenario” response.

In Step 3, suppose that the guess is 4113 and the response is (1,2). The program should go through all of the possibilities and eliminate all of those which would not give the response of (1,2) when scored against 4113. That would leave 3151 and 1141 as possibilities.

FAQ

  • Q: Why does Knuth’s algorithm start with 1122?

    A: You should not focus on this starting point. It is a consequence of having checked all of the possible starting guesses using the same system that you use to make all of the other guesses.

    When you change the number of colors or the number of locations, a guess with all 1s and 2s is not necessarily optimal anymore.