Improvement of Genetic Algorithms by the Addition of new Primitives

Edgar Dies

Sheanon Chung

Joe Gagliano

Stan John

Motivation:

In this project, we explore the effect on Genentic Algorithms’ performance of a change in the information made available to it.  In this example, for the Genetic Algorithm for playing Othello, we vary the information that is made available to algorithm by adding new primitives which give more information about the status of board during different stages of the game.

We wanted to experiment with the GA package by adding new primitives.  The purpose was to make the tree function representation more robust and hence be able to describe a larger number of functions with increased primitives.  As human beings that were relatively new to the game of othello we were not very good at beating Edgar.  Our goal was to create a player that would evolve to beat Edgar and to be a good player in general.

Procedure:

Added 5 new primitives of 3 different types.

For simplicity sake we have named each primitive after

SHAFT

-        white_one_from_edge

-        black_one_from_edge

o      This calculates the number of white and black pieces that are one space away from the edge respectively.

DOLEMITE

-        white_moves

-        black_moves

o      This calculates the number of possible moves for black or white pieces given a current board position.

FLIP WILSON

-        flips

o      This calculates the number of opponent players pieces fliped given a certain move.

SUPERFLY

-    All of the primitives

Then these primitives were trained against Edgar and tested against Edgar and Random Player.

Results:

Initial Parameters:

The following are the paraemeters we used to train the players.

 Population Size 200 Number of Generations 20 Number of Good Runs 10 Terminiation Fitness 150

Each primitive was added separately to the existing set and trained, but we also added all three primitives to the existing set of primitives, and also trained all  three primitives together without the exisitng set.   The following are the results from the test games against Edgar and the Random Player

NOTE:  In the data below, scores that are underlined are winning scores, and percentages that are underlined are those above 50%.

Primitive:   One From Edge

Player Color

Player Name

White

Edgar

Black

Shaft

 Run Number Resulting Player Score 1 ( * ( - ( - ( - white_edges black_corners ) ( / white_one_from_edge black_one_from_edge )) ( / ( - white_near_corners white_edges ) ( / white black_edges ))) ( / ( * ( - black_corners white_near_corners ) ( + black black )) ( - ( / black black ) ( * white_corners white_corners )))) 40 24 2 ( / ( - white 10 ) ( + 10 black_near_corners )) 34 30 3 ( * ( - ( + white_edges white_corners ) ( * 10 black_edges )) ( / ( + white_one_from_edge black_corners ) ( + white_one_from_edge black_near_corners ))) 11 53 4 ( - ( / white_near_corners white_corners ) ( / black_near_corners white )) 6   58 5 ( * ( + white black_one_from_edge ) ( - white_one_from_edge 10 )) 40 24 6 ( / white_one_from_edge ( * 10 black )) 38 26 7 ( / white  ( + white_near_corners black_one_from_edge )) 42 22 8 ( / ( - ( - ( - white_edges black_one_from_edge ) ( - white_near_corners black_near_corners )) ( / ( * black black_one_from_edge ) ( / white_corners black_one_from_edge ))) white ) 38 26 9 ( + white ( / white_near_corners black_near_corners )) 32 32 10 ( + ( + black_edges white_one_from_edge ) black_one_from_edge ) 45 0

Player Name

White

Random Player

Black

Shaft

Run Number

Resulting Player

Percentage of Wins

1

( * ( - ( - ( - white_edges black_corners ) ( / white_one_from_edge black_one_from_edge )) ( / ( - white_near_corners white_edges ) ( / white black_edges ))) ( / ( * ( - black_corners white_near_corners ) ( + black black )) ( - ( / black black ) ( * white_corners white_corners ))))

90%

2

( / ( - white 10 ) ( + 10 black_near_corners ))

30%

3

( * ( - ( + white_edges white_corners ) ( * 10 black_edges )) ( / ( + white_one_from_edge black_corners ) ( + white_one_from_edge black_near_corners )))

71.4%

4

( - ( / white_near_corners white_corners ) ( / black_near_corners white ))

71.4%

5

( * ( + white black_one_from_edge ) ( - white_one_from_edge 10 ))

48%

6

( / white_one_from_edge ( * 10 black ))

96%

7

( / white  ( + white_near_corners black_one_from_edge ))

4%

8

( / ( - ( - ( - white_edges black_one_from_edge ) ( - white_near_corners black_near_corners )) ( / ( * black black_one_from_edge ) ( / white_corners black_one_from_edge ))) white )

6%

9

( + white ( / white_near_corners black_near_corners ))

56%

10

( + ( + black_edges white_one_from_edge ) black_one_from_edge )

96%

Player Color

Player Name

White

Edgar

Black

Dolemite

 Run Number Resulting Player Score W-B 1 ( +  ( -   black_near_corners  ( *   black   white_near_corners ))  black_corners ) 27 37 2 ( *  ( /   num_white_moves   white_edges ) ( /  ( +   num_black_moves   black )  black_near_corners )) 42 22 3 ( /  ( /  ( +   black   white_edges )  num_black_moves )  white_edges ) 37 27 4 ( *  ( -   black_near_corners   black_edges ) ( -   white_edges   white_corners )) 42 22 5 ( /  ( -   black_edges   black )  white_edges ) 30 0 6 ( /   black   white_edges ) 61 3 7 ( *  ( +  ( +  ( *   black_corners   black_edges ) ( /   num_black_moves   white )) ( /  ( -   num_white_moves   num_black_moves ) ( /   num_white_moves   num_white_moves ))) ( *  ( *  ( *   white_corners   white_edges ) ( -   black   num_black_moves )) ( -  ( +   white   white_edges ) ( /   num_black_moves   black_edges )))) 42 22 8 ( +   white   black_edges ) 56 8 9 ( /  ( /  ( -   black   white_edges ) ( *   num_white_moves   black_corners )) ( +  ( *   white_edges   num_white_moves ) ( /   num_white_moves   num_black_moves ))) 45 19 10 ( *  ( *   num_black_moves  ( -  ( -  ( /   white_corners   white_edges ) ( /   num_black_moves   black )) ( /   black_corners   num_black_moves )))  num_white_moves ) 42 22

Player Color

Player Name

White

RandomPlayer

Black

Dolemite

 Run Number Resulting Player Percentage of Wins 1 ( +  ( -   black_near_corners  ( *   black   white_near_corners ))  black_corners ) 90% 2 ( *  ( /   num_white_moves   white_edges ) ( /  ( +   num_black_moves   black )  black_near_corners )) 96% 3 ( /  ( /  ( +   black   white_edges )  num_black_moves )  white_edges ) 96% 4 ( *  ( -   black_near_corners   black_edges ) ( -   white_edges   white_corners )) 94% 5 ( /  ( -   black_edges   black )  white_edges ) 96% 6 ( /   black   white_edges ) 96% 7 ( *  ( +  ( +  ( *   black_corners   black_edges ) ( /   num_black_moves   white )) ( /  ( -   num_white_moves   num_black_moves ) ( /   num_white_moves   num_white_moves ))) ( *  ( *  ( *   white_corners   white_edges ) ( -   black   num_black_moves )) ( -  ( +   white   white_edges ) ( /   num_black_moves   black_edges )))) 98% 8 ( +   white   black_edges ) 88% 9 ( /  ( /  ( -   black   white_edges ) ( *   num_white_moves   black_corners )) ( +  ( *   white_edges   num_white_moves ) ( /   num_white_moves   num_black_moves ))) 96% 10 ( *  ( *   num_black_moves  ( -  ( -  ( /   white_corners   white_edges ) ( /   num_black_moves   black )) ( /   black_corners   num_black_moves )))  num_white_moves ) 88%

Primitive:   Number of Flips

Player Color

Player Name

White

Edgar

Black

Flip Wilson

 Run Number Resulting Player Score 1 ( *  flips  white_corners ) 16 48 2 ( *  ( +  ( -   black_edges  flips)  white_near_corners ) ( -   white   white_near_corners )) 42 22 3 ( *  flips  white_corners ) Repeat Tree 4 ( *   white_corners  flips) Repeat Tree 5 ( *   black  ( *   white_corners  ( *  flips  white ))) 16 48 6 (+  ( *   white_corners  flips) ( -   black_near_corners   white_corners )) 54 10 7 ( *   white_corners  flips) Repeat Tree 8 ( -  ( +   10   black_edges ) flips) 48 16 9 ( *  flips  white_corners ) Repeat Tree 10 ( /  ( +  ( +   white_near_corners   white ) ( +   white_edges   black_corners )) ( +   white_near_ corners  ( *   black_edges   black ))) 38 26

Player Color

Player Name

White

Random Player

Black

Flip Wilson

 Run Number Resulting Player Win Percentage 1 ( *  flips  white_corners ) 92% 2 ( *  ( +  ( -   black_edges  flips)  white_near_corners ) ( -   white   white_near_corners )) 94% 3 ( *  flips  white_corners ) Repeat Tree 4 ( *   white_corners  flips) Repeat Tree 5 ( *   black  ( *   white_corners  ( *  flips  white ))) 90% 6 (+  ( *   white_corners  flips) ( -   black_near_corners   white_corners )) 96% 7 ( *   white_corners  flips) Repeat Tree 8 ( -  ( +   10   black_edges ) flips) 98% 9 ( *  flips  white_corners ) Repeat Tree 10 ( /  ( +  ( +   white_near_corners   white ) ( +   white_edges   black_corners )) ( +   white_near_ corners  ( *   black_edges   black ))) 80%

Primitive:   All Primitives Combined

Player Color

Player Name

White

Edgar

Black

Superfly

Run Number

Resulting Player

Score

W – B

1

"( /  ( /   white   num_white_moves ) ( +   white   white_corners ))"

40 24

2

"( /   white   num_black_moves )"

50 8

3

"( /   white_one_from_edge   black )"

22 42

4

"( *   white  ( +   black_one_from_edge  ( *   num_flips   num_flips )))"

28 36

5

"( /   white   num_black_moves )"

50 8

6

"( /   white_one_from_edge   black )"

22 42

7

"( -   10  ( /   white_near_corners num_flips ))"

19 45

8

"( /   white_one_from_edge   black )"

22 42

9

"( /  ( +  ( -  ( *   white_one_from_edge   10 )  black )  num_white_moves )

28 36

10

"( /  ( +   black   num_flips )  black_one_from_edge )"

16 48

Player Color

Player Name

White

Random Player

Black

Superfly

 Run Number Resulting Player Win Percentage 1 "( / ( /   white   num_white_moves ) ( +   white   white_corners ))" 86% 2 "( /   white   num_black_moves )" 60% 3 "( / white_one_from_edge   black ) 54% 4 "( *   white  ( +   black_one_from_edge  ( *   num_flips   num_flips )))" 12% 5 "( / white   num_black_moves )" 56% 6 "( / white_one_from_edge   black )" 70% 7 "( - 10  ( /   white_near_corners   num_flips ))" 94% 8 "( / white_one_from_edge   black )" 50% 9 "( / ( +  ( -  ( *   white_one_from_edge   10 )  black )  num_white_moves ) white_edges )" 90% 10 "( / ( +   black   num_flips )  black_one_from_edge )" 88%

Shaft Results:

In looking at the results, several patterns were evident.  In general, the trees that did well against the Random Player, i.e. over 90%, beat Edgar.  This points to significant learning in the functions in runs 1, 6, 10.  In these runs, the primitives white_one_from_edge and/or black_one_from_edge were included.  Similarly runs 2, 4, and 9, that did not contain the one_from_edge primitives did not perform well against Edgar or RandomPlayer.  Overall there was not strong evidence of evolution over runs.  However, the final run beat Edgar 45-0.

Dolemite Results:

Dolemites main added feature was the ability to calculate the number of moves the opponent had available once a specific move was performed on his part.  From the above results for Dolemite’s games against Edgar, we immediately see one obvious result.  That is that the one function tree that did beat Edgar was very short comapared to the other longer ones that lost, some of which lost very badly.  However, there is a bit of a contradiction in that the two shortest did lose the worst.  This shows that though we want concise trees, overly concise trees will cause us to lose out on valuable information.

In addition, the main primitives that were added for this player are those describing number of moves.  These primitives were not present in the winning function, and only appear in numbers 2,3,7,9,10.  This is only half of the functions we got back, meaning that it did not give a great deal of useful information for playing Othello, as this trait did not last through the evolution of the function trees, especially the more desired shorter trees.  Since Edgar was very good to start with, we do not expect to gain much from one primitive, but this one primitive is obviously less advantageous than the others we decided to add.

Now looking at the results of the functions produced with these primitives playing against the Random Player, we see quite different results, as this player performed extremely well against the Random player, winning over 90% of the games in most of the  runs of 50 games.  We see that though this primitive may not have added a great deal of useful information for beating Edgar, an extremely strong player, it was not completely useless as it was able to follow some logic and beat the Random Player most of the time.  In fact, in this case, unlike what we saw with Edgar, all functions that did include the new primitive with the exception of one were able to beat the random player at least 96% of the time.

Flips Results:

The flips primitive calculated the number of flips our player could make per move.   Out of all the trees that were constructed only one did not include “flips” and also, the tree “( * white_corners flips)” came up 5 times.   The tree that did not include “flips” had the lowest percentage against the Random Player and lost to Edgar.   This shows that the flips primitive became very important in the training process.   The  “( * white_corners flips)” tree was able to beat Edgar and also had a percentage of 92% wins against the Random Player.  The trees that were constructed using the flips primitives did better against the Random Player than the other trees with the other new primitives.  However, they were equally as successful against Edgar.   “White_corners” came up several times because our player was trained to be black, and one strategy in Othello is to try to obtain the corners, and so our player was keeping track of how many corners its opponent had.  Primitives involving flips or the corners dominated almost all of the trees that were created.

Superfly’s Results:

Finally, we look at Superfly, who combined all of the above stated primitives into one very good player.  We were able to beat Edgar most of the time with the functions produced by this plaer.  One main thing to note is the contrast in size of these trees compaged to many of the other trees we have above.  These are extremely small trees, and all peformed very well against Edgar.  This supports the concept of Occam’s razor that the shorter, more concise trees are usually provide a better evaluation of the matter at hand.

In addition, we see that most of the winning trees contained two of our new primitives:  num_flips and num_black/white_one_from_edge.  For the latter, we mostely see white_one_from_edge in our trees, showing that it gave higher ranking to putting a black piece one away from the edge, which is contradictory to what we expected the turnout to be.  However, we were obviously wrong, as this primitive tends to shut down Edgar very often.   Numflips is a primitive that would be used by many human players, which would naturally favor flipping as many pieces as possible without using the strategy of waiting  as Edgar seems to do.  However, this did also help in achieving a great number of very good scores against Edgar.

Again, we see that the num_black/white_moves does not exist in many of our trees at it was probably filtered out through evolution, and did not give a great deal of useful information to us.

In looking at the scores against the Random Player, we do see some surprising results.  In particular, number 4, which beat Edgar, was only able to beat the RandomPlayer 12% of the time.  This seems to make very little sense, as it should be much harder to beat Edgar than RandomPlayer.  This brings up the issue of specialized learning.  It may be possible that this function, since it was trained against Edgar, was taught to play so well against Edgar specificially, that it fails miserably against any other player, even if that player has a very weak strategy.

However, in the overall picture, there is consistency between the higher percentages with those that beat Edgar, showing that adding the information that we did to the player was extremely beneficial, and very often filtered out the other existing primitives that were originally given to us, which we did leave in the code.

Conclusions:

From the above analysis we found that adding certain primitives to the Genetic Learning process added a great deal to our ranking function as with num_one_from_edge, while others added very little or may have even hurt the learning process.  The prior changed the original learning process to an incredibly strong one that allowed us to shut out Edgar 45-0 in a function that used both the num_black and white_one_from_edge in it.  In addition, we found that this one primitive was very strong as it lasted quite often through the evolution of functions, which also contained the other primitives we incorporated.  We also saw a stronger performance from shorter function trees, as we would expect according to theory of Occams Razor.  Finally, we also observed the possibility of a presence of over-learning in our results as those functions that performed extremely well against Edgar did not do as well against the Random Player, which should be very easy to beat.  Since all of our functions were trained using Edgar, it is possible that for a general purpose player, some of our functions that did well against Edgar may be beat by other functions that did better against the Random Player.  This may possibly be discussed further in a more extensive research project.

Click on the Board to watch evolved Shaft versus Edgar!