3
$\begingroup$

I'm reading about Knuth's algorithm to solve the mastermind game, so I've looked in wikipedia and read the pseudo-code (http://en.wikipedia.org/wiki/Mastermind_(board_game)#Five-guess_algorithm).

I have a question about step 3 in the algorithm, "Remove from S any code that would not give the same response if it (the guess) were the code".

How would this estimation (of which codes would not give the same response) be "performed"? Obviously we can't ask for responses for each of the codes in S, that would just be brute force.

Thanks!

$\endgroup$
3
  • 1
    $\begingroup$ The algorithm isn't guaranteed to be fast; just to be correct. You can indeed iterate over all of the codes in $S$ and check each of them against the response. $\endgroup$
    – Steven Stadnicki
    Dec 13, 2014 at 2:47
  • $\begingroup$ @StevenStadnicki Hi, thanks for the answer. But to get a response for each of the remaining $O(|S|)$ codes, wouldn't that cost me $O(|S|)$ guesses? It doesn't seem (to me, which doesn't say much) that there is a way to determine if the responses for two codes are the same, given the response of only one of them, so we would have to submit the second one as a guess, no? $\endgroup$
    – Ana M
    Dec 13, 2014 at 2:55
  • 1
    $\begingroup$ Ana M: you don't need to guess - you just need to match the remaining codes against your most recent guess and determine whether they would give the same response. For instance, suppose your first guess is '1122' and you receive one black peg and one white peg. Then you would remove '3422' from your set $S$, since if that were the actual code then your '1122' response would have netted you two black pegs, but you would keep e.g. '2134' in $S$ since that fits the one black peg, one white peg result. $\endgroup$
    – Steven Stadnicki
    Dec 13, 2014 at 3:06

1 Answer 1

Reset to default
3
$\begingroup$

The idea is that $S$ maintains the set of all possible codes that you could be guessing at, so after each guess you iterate through the remaining elements of $S$ seeing how they stack up against the (most recent) guess you've made and rejecting those that don't fit the response you got. For instance, if your first guess is 1122 and you receive a response of one white and one black peg, then you'd remove 1134 from $S$ (since if that had been the actual code you would have gotten a different response, namely two black pegs), but you would keep 2134 in $S$ (since that code is consistent with the response of one black, one white to 1122). You're constantly asking the question 'if this were the master's code, what would the response to my guess have been?' of all codes in $S$, and that calculation — while inefficient — doesn't require any guesses at all.

$\endgroup$
7
  • $\begingroup$ The actual algorithm says that we need to (at each stage) compare against all the values in the initial set and not the pruned set S that we get after every step. Any idea why that's the case? $\endgroup$
    – dhruvbird
    Oct 7, 2016 at 17:09
  • $\begingroup$ There is something that doens't make sense here. Your explanations assumes that you know which values in your guess 1122 is represented by the black and white pin. Mastermind doens't work like that. I mean it could be any one of the 4 values that triggers the black and white pin. It could be be the first 1 that is the black and the second 1 who is the white. As i can figure in your example then you just assume that the second 1 is the black pin and one of 2 is the white pin. but how would you know? $\endgroup$
    – Nulle
    Nov 14, 2016 at 18:46
  • $\begingroup$ @Nulle Not at all. You're keeping every element in the set $S$ that would give the response that you get, and that doesn't require any of the knowledge you're talking about. For each code in $S$ I just ask (myself) 'if this were the real code, and I guessed 1122, what would the result be?'; I can do that without any knowledge of the actual code, because I can follow the rules of the game just as well as the mastermind themselves. 2134 there is just one example, but I would also keep e.g. 3412 in $S$. $\endgroup$
    – Steven Stadnicki
    Nov 14, 2016 at 18:50
  • $\begingroup$ So how do you determine what the next guess should be? $\endgroup$
    – Nulle
    Nov 14, 2016 at 20:11
  • 1
    $\begingroup$ @Nulle That's step 6 in the algorithm that OP links to, but that's moot to the question here. In brief, you go through your set $S$ of still-valid possibilities and pick the one that's guaranteed to eliminate the largest number of possibilities regardless of what the actual response is. $\endgroup$
    – Steven Stadnicki
    Nov 14, 2016 at 20:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .