The way that Knuth's algorithm works is that it chooses the element of $S$ that has the best 'worst-case scenario' - that is, for a given $s\in S$, it computes (of all of the possible responses) which one would result in the fewest elements being eliminated from $S$; it then ranks the elements of $S$ by the number of elements thus eliminated, and chooses the one that eliminates the most.
An example might make this clearer. Let's choose a 'toy' example: four colors (1, 2, 3 and 4) and three peg slots. Then we start (semi-arbitrarily) with 123 as our guess; let's suppose that the result that comes back is one white peg and one black peg. Now, the (remaining) members of our 'valid choices' set $S$ are 112, 131, 134, 142, 221, 233, 243, 313, 322, 324, 413, and 421. We'll go through each of those in turn, imagining what could happen if we made that our next choice.
Suppose we were to choose 112 next. Then the possible responses are: three black pegs (in which case we win, of course), one white and one black peg (131), one black peg (134, 313, 322, 413), two black pegs (142), two white pegs (221, 421), and one white peg (233, 243, 324). Of these, the 'worst' response is if we get one black peg, in which we've gone from $\left|S\right|=12$ to $\left|S'\right|=4$, so the 'score' we assign to 112 is 8; no matter what response we get, we're guaranteed to eliminate at least 8 choices from our set $S$.
OTOH, suppose that we were to choose 134. Then the possible responses are: three black pegs again, one black peg (112, 233), two black pegs (131), one black and one white peg (142, 324, 421), one white peg (221, 322), two white pegs (243, 313), or three white pegs (413). Here, the worst-case scenario is that we get one black and one white peg, where we go from $\left|S\right|=12$ to $\left|S'\right|=3$, so we assign a score of $9$ to 134 because we're guaranteed to eliminate at least that many choices. Since this is higher than $8$, 134 is a 'better' move (by this algorithm) than 112 is.
We do the same thing for all the elements of $S$, assigning each one a score, and then at the end choose an element with the highest score. (If two or more elements are tied for the same score, the algorithm doesn't specify which one to pick; there are plenty of heuristics that you could use, though.)
Note that the overall running time to grade all the elements of $S$ is approximately $O(\left|S\right|^2)$ (plus some small additional time to bucket the responses); for each element of $S$ we check all the other elements of $S$ to find out which ones correspond to which replies. This isn't an especially efficient algorithm since the size of the original set $S$ is exponential in the number of slots, but it's not meant to be computationally efficient from the perspective of how long it takes to choose a move; instead, it's trying to minimize the number of guesses.
