The game of Mastermind is a constraint optimisation problem. There are two aspects which seem interesting to minimise. The first is the number of guesses needed to discover the secret combination and the second is how many combinations (potential guesses) we evaluate but do not use as guesses. This paper presents a new search algorithm for mastermind which combines hill climbing and heuristics. It makes a similar number of guesses to the two known genetic algorithm-based methods, but is more efficient in terms of the number of combinations evaluated. It may be applicable to related constraint optimisation problems.
Keywords: mastermind, stochastic search, genetic algorithms, games