Genetic Algorithms Playing Mastermind

Abstract

This thesis discusses the game Mastermind and a number of strategies that can be imple- mented to solve this NP-complete problem. First, four different types of algorithms that can be used will be discussed and examples will be given for each one. These algorithms will then be compared with each other. One of these algorithms, the GA presented by Berghman et al. (2009), will be discussed in detail and tested for its scalability, along with a few variations on said algorithm. This algorithm scales relatively well; one of its variations scales even better and is therefore suited for solving Mastermind even for larger problem parameters. In order to obtain a better understanding of the performance of the algorithms tested here, in terms of the number of guesses needed to solve the problem, a follow-up study is required. It is clear however, that in terms of computation time and scalability this GA and its variations perform well compared to many others.