Knuth's Mastermind Algoritm: "The last step"

Question

I have recently programmed a mastermind game and now I need to program an AI that can solve the puzzle.

I have read a lot of guides on this algorithm of Donald Knuth which apparently can solve the puzzle in 5 moves.

So i have come so far now that:

1. I have created a list of all 1296 possiblities there are in mastermind. Mathmaticians refer to this as S
2. Then I have created a function that removes all the elements from the list S that wouldn't give the same result/response if your guess was the Mastercode.
3. Then i pick a random value from the remaining elements of the list S and repeat the process. untill I only have one possibility left.

This makes my AI complete the code in 3-8 guesses. Mostly 5-6 guesses. Though i think my 3rd step is not correct. Can someone specify how i should choose the next guess?

Answer 1

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.