Mastermind (board game) - Five-guess algorithm

The algorithm (from here) -



-
Create a set S of remaining possibilities (at this point there are 1296). The first guess is aabb.

-
Remove all possibilities from S that would not give the same score of colored and white pegs if they were the answer.

-
For each possible guess (not necessarily in S) calculate how many possibilities from S would be eliminated for each possible
colored/white score. The score of the guess is the least of such
values. Play the guess with the highest score (minimax).

-
Go back to step 2 until you have got it right.


I confused about the 3nd step -

what is mean -


how many possibilities from S would be eliminated for each possible
colored/white score

what is the "correct answer" and the "guess" here ?

Can someone clear it some more ?

The text you quoted seems clear as it is. But I'll try to elaborate on step 3, since you asked:

Let $S$ denote the set of possible secrets (given responses to moves you've made so far). Given a candidate guess $g$, you run over all possibilities $s \in S$ and calculate the response that you'd get if you guessed $g$ and the secret was $s$ (the number of black pegs and the number of white pegs); this is "the colored/white score". Now, for each colored/white score that could be received, if you were to get that score, you could eliminate some possibilities from $S$ as incompatible with that colored/white score; the "goodness" of a colored/white score is the number of possibilities eliminated. The "helpfulness" of a candidate guess $g$ is the minimum of the "goodness" of all the colored/white scores you could possibly get, in response to $g$. Select the guess $g$ with highest "helpfulness".

In other words, let $R(g,s)$ denote the number of black pegs and number of white pegs you'd get if the secret were $s$ and you guessed $g$ (this is what your quote calls the "colored/white score"). Let $Z(g) = \{R(g,s) : s\in S\}$, so that $Z(g)$ denotes the set of "colored/white scores" you could possibly get if you made guess $g$ (given that the secret $s$ has to be one of the possibilities in $S$). Now, if you have a "colored/white score" $z$ where $z \in Z(g)$, let

$$G(g,z) = |\{ s \in S : R(g,s) \ne z\}|,$$

so that $G(g,z)$ is the "goodness" of getting a "colored/white score" $z$ in response to guess $g$. Also, let

$$H(g) = \min \{G(g,z) : z \in Z(g)\},$$

so that $H(g)$ denotes the "helpfulness" of a candidate guess $g$.

Now step 3 says: you should play the guess $g$ that maximizes $H(g)$.

StackExchange Computer Science Q#18749, answer score: 4