MasterMind algorithm

The algorithm used by my MasterMind applet is very simple. Yet it is also very fast and it uses relatively few guesses. The algorithm consists of three parts: I will describe the algorithm for the standard MasterMind game with 4 positions and 6 colors. However, the same algorithm can be used for any number of positions and colors.

The basic algorithm

The basic algorithm is just a counter. I see the pins of the Mastermind game as digits and the position of the pins determine the position of the digit in a number. So in the standard case, I have a counter with four digits in the base 6 (i.e. the digits can have the values 0, 1, 2, 3, 4 and 5). I start the algorithm with the guess 0000 and record the reply. Then the counter is incremented until a value is reached that is possible given the previous guesses and replies. This is repeated until the code is found. If the counter overflows (i.e. gets at 0000 again), then there is no possible code and hence the adversary has made a mistake.

Improving the speed

The first improvement on the basic algorithm is to realize that most of the time, we can increment the counter with more than 1. As an example, suppose the reply to the first guess 0000 was 1 black and 0 white. Then it is easy to see that the first possible counter value is 0111. So many iterations can be skipped. In general, by comparing the current counter value with a guess and its reply, I can determine the highest digit that should at least change to get a value consistent with that guess. I do this for all previous guesses and get the highest digit that should at least change to get a possible value. I increment that digit (and set the lower digits to 0). Then I chack again whether this value is possible (and if not, which digit I must increment). This improvement GREATLY improves the speed of the algorithm since it skips most of the iterations. Furthermore, it gives exactly the same result (i.e. the same guesses) as the original algorithm.

Reducing the number of guesses

The second improvement on the basic algorithm is not to use the digits as direct representations of the colors. Before the start of a game, I generate a random color lookup-table for each position. So the same digit can mean a different color in each of the positions. This does nothing to improve the speed of the algorithm, but it greatly improves the quality (i.e. information content) of the first guesses. As a result, the number of guesses is significantly reduced. Also, it makes it difficult for the adversary to adapt his code to the algorithm.

Results

The results of this algorithm are as follows:
1 try 0.08%
2 tries 0.94%
3 tries 7.84%
4 tries32.83%
5 tries43.20%
6 tries13.99%
7 tries 1.09%
8 tries 0.03%
The average is 4.65 tries.

I do not include speed measurements, because they are to dependent on the platform that is used. However, by comparison with other MasterMind algorithms I can say that it is very fast.

Theoretical results and possible improvements

The theoretical optimum is an average of 4.34 tries with a worst case of 6 tries. However, this optimum sometimes requires guesses that are not possible codes according to the previous guesses/replies. Still, these 'impossible' guesses have so much information content that they do reduce the average and maximum number of guesses. This theoretical optimum has bee calculated by searching all possible code/guesses combinations, which is not a feasible approach for a MasterMind playing program.

I think the quality (i.e. number of guesses) of the above algorithm could be improved by using first guesses that have more information content. It will be very difficult though to find a method that works well (and fast) in the general case (i.e. for any number of colors and positions). I don't think the speed of the above algorithm can be much improved upon in the general case.