Knuth's Mastermind Plan

If you've never played the classic Mastermind board game, take a quick look through the rules before continuing.  This post will make a lot more sense.

Programming's Mafia boss "Don" Knuth devised a way for all of us geeks to never get invited to parties again win at Mastermind in five moves or less.  The premise is basic: Keep track of the moves that remain.  When you've only got one left, you win!  A trained monkey could do it.

Naturally, this simple solution isn't the one that Knuth came up with.  Simply taking the first possible answer as the next guess results in a worst case of 7 moves, vs. Knuth's 5 [0].  What Knuth has done is run through all of the possible states and find the optimal guess at each state.  Sometimes, like the example on page three, the optimal guess isn't actually one of the remaining possible guesses.

Pages four and five contain his entire table, using his propitiatory notation.  While this works great, it's a bit difficult to point a program at a PDF and say "go."  Instead, I've created a JSON version that works just as well with a few adjustments to the code.

At this point, I've got a cute little implementation that solves the generic Mastermind board and will bore everyone to tears explaining it at the next party I attend.  Inevitably, some smart aleck will say "Well, what if there are seven colors?  Where is your Knuth now?"

I have three options at this point:

1. Hide under the nearest bed
2. Punch them in the face
3. Write up an even better algorithm and blog about it.  That'll show 'em.

The core of Knuth's algorithm is the idea of min/maxing possible results.  Programming Praxis has a much better explanation of this, but if you're afraid of clicking links, each possible guess is investigated, along with the potential remaining possibilities with each response.  Whatever guess results in the lowest number of possible remaining guesses at the high point is chosen for the next guess.  Sweet.  We totally showed that jerk.

"Fine" says the critic "You know what it is.  But can you do it?"

My attention is rapidly waning at this point but the challenge has been made.  I slam out some lines of code but am not Knuth.  Still, I sit satisfied that I've done something.

Think you can do better?  Fork me.  Got a comment?  Comment.  Want more of this?  Twitter.

[0] You can prove this by visiting my github page and running `testRig.runKnuthTest()` and `testRig.runBruteTest()` in the console.  You can disprove it by finding bugs in my code.