MasterMind: the problem

In general, the generalized mastermind problem can be formulated as a
search for a hidden code which uses hints provided by a black box. In
particular, the code and the guesses are extracted from an alphabet
with cardinality *N*; each guess and the code have length *L*. Search
space size is *N*^{L}. The board game that is sold has two variants: the
``classic``, with *N*=6,*L*=4 and the ``super MasterMind'' with
*N*=8,*L*=5. In the first case, search space size is 1296 and in the
second 32768. Each ``hint'' in the shape of black and white pins
provided by the codemaker restricts the search space, ruling out some
of the combinations of that search space. However, since the search
space is multi-dimensional, it is not straightforward to compute the
subspace that has been ruled out by the hint.

However, within that subspace, each combination can be scored by computing how many hints it meets, or how close it is to meeting those hints. For instance, in the situation shown in figure 2, the combination in the bottom row would have a score of -2, because that is the distance that separates it from being consistent with the guess made in the middle row. A combination that meets all rules, or answers to guesses made so far, would have a score of 0.

Formulated in this way, finding the hidden combination is a combinatorial optimization problem: each combination has a score, and that score has to be maximized (to a maximum of 0) for each guess. And, as such, it bears resemblance with other computational problems:

*Circuit testing*: each manufactured circuit includes a module for self-test; the problem of generating patterns in such a way that it covers most of the faults with a minimal amount of patterns is similar to an*inverted*mastermind: that is, find the set of combinations that would be able to find a given secret code. Indeed, this problem has already been approached using GAs in [2].*Differential cryptanalisis*is similar to MasterMind: combinations of letters in an alphabet is submitted to a ``black-box'' encrypting device, and the encrypted output is analyzed to crack the key; once again, the problem is to compute a set of combinations that allow to extract maximal information from the ``black box''. In fact, many of the posts that deal with MasterMind in the*sci.math*Usenet forum are also cross-posted to*sci.crypt*, the forum about cryptography.*Additive Search Problem*is like a MasterMind in which only the pegs in the correct position, and also which is that position, are answered to each combination. This problem has been solved using genetic algorithms in [3]. In that paper, the similarity to the ``Royal Road'' function [4] of both problems is also mentioned- In [5], MasterMind is mentioned as a variant of the
*on-line model with equivalent queries*; in this model, when an incorrect hypothesis is proposed, the oracle responds with a counterexample to the hypothesis. Then, as in the case of MasterMind, the algorithm proceeds to form the next hypothesis (or combination) using the information obtained from the incorrect queries.

Any conclusion obtained for MasterMind may then be applied, although
probably not directly, to any of these problems, as well as any other
combinatorial optimization problem. Asking about a solution to the
game of MasterMind is so popular that it has become a FAQ (frequently
asked question) for the *sci.math* usenet forum, since at least
1994 [6]. All this would answer the question
posed by an anonymous referee that reviewed our first paper on
MasterMind [7]: ``Why would anyone want to solve the game
of MasterMind?''.

In fact, we could give some other answers to this question: since the
first version of the algorithm is working on the Internet (back in 1995), it has
received tens of thousands of visits, it is been mentioned on AI
articles, also as an example of board games using artificial
intelligence in the AI games web site (*http://www.gamesai.com*);
solving MasterMind using GAs (and other AI techniques, such as
Simulated Annealing) is also a popular assignment in basic-level artificial intelligence courses. Several
graduate students from all the continents have written the authors
requesting information on MasterMind to solve it for their Master
thesis. The web site itself ( *http://kal-el.ugr.es/mastermind* ) is a popular demo of genetic algorithms at
work. But it could improve, and that is what we present in this paper.

The rest of the paper is organized as follow: in section 3 we show the state of the art in solving MasterMind by algorithmical means; then we present the the evolutionary algorithm used in section 4, and the results obtained with this new algorithm, comparing it with the old one in section 5. Finally we discuss results and propose new lines of research in section 6.