Knuth's Mastermind Algoritm: "The last step"

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?

• if the 6^4 possibilities are to big an area to illustrate an understandable example. Then feel free to choose something smaller. Aslong as it is the same technique Nov 14, 2016 at 20:47
• What is wrong with the description at Wikipedia? BTW, if that game is intended for humans (rather than being some coursework), it won't be fun if the computer beats you every time in just 5 moves. Nov 14, 2016 at 21:26
• There is nothing wrong with the description except it is very briefly explained and not illustrated by an example. And i know it wont be fun to play against the AI. But it is a School assignment and one of my tasks is to program an AI that can solve the puzzle. So if could understand Knuth's theory then i would hold the key to make program that can do that. Nov 14, 2016 at 21:55

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.

• Thank you my friend! I now hold all the pieces i need to complete my AI! Nov 19, 2016 at 15:18