The Welcoming Committee

If you are unfamiliar with the Mastermind board game, I suggest checking out the Wikipedia article on the subject and perusing the internet for an online flash variant of the game.

In brief, the game is this: There are two players, one who makes codes and one who tries to break them. A code is made of colorful pegs. In the traditional game, a code was made of four pegs each of which could be any one of six colors; there are 6^4 (1296) such codes. To play, the code breaker would assemble a code and offer it to the code maker as a guess at the answer. The code maker would respond with the number of pegs in the guess that exactly matched pegs in the secret answer (so, by position and color). The response would also include how many of the remaining pegs belonged in the answer but were in the wrong position; the remaining quantity of pegs simply did not belong in the answer. The code breaker would use this feedback to make a second guess, then a third, and so on. If the code breaker guessed the correct answer before a certain number of turns had elapsed, they won. Otherwise, they lost.

This program tries to determine efficient strategies for playing mastermind under different configurations of the rules. How many turns does it take to beat the traditional game? What if pegs can be one of eight colors instead of just six? What if we want to beat the game in the shortest average number of turns rather than reliably beat the game in a certain number of turns?

The original implementation of this program followed its predecessors by implementing a greedy algorithm which sharply curtailed the amount of work necessary to arrive at an answer. While this was fast and useful, it was not necessarily optimal. The current draft is very configurable, the objective of which is to allow the algorithm to answer a variety of questions. Ideally we will be able to evaluate the traditional game exactly, and hopefully "larger" games than that as well.