State of the art

After the first paper by Donald Knuth [1] was published in 1977, being the first known algorithm to solve MasterMind, lots of papers have been published with many different approaches. They usually fall into one of the following categories:

*Stepwise optimal*: each guess is optimal in the sense that it is possibly the right answer, that is, it is consistent with all guesses made so far (for instance, it coincides at most in 1 peg with those that have been answered 1 black pin, and so on). In this case, there is not a boundary for the number of guesses that will be needed, other than it will be finite. It must be finite, since each guess and its answer rule out a non-zero set of combinations, and each new combination must be extracted from that set; the number of possible combinations is reduced each step, and then, finally, only one is possible.*Strategically optimal*. In this case, combinations which are known to be incorrect are played, with the intent of extracting information about the shape of the hidden combination, or reducing further the remaining search space. A game of this type would go like this: the first combination would be composed of only one color; the second of the next possible color, and so on. Or else, play a combination with all possible colors in the first place, then shift it left, until a cycle has been completed. After a group of šnon-optimal'' combinations have been played, then the correct solution is deduced analytically. The advantage of this approach is that it is guaranteed to find the solution in a fixed amount of guesses; the problem is that usually that number is higher than the optimal one, and thus, as has been mentioned in section 1, they would be worse players in general. This strategy was used originally in Knuth's paper, and is often mentioned in Usenet posts, such as [8].

If the stepwise optimal strategy is the choice, there are several
possible ways of choosing the next move in a consistent way (we will
call this move *consistent*), that is, such that is possibly the
secret code. To achieve that, the new guess is checked against all
guesses, and it must have as many black and white pegs with respect to
them as the played guess has against the secret code, that is, it must
have 0 score (see section 1 against them. Here are some possible strategies:

*Exhaustive search*considers one by one all possible combinations, and rules out those that are not consistent with the set of played guesses. There are many ways of running over the search space, depending on where you start and how you follow, but one possible way is playing a random combination to start, and then start considering the next number-wise; that is, if the combination played has been 1112, the next would be 1113, up to 1116, and then 1121, and so on. This can be further improved by using some heuristics to rule out combinations: for instance, if a combination got no white and no blacks, combinations with those colors will inmediately be ruled out. The great advantage of this approach is that it is guaranteed to find the solution in finite time, and it runs over the search space only one time. On the other hand, all search space must be stored, which will take as many bytes as possible combinatios, not a problem for the 4x6 game (4 pegs, 6 colors), which only uses 1296, but impossible for the generalized game; for instance, a 10x8 game would need exactly 1 terabyte (1024 terabytes) of storage. This approach has been taken, for instance, by Koyama [9]*Random search*randomly generates combinations, and plays the first that is found consistent. Once again, some combinations can be ruled out before being checked, but that would produce only a marginal improvement. On average, this approach will generate as many combinations each guess as the number of consistent combinations divided by the search space size. That depends on the game, but, in general, in could be said that the search space will be searched more than once. On the other hand, memory used is almost negligible, since only one combination and the set of played guesses need to be in memory at once. This approach has been taken, for instance, by [10], who built a calculator using a microcontroller to play mastermind.

The first paper known about the subject, by Knuth [1], used
an strategy of the second kind. Each guess was made so that it
minimized the maximum number of remaining possibilities; if several
guesses met this condition, and one of them was a ``valid'' pattern,
that is, that could make ``all blacks'' possible, that was the one
used. This allowed to solve the game in, at most, 5 guesses. The
expected number of guesses is 4.478. This result was further improved
by Irving [11] and Neuwirth [12] to 4.364. None of this strategies have
been proved to be optimal, so there was further room for improvement,
and indeed, Koyama and Lai [9] lowered that bound to 4.340
if five guesses were allowed at most, and 4.341 if 6 guesses were
allowed. Koyama and Lai use an exhaustive computer search. Chen and
coworkers [5] generalize these results to the general case of
*n* colors and *m* positions, obtaining upper and lower bounds for the
number of queries that should be made to find the hidden code; they
also give an algorithm that uses binary search. This paper improves
previous bounds found by [13].

Bestavros and Belal [14] use information theory to solve the game: each guess is made in such a way that the answer maximizes information on the hidden code, be it on the average or in the worst case. With that algorithm, they find the hidden code in or average combinations in the standard game (4 positions, 6 colors). This result is consistent with Knuth's, but it is a clear improvement over it. Variants of the Mastermind game have also been researched by Flood [15] and Ko and Teng [16]. Other approaches have also been reviewed in [17].

In fact, the game of Mastermind has been approached several times using genetic algorithms. One of the authors used genetic algorithms and simulated annealing [7,17] to solve the generalized mastermind problem. In the first paper and in the SA algorithm in the second paper, a non-optimal strategy was used, by playing a combination known not to be the best, if no proper solution was found in a fixed time; the GA in the second paper used only guesses known to be optimal, at the cost of a higher average time to find the solution, but with less guesses made. In bot cases, the fitness of each combination in the GA were computed from the rules that the combination met, with more importance given to combinations with more black pegs. A suboptimal approach was also used in a paper by Bento et al. [18]: each generation, the best combination was played. Each combination had a fitness computed as the difference between the number of black and white pegs the last played combination was awarded and the number of black and white pegs of the combination with respect to this last played combination (as has been shown in section 1. Since this algorithm does not play optimally, it obtains an average of only 6.866 (no standard deviation is quoted).

In this paper, we try to solve the general mastermind case using genetic algorithms, by playing a stepwise optimal strategy, and by using a fitness function which is different from that used in previous papers [7,17] and similar to the one used by Bento [18].