Knuth's mastermind algorithm

Question

I read the other thread regarding Knuth's algorithm and mastermind but I still do not understand quite how it would be implemented. I am confused by the language or my brain is just broken (or both).

I understand that you start with a list S of all possible permutations based on the particular game's parameters, for example a list of 1296 possible 4-digit combinations where each digit can be a number 1-6 (including repeats).

You create a 4 digit secret code.

You play a guess (from the list S) against the secret code and receive a response in terms of black and white "pegs", where each black peg means the guess has the right digit in the right spot, and each white peg means the guess has the right digit in the wrong spot.

According to Knuth, you should always use 1122 as the first guess, from which you get a response in terms of black and white pegs.

Then, in order to reduce the number of possible guesses for the next turn and eventually find the right code, if the response is not 4 black pegs (meaning the code has been guessed correctly and the game's over), we are to remove from S any element (guess, code, whatever you want to call it) that would not give the same response if it (the guess/code/element in S) were the code.

What does that mean? Is anyone else confused by that wording?

I do not understand what comparison is being made here. To me, this means that if the response to the first guess of 1122 is one black, one white, we would remove from S all of the potential guesses that, when played against the secret code, would not return the same response of one black, one white. That would of course leave us with a list of possibilities that would not contain the correct answer, because it would just be a list of elements that would all get a response of one black, one white.

So I see that obviously that can't be what it means, so the alternative is to say "OK it must mean that you should remove from S every potential guess that also returns the one black, one white) answer and go from there." That makes more sense than my initial interpretation but it still doesn't feel right.

Can anyone help explain this using multiple examples? I cannot wrap my head around what comparison is being made and what two things are actually being compared in order to remove elements from S.

Answer 1

Let's say $S_i$ is an element of $S$, the possible values of the winning code.

What you're asking of each $S_i$ at the step you're puzzling about is this:

If the answer were $S_i$, would I have gotten the response I got with my current guess?

If the answer is no, then $S_i$ cannot be the code, because you would have gotten a different response. If the answer is yes, then you keep that around for another turn, because it's consistent with the response you got. In other words, you can't eliminate it as impossible.

Looking at the example in the other thread:

You guess $1122$ and get one black peg (one peg color correct and in the right position) and one white peg (one peg color correct but in the wrong position).

The step of reducing the list involves asking, for every $S_i$, "Would I have gotten one black peg and one white peg with my guess of $1122$ if the code were $S_i$?"

OK, so let's do a few:

• If the code were $1111$ I would have gotten two black pegs ($BB$) with my guess of $1122$, which is not the same as one black peg and one white peg ($BW$). (Represent this by $F(1122, 1111) = BB$.) So, I remove $1111$ from the list of potential solutions.
• $F(1122, 1112) = BBB \neq BW \to \text{Remove 1112 from S}$
• $F(1122, 1113) = BB \neq BW \to \text{Remove 1113 from S}$
• $F(1122, 1114) = BB \neq BW \to \text{Remove 1114 from S}$
• $F(1122, 1115) = BB \neq BW \to \text{Remove 1115 from S}$

And so forth.

However,

• $F(1122, 1314) = BW = BW \to \text{Keep 1314 in S}$

Hope this helps.

Answer 2

I had the exact same comprehension problem as auxwalter when I was trying to write a Mastermind program. Thanks to John's answer and to auxwalter for asking this question, I was able to figure out what I was doing wrong.

Initially, I mistakenly eliminated from set S all elements that did not provide the same clue as the initial 1122 guess. Then, much like auxwalter, I tried the alternative they mentioned — I removed from S all elements that did provide the same clue. That didn't work either (well, maybe 1/5 times the computer would correctly guess the code).

The key point to understand is that set S is not the set of potential guesses, it's the set of potential codes. If your program "plays a round" for each element of S in order to retrieve the clue and discard/keep each element based on that clue, then the code needs to be defined as the element for each iteration — not the guess.