Mastermind: An Evolutionary Computing Framework Demo

• Download source files - 24.1 KB

Introduction

The mastermind application is a demonstration project to illustrate how you can use the Evolutionary Computing Framework to build a real program and to test how changing the different parameters of the evolutionary setup can affect its problem solving ability. Essentially, the application attempts to solve the standard "Mastermind" problem which is to discover the colour and position of a number of hidden pegs by guessing based on the feedback of the correctness of the guesses that precede it.

MastermindEnvironment: IEnvironment

The MasterMind environment class is an implementation of the IEnvironment that defines the correctness of each of the population of current guesses. To do this, it has a copy of the correct peg layout and it compares each guess in the guess population against this assigning 5 points if the guess has the right colour peg in the wrong position and 50 points if the guess has the right colour peg in the right position. It then culls those that have less than the average number of points and breeds the new guess population from the remainder. Thus the population gets healthier each turn and nearer to the correct guess.

'\\ --[NextGeneration]-------------------------------------------------
'\\ Evaluates the health of each individual in the current population, 
'\\ killing off the least healthy and breeding from the rest
'\\ -------------------------------------------------------------------
Public Sub NextGeneration()
 
    If _Population.PopulationSize = 0 Then
        Throw New Exception("The population is extinct")
    Else
        Dim GenomeHealth As Integer
        Dim TotalHealth As Integer
        _HealthiestIndividual = Nothing
        Dim TestGenome As Integer
        For TestGenome = 0 To _Population.PopulationSize - 1
            If _HealthiestIndividual Is Nothing Then
                _HealthiestIndividual = _Population.Item(TestGenome)
                TotalHealth = GetHealth(_Population.Item(TestGenome))
            Else
                GenomeHealth = GetHealth(_Population.Item(TestGenome))
                If GenomeHealth > GetHealth(_HealthiestIndividual) Then
                    _HealthiestIndividual = _Population.Item(TestGenome)
                End If
                TotalHealth = TotalHealth + GenomeHealth
            End If
        Next
        Dim Averagehealth As Integer = TotalHealth/_Population.PopulationSize
        Dim MaxIndex As Integer = _Population.PopulationSize - 1
        For TestGenome = 0 To MaxIndex
            If TestGenome > MaxIndex Then
                Exit For
            End If
            GenomeHealth = GetHealth(_Population.Item(TestGenome))
            If GenomeHealth < Averagehealth OrElse GenomeHealth = 0 Then
                _Population.Kill(TestGenome)
                MaxIndex = MaxIndex - 1
            End If
        Next
        For TestGenome = 0 To _Population.PopulationSize - 2 Step 2
            Dim Parents As New MastermindGuessPopulation()
            Parents.AddGenome(_Population.Item(TestGenome))
            Parents.AddGenome(_Population.Item(TestGenome + 1))
            _Population.AddGenome(Breed(Parents))
        Next
    End If

End Sub

MastermindGuessPopulation : IPopulation

The mastermind guess population is all the current guesses at the peg layout. It is not much more than a type safe collection of MastermindGuessGenomes.

MastermindGuessGenome : IGenome

The MastermindGuessGenome represents a single guess at the hidden peg set. It has one MastermindGuessGene for each of the available peg holes.

MastermindGuessGene : IGene

The mastermind guess gene is a single peg colour. The gene holds one of 8 possible colour values according to the enumerated type Peg_Colours:

Public Enum Peg_Colours
    White_Peg
    Black_Peg
    Green_Peg
    Blue_Peg
    Yellow_Peg
    Red_Peg
    Orange_Peg
    Brown_Peg
End Enum

Other Stuff

There is also a form that shows the current state of the game and another to allow you to alter the environment settings for each game. This allows you to investigate the effect of changing the population size or the number of peg holes on the number of generations needed to solve the problem

Comparison to an Intelligent Player

There are a couple of things that an intelligent player would do that this demonstration doesn't do. Firstly, the intelligent player would never submit the same guess twice because this is obviously wrong. Also, the intelligent player would swap the positions of the pegs if they were getting a number of "right colour in the wrong hole" feedback. In this implementation, each peg has to evolve towards the right colour in situ. I will address this in a later version.

History

• 16^th September, 2004: Initial version