next up previous
Next: Algorithm Up: Finding a needle in Previous: MasterMind: the problem


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:

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:

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 $3.9 \pm 0.5$ or $3.8 \pm 0.6$ 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].


next up previous
Next: Algorithm Up: Finding a needle in Previous: MasterMind: the problem

1999-06-23