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
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.
- a basic algoritm
- an improvement to increase the speed
- an improvement to reduce the number of guesses
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.
The results of this algorithm are as follows:
The average is 4.65 tries.
|1 try || 0.08%|
|2 tries|| 0.94%|
|3 tries|| 7.84%|
|7 tries|| 1.09%|
|8 tries|| 0.03%|
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.