11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You don't create a 4-digit secret code. Your opponent does. Perhaps this is the source of your confusion. $\endgroup$ – TonyK Mar 16 '15 at 22:40
  • $\begingroup$ Thanks TonyK but no, that is not the issue. I understand how the game works, I am just trying to understand the logic of Knuth's algorithm. I was hung up on the language used to describe narrowing the list of S which I would argue is ambiguous (at least as it exists in the Wikipedia article). $\endgroup$ – auxwalter Mar 17 '15 at 4:57
  • $\begingroup$ There's comprehensive explanation on this link for all mastermind strategies: serkangur.freeservers.com $\endgroup$ – Donald Knuth Jun 6 '16 at 16:42
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ok I think this has helped me understand my hangup -- when removing elements from S, rather than bumping each element in S against the actual secret code, we're bumping each element in S against the most recent guess. So once we start eliminating the elements from the list of S we're basically forgetting the real code for a moment and comparing each element to the most recent guess? $\endgroup$ – auxwalter Mar 17 '15 at 4:53
  • $\begingroup$ Yes. The actual secret code is in $S$. Each guess is in $S$ (or should be if you're playing to win!) and eliminates a bunch of candidate secret codes based on the response. This reduces the number of members in $S$, and you guess again (again, using one of the remaining members of $S$) until you win. $\endgroup$ – John Mar 18 '15 at 19:23
  • $\begingroup$ "If the code were 1111 I would have gotten two black pegs" how do you know that? you might aswell have ended up with 0 blacks and 0 whites. Taking into account that we dont know if the black peg represents the 1 or the 2 value. and you also dont know if it is a 1 or a 2 that is out of position. $\endgroup$ – Nulle Nov 14 '16 at 20:19
  • 1
    $\begingroup$ @Nulle Earlier in my answer I wrote: "You guess 1122 and get one black peg ... and one white peg ..." Based on this particular guess (1122) and the response to this guess (one black, one white), the actual code cannot be 1111. $\endgroup$ – John Nov 14 '16 at 23:12
  • $\begingroup$ I don't think it's quite as simple as this. Knuth was rather considering, for each possible clue that a code might receive, how much the remaining possible codes would be reduced. Knuth actually pointed out that the code to guess next might actually be impossible based on previous clues, yet would still most reduce the potential codes remaining and should still be guessed (that is, even knowing that it is not the correct code) to ensure that the correct code is actually guessed within five guesses. $\endgroup$ – Richard Ambler Aug 1 '18 at 2:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.