Solving Mastermind Logically

Many of you know that I love logic puzzles, and that artificial intelligence fascinates me. These two interests go hand-in-hand, and both are complemented by my passion for programming. I have at various times tried to write programs to either generate or solve different kinds of logic puzzles, including tic-tac-toe, Sudoku, Lights Out, and Mastermind. I even wrote some notes about the expected value of a Yahtzee game (while taking a statistics class) as part of an effort to pit two “smart” computer players against each other in Yahtzee—though that had more to do at the time with statistics than artificial intelligence, so I digress.

Sadly, many of my efforts never generated full working solutions, but I sure did have fun trying. The interesting thing about implementing any kind of artificial intelligence, even very simple machines, is that it is usually far easier to explain how it should work to another person than it is to make the computer behave correctly. This is a testament to the incredible computing power our brains actually possess, but it also poses a challenge that I love trying to overcome, even just for the sake of it. So today, I’ve decided to write out my simple explanation for solving Mastermind, which will hopefully prompt me to finish writing my solution.

Mastermind is a relatively simple logic game. (Side note: wow, that Wikipedia link just gave me a bunch of ideas, particularly because of Knuth’s five-guess algorithm. That dude is a genius.) The game seems intimidating to some people, but it is really far easier than almost any game I can think of. This is because there are no time limits and only two rules:

1. A black peg means you have a correct color in the right place.
2. A white peg means you have a correct color in the wrong place.

That’s all there is to it. All you need to do is choose pegs that do not violate any of those rules for any of your guesses so far. Everything else is random (ignoring the optimizations possible with Knuth’s five-guess algorithm, or the six-guess one also from the article). In order to play the game, you need to follow only two steps:

1. Choose random colors for pegs that you assume to be wrong.
2. Arrange your current guess in a way that doesn’t violate either of the rules above.

As long as you don’t have any guesses that don’t fit with the “grade” pegs you get from any previous guesses, then you will solve the puzzle in a perfectly logical fashion. It may not be the optimal solution, but it is certainly logical. Try a quick online version here if you want to try it out.

The problem with writing a program to actually solve a puzzle is making the program intelligently follow those two steps above, particularly #2 (step #1, choosing new random colors, is usually really easy). Depending on which language you choose to write your solver in, it could be more or less complicated. The logic is the same, but some languages really lend themselves to that kind of coding. The absolute best language I know of is Prolog, because it has a built-in logic engine. I can’t imagine how it works behind the scenes, but it’s incredibly capable. There is an elegant Prolog Mastermind solver here if you want to check it out.

I had a Prolog class in college, which was fascinating but sadly not enough to make me confident enough to try writing a program of that complexity, even though it’s probably not that complex as Prolog programs go. I’d love to learn more about the language, and Mastermind would be a great exercise, but I want to use a language I’m familiar with. For me, that means C/C++ or PHP. I’ll probably go with PHP, because I don’t care for speed (yet) and I have to deal with multidimensional arrays, which are way easier with PHP.

Programmatically, to make sure any guess doesn’t disagree with any previous set of grade pegs, you need to track the information given by each grade. Each grade gives you two categories of information:

1. Which color/position arrangements are possible
2. Which color sets are impossible

These two types of information are recorded and used very differently. Each graded guess will give you a different set of information for each category, and the quantity of information available depends on how many black and white grade pegs you get. For example, say you have a puzzle whose solution is:

…and your guess is:

The red is the right color in the right place, and the blue is the right color in the wrong place, and the last two are simply wrong colors. Therefore, that guess would receive a grade of 1 black and 1 white peg. What exactly does this tell you? Well, in simple terms, it tells you part of what we already know: you have one right color in the right place, and another right color in the wrong place. However, since you hypothetically don’t know the solution yet, that grade doesn’t tell you which of your guess positions the grade pegs apply to. So, from the computer’s perspective, that grade tells you exactly this:

1. Possible color combinations: (based on 1 black, 1 white)
   1. #1=Red, #3=Blue
   2. #1=Red, #4=Blue
   3. #2=Blue, #3=Red
   4. #2=Blue, #4=Blue
2. Impossible color sets: (based on 2 grade pegs)
   1. Red, Blue, Black
   2. Red, Blue, Orange
   3. Blue, Black, Orange
   4. Red, Blue, Black, Orange

This is not that difficult to determine automatically. If you work out the possibilities manually though, it can definitely be a pain. You might also discover that a grade of exactly two white pegs is the least helpful grade you can possibly get, since all you know is that two of the four colors are in the wrong place. This is less helpful than exactly one white peg (which tells you that three pegs aren’t in the solution at all), and exactly three white pegs (which tells you that three of the pegs are in the solution).

The key is to take each of these sets of information and run new guesses through them like filters. Each potential new guess must fit with all previously gathered information, or it must be tossed out. If it fits, then it’s logical, and you can proceed to get a new grade.

A program to solve a Mastermind puzzle has to repeat this process over and over until it finds the solution. It doesn’t seem so bad explained like this, but all (both) of my previous attempts at an implementation failed. One of them came really close, but something about it wasn’t quite right. Maybe the publication of this post and my renewed interest will encourage me enough to fix it and finish, so I can post something more concrete for you all, like an actual solver that you can run online.

On a separate note, those of you paying any attention at all probably noticed that my blog layout changed again. I really like the old one (a very dark theme with light text), but as nice as it looked, it was kind of hard to read because of the contrast. I may try to fix it and maintain much of the old theme, but for now, I like this new one enough to keep it.