Figure 1 - The Game of Mastermind played by the computer
After writing the Genetic Algorithm Article for implementing a Genetic Algorithm in C#, I tried to think of a good example of how to illustrate a real-world use of Genetic Algorithms to illustrate artificial intelligence. It dawned on me that Mastermind could be played completely by the computer using AI. Looking back at my Mastermind Game in C# (also check out Jigar Desai's Mastermind game, a much more graphically pleasing and user friendly version), I thought it would be easy enough to drop in the Genetic Algorithm stuff to produce a feature in the game that allowed the computer to give a best guess for the current row. The design of the incorporation of the Genetic Algorithm classes into the game is shown below:
Figure 2 - UML Design of AI Mastermind game reverse engineered using WithClass 2000
I extended the Genetic Algorithm library, by creating a MasterMindPopulation and MastermindGenome class to work specifically with Mastermind color arrays. There is actually very little difference between a MastermindGenome and a ListGenome except for the Fitness Function and how a MastermindGenome converts itself into a string. The AutoPlayer class encapsulates most of how the MastermindGenome calculates its fitness function to product the computers guess. The MastermindGenome also uses the Board and the ScoreBoard objects to compute its fitness function.
So how do we go about having the computer player calculate a fitness score that illustrates a fitness of the next best guess for the current row on the Mastermind Board? Believe it or not, I stayed awake at night trying to figure this one out. It turns out that its not really that hard. To calculate the fitness for the next guess on the board, simply compare the current genome values against the score for all known turns on the board. For example if row #1 has two white pegs, then the Genomes that produce two white pegs compared against row #1 get a perfect fitness for that row, because the unknown final answer we are trying to match against also matches row #1 with two white pegs. Repeat this test for all of the rows on the board and add up the fitnesses for all of the rows. This is the final fitness number. Below is the Fitness function in C# in the MastermindGenome class
private float CalculateFromMastermindBoard()
{
// cycle through all of the current rows on the board and calculate a fitness score
// based upon how each of the guessing row's peg score matches against the Genome
// as if the Genome were the current solution
float fFitnessScore = 0.0f;
for (int i = 0; i < TheBoard.CurrentRow; i++)
{
// calculate a score using the Board's calculate function against the next guessed row
int[] result = TheBoard.CalcScore(GetIntArray(TheArray), i);
// compare the actual peg score of the next guessed row to the peg score of the Genome against that same row
int numCorrectInRow = CompareToScore(i, result);
// Normalize the fitness score a little bit (not really necessary, since the AutoPlayer takes the highest fitness score in
// final generation)
fFitnessScore += ((float)numCorrectInRow)/4.0f;
}
// this function goes through each peg score of the current peg row and compares it to the
// peg score that was calculated against the same row and returns the # of pegs that match against
// it (including blank pegs)
private int CompareToScore(int nCompareRow, int[] testpegs)
{
int nScoreMatch = 0;
for (int i = 0; i < 4; i++)
{
int nPeg = TheScore.GetPeg(i, nCompareRow);
if (testpegs[i] == nPeg)
{
nScoreMatch++;
}
}
return nScoreMatch;
}
fFitnessScore += .02f;
// give it some value greater than 0
return fFitnessScore;
}
public override float CalculateFitness()
{
CurrentFitness = CalculateFromMastermindBoard();
return CurrentFitness;
}
Conclusion
The computer seems to average winning in 5 tries or less at the expert level. The beginner level either loses or takes longer to get the right answer. You can make the computer play a little worse by reducing the population size and population limit in the Population class and by decreasing the # of generations the AutoPlayer goes through in the CalculateGeneration method. The download is initally set at expert level with a population of 1000 Mastermind Genomes and number of generations set to 10. The beginner level is set to a population of 10 Genomes and 25 generations.