Machine Learning CS-W4771

Homework #4 Genetic Programming

Project Othello Student: Manuel Reyes

INTRODUCCION.

In this homework, the student is introduced to the practical issues of a genetic programming implementation such as: the fitness function, percentage of crossover, representation of the genetic program as a tree, etc.

A genetic programming framework is provided in the directory /OthelloProj/GP/gpjpp, this framework defines the classes needed for the correct representation of the genetic program as a tree structure, it also provides the definition of the different genetic operators such as crossover and different kinds of asexual mutation, different selection types for the creation of the next generation are also provided within the framework. However some of the classes are Abstract Classes, which must be overridden by a subclass that contains the information required for the implementation of the framework in a specific application.

All the necessary subclasses for the implementation of a “genetic Othello player” using this framework are also provided in the directory /OthelloProj/othello. In this implementation a target function representation is used as the genetic program, this function express the characteristics and the desirability of a given board configuration in a particular moment, this function is used to decide the next move of the genetic player. This target function uses 13 primitives; 4 basic operators: +, -, * and /; another 8 primitives that state the statistics of the board configuration and finally, a numerical constant primitive “10”. Different kinds of Othello players are also provided, like a random player and an expert: “Edgar”. These players are used to train and test the generated genetic Othello players.

The different goals that could be covered by this homework are: 1.- Compare, contrast and discover methods to approach Othello with GP, 2.- Investigate methods to evaluate resulting Othello players, 3.- Compare results to another learned Othello player, Edgar and 4.- Use another Othello expert, Edgar, during training.

In this homework, I implemented some changes in the subclasses for the Othello application to cover the desired goals; the motivation for the selection of the particular experiments made is following.

MOTIVATION

The first goal could be done varying the GP parameters (population size, crossover probability, selection process, etc) or changing the representation of the target and fitness function. I decided to use the second approach because I think that, it could have more impact in the total performance of the application, regardless of the GP parameters. The other three goals are very important to get an unbiased and objective measure of the performance of the generated genetic players.

MODIFICATIONS AND EXPERIMENTS

I did four different types of modifications and experiments. The modifications tested are:

- Use of normalized primitives in the target function.

- Use of a weighted fitness function.

- Use of two new primitives.

- Use of two new primitives and a weighted fitness function.

In all the tests, the default GP parameters were used: Population size = 200; Crossover probability = 0.90; Mutation Probability = 0.0, etc; and Edgar was used for the training phase. Results using Edgar and a random player in the test phase are presented.

First I will present some of the results obtained in the application without changes and then the results using the modifications would be presented and compared.

Results using the application without any changes.

The program was run several times the results of the best three individual can be seen in the following table:

Individual	Percentage of games won against a random player	Average score against a random player	Percentage of games won against Edgar	Average score against Edgar
(- black_edges 10)	98%	41.8 – 22 .7	0.0%	22 – 42
(- (* black_corners white_near_corners) (/ black_edges black_edges))	98%	44.54 – 3.76	0.0%	16 – 48
(/ black_edges white)	60%	34.78 – 29.74	0.0%	15 – 49
Average	85.33%	40.37 – 18.733	0.0%	17.666 – 46.33

Even thought, these results appear to be very good in terms of the random player, it is important to mention that these are the best individuals found after a lot of runs, but the performance of the average genetic player against a random player using this approach is really low.

First modification: Use of normalized primitives in the target function.

The non-operator primitives used in the application gave information about the statistics of the board in a given moment; these primitives and their maximum values are the following:

Primitive Maximum Value

Number of white/black pieces 64

Number of white/black pieces in a edge 30

Number of white/black pieces in a corner 4

Number of white/black pieces adjacent to a corner 12

As Juno Suk state in his report, the application uses these non-normalized values for the estimation of the target function. I agree with Suk’s comment that the use of the non-normalized value introduces a bias toward the number of pieces of a given color, obviously these values are important to determine the winner of the game, but during the game some positions are more desirable than others e.g. the corners, so it make sense that if the normalized values of these primitives are used then the player could have a better estimation of the desirability of a given board in term of the total number of pieces of a given color, but also in terms of their position.. So the first modification done to the original code was the normalization of the primitive’s values. This normalization was done just dividing the actual value of the primitive by its maximum value. Also a change was made in the numerical constant primitive 10, its value was change to 1.5, because 10 would introduce a huge difference when it used with the “+” and “-“ operators. The changes in the code were introduced in the updateStatisitcs( ) of the OthelloBoard class.

Some runs of these modification were done the results of the best individuals obtained can be observed in the following table:

Individual	Percentage of games won against a random player	Average score against a random player	Percentage of games won against Edgar	Average score against Edgar
(+ black_edges black_edges )	100%	42.54 – 7.8	0.0%	16 – 48
(/ white_near_corners (-black_corners 10))	98%	40.34 – 24.4	0.0%	22 – 42
(- black_edges black_near_corners)	92%	43.26 – 13.92	0.0%	10 – 54
Average	96.6666%	42.04– 15.373	0.0%	16 – 48

As we can observed, the performance of the genetic players against a random player has a slightly improvement, but the performance against Edgar is still very poor.

Second modification: Use of a weighted fitness function.

The application uses as the fitness function the sum of the remaining pieces of the genetic player’s opponent, after five games. So this fitness function gives the same weight to all the pieces independently of their position, but some positions are more desirable than others. For example, boards where the opponent has pieces in the corners are less desirable than the ones where there are not opponent’s pieces in the corners, this is because, if a player gets the corners is more likely that he would win the game. So I followed the idea introduced in the work of Daby Sow, but I changed the value of the weights, as it can be seen in the following picture.

The idea is that when the opponent has pieces in the corners, he has more possibilities to win, so boards with this condition are less desirable and that’s why these positions have high value weights, in other hand, if the opponent has pieces one position away from the corner, these pieces would let the genetic player to put pieces in the corners and then elevate its possibilities to win and that’s why the weight of these positions is zero. I changed the values of weights compare to Sow’s work because I think that there was not enough “relative desirability” for the one-position-away-from-the-corner pieces. Some runs of this modification were done, the results of the best individuals found can be observed in the following table. The changes in the code were introduce mostly in the OthelloBoard Class where the new method, getWeightedFitness( ) was aggregated.

Individual	Percentage of games won against a random player	Average score against a random player	Percentage of games won against Edgar	Average score against Edgar
/ - - - + black_edges white + white_corners white_edges / + white_edges white_edges + white_edges white - + / black_near_corners white * white_edges black_edges + -white_edges black_corners white_corners * white_edges black_corners	96%	43.00 – 21.00	0.0%	22 – 42
/ + + / black black_corners / white_corners white_corners / / white_edges white_corners + black_corners white - * * white_near_corners black_near_corners – white black_near_corners / * white_near_corners black_edges – white white_corners	98%	37.98 – 23.64	0.0%	22 – 42
(* / white_edges black + white black_edges)	92%	39.50 – 7.02	0.0%	16-48
Average	95.3333%	40.16– 17.22	0.0%	20 – 44

The performance of these players against a random player is lower than the ones of the previous players, but their performance against Edgar is slightly better. Another disadvantage is that the complexity of these players is considerably higher. This result was a surprise because a really expected a really improvement in the performance of these players.

Third modification: Use of two new primitives.

A aggregate two new primitives:

- Number of white pieces two positions away from the corners: white_2d_corners.

- Number of black pieces two positions away from the corners: black_2d_corners.

The new primitives were calculated in the updateStatistics( ) method of the OthelloBoard Class, and the definition of the primitives was aggregated to the definition of the OthelloGenes used in this application.

Some runs using these modifications were done, the results of the best individuals found can be observed in the following table:

Individual	Percentage of games won against a random player	Average score against a random player	Percentage of games won against Edgar	Average score against Edgar
( + black_2d_corners black_edges )	92%	40.40 – 8.74	0.0%	22 – 42
( * black_edges black_2d_corners)	98%	48.80 – 10.88	0.0%	16 – 48
( * black_near_corners black_edges )	96%	39.62 – 10.52	0.0%	22-42
Average	95.3333%	42.94– 10.04	0.0%	20 – 44

The performance of these players against random is better than the performance of the other players, but the performance against Edgar doesn’t improve at all.

Fourth modification: Use of two new primitives and weighted fitness function.

This modification is just the use of modifications two and three at the same time. The results in the best players found can be seen in the following table:

Individual	Percentage of games won against a random player	Average score against a random player	Percentage of games won against Edgar	Average score against Edgar
( / * * / / black_edges white * white_edges black + + black black_2d_corners – black_2d_corners black_2d_corners + - + black_corners black_edges + black_corners black_corners - * black_2d_corners black_corners * white_edges black_near_corners + + black_corners black_corners * 10 white_corners)	98%	39.4 – 24.6	0.0%	22 – 42
( / * white white_2d_corners / black black_edges)	96%	39.78 – 8.56	0.0%	22 - 42
Average	97%	49.59– 16.58	0.0%	22 - 42

As we can see, there is not any improvement in the performance of these players.

CONCLUSIONS

Even though the performance of the best individuals found in each case are not quite different, an improvement in the performance against a random player in the average of the individuals was found in general in all the modifications, what is really disappointed is that the performance against Edgar was really poor in all the cases. The modification that in general worked the better was the addition of the new two primitives, which let think that maybe a better representation of the target function is needed; in order to really improve the performance of the genetic players found using the given genetic programming framework.