Solving Mastermind

A question was posted online recently about the best strategy for winning the game of Mastermind. Mastermind is a game played between two players, a Code Maker and a Code Breaker. The Maker makes a code of colored pegs, and the Breaker has to guess the code. After each guess, the Maker gives feedback of how many of the pegs were the right color in the right place and how many are the right color in the wrong place, indicated by black and white pegs in the board. The Breaker then makes another guess.

The parameters of the game are how many possible colors there are, how many pegs are in the code, and whether the same color is allowed to be repeated in the code, as in (4 of 6, repeats).

Donald Knuth wrote a paper on optimal play for the Breaker and showed that in four pegs in the code of six possible colors with repeats, it can be solved in no more than five tries. Donald Knuth is a deity of Computer Science, having written The Art of Computer Programming. I wrote a program to implement Knuth's algorithm in C#. It also creates a table at the end of how to make perfect play.

In my program, I replace colors with numerals since the colors are arbitrary. I have placed the code on GitHub. You can try the suggested algorithm on this site.

The program uses a MinMax algorithm, which finds the code that will reduce the number of possible remaining codes on each play. Because of the way it works, sometimes it will make a code that might not actually solve it on the next play, but instead guarantee that it solves it in the least number of tries. There are some other algorithms that will solve it in a smaller average number of tries, but possibly having a larger maximum.