CEng 713 Evolutionary Computation,
Homework 1
Due: 17^th October 2005

In this homework, you will write a genetic algorithm that plays the game Mastermind and analyse it with some parameters.

There are different versions of mastermind game. Basically, the player A keeps a number and the player B guesses that number. At the end of each guess, player A reports the success of the guess with the number of digits that are guessed with exact position and the number of digits guessed but in a wrong position. The general form can be described as follows:

M, N, M < N	The number of digits in the guessed number and number of digits in the alphabet
L = {0, 1, 2,..., N - 1}	The set of digits, the alphabet.
P $\in$ LM	The number (an M-tuple of digits) kept by player A to be guessed.
Gi $\in$ LM	The guess of player B at move i .
score(Gi, P) = < + c, - d >	The score of the player B for move i.
+ c	Number of digits guessed correctly in exact position. c = #j such that Gi[j] = Pi[j]
- d	Number of digits guessed correctly however in a wrong position. c = #j such that Gi[j] = Pi[k], k $\not=$j
score(Ge, P) = < + M, -0 >	End of game

One constraint parameter about P and G_i can be defined according to if a digit can only be used for once or not (i.e. 123437 is a invalid number since 3 is repeated). Let us called this digits used once constraint.

Following is a sample game with N = 10, M = 6, P = 654321, the numbers at left are the G_i's and their scores are given at right hand side :

654321
045894 --> <+0,-2>
591760 --> <+0,-3>
259108 --> <+1,-2>
950643 --> <+1,-3>
452076 --> <+1,-3>
856427 --> <+2,-2>
809473 --> <+0,-2>
756219 --> <+1,-3>
216047 --> <+0,-4>
658921 --> <+4,-0>
354921 --> <+4,-1>
053921 --> <+3,-1>
654321 --> <+6,-0>

You are asked to write a genetic algorithm for playing this game. Your algorithm will start with an initial guess and execute this loop:

Make a guess G_i
Get your score S_i
if S_i = < + M, 0 > exit
initialise a population of guesses
evaluate each individual I based on S_k and score(G_k, I) for k = 0, 1,.., i
Execute Genetic algorithm for T generations
Define your next guess G_i+1 as the best individual
Go to the beginning

Please choose a hard problem size, i.e. at least M = 8, N = 16. Then make an experiment with different parameters. Here are some parameters for experiment:

• different crossover,mutation probabilities
• different selection mechanisms/pressures/elitism
• digits used once constraint or not
• different order preserving crossovers vs normal crossover for digits used once
• different portions of existing population transferred to next moves population. G_i population to G_i+1 population.
• any other thing you can think of (just ask me before)

Choose at least 3 parameter setups. Repeat each setup for at least 20 times and collect results for best and average fitnesses for each generation and number of moves required to guess the number. Plot average (of 20 experiments) charts for:

• parameter setup versus the number of steps required to guess.
• generation versus best/average fitnesses of setups at a single common guess step (like i = 15).
• guess step versus the normalized fitnesses of setups at a common instance in generations.

You can use GALib (http://lancet.mit.edu/ga/) or any library of your choice. You shall submit your code with an experiment report with the following template:

CEng 713 Homework 1
Experiment Results

Topic: Mastermind game
Name surname: Id:

GA Parameters:

Population size:
Crossover/mutation rates:
Type of crossover/mutation:
Selection mechanism:
% of Elitism:
Digits used once:
Fitness function:
% of Population transfer to next move:
M/N:

Results

..... ..... .......... ......... .......... .......... ........ ..... ..... .......... ......... .......... .......... ........ ..... ..... .......... ......... .......... .......... ........

Figure 1: .... vs .....

Figure 2: .... vs .....

..... ..... .......... ......... .......... .......... ........ ..... ..... .......... ......... .......... .......... ........ ..... ..... .......... ......... .......... .......... ........