next up previous
Next: State of the art Up: Finding a needle in Previous: MasterMind, the game


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 NL. 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.

Figure: Example of how combinations can be scored. The top row shows the hidden combination, the middle row one of the combinations the codebreaker has played and the answers. The bottom combination has to be scored against the middle row. In principle, it would not be consistent with the combination played: while this one coincides in only one place and one color with the hidden combination, the combination to score coincides in 3 places with it, so it would not meet that rule. However, only 2 pegs would have to be changed to meet the rule, so that would the ``distance'' to a correct combination; the score would that be -2.
\begin{figure}
\vspace{0.3cm}
{ \psfig{figure=hidden.ps,width=2.5in}\vspace{0.3c...
...}
\psfig{figure=guess3.ps,width=2.5in}}
\vspace{1in}
\vspace{0.3cm}
\end{figure}

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:

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.


next up previous
Next: State of the art Up: Finding a needle in Previous: MasterMind, the game

1999-06-23