Mastermind (board game) - Five-guess algorithm

Problem Detail: 

The algorithm (from here) -

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

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

3. 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).

4. 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 ?

Asked By : URL87

Answered By : D.W.

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)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18749