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
-
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.
-
white_moves
-
black_moves
o
This
calculates the number of possible moves for black or white pieces given a
current board position.
-
flips
o
This
calculates the number of opponent players pieces fliped given a certain move.
- 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 Color |
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!