James Lott

jrl28@columbia.edu

The purpose of this project is to investigate ways of improving a GP othello player to defeat more types of opponents, more often, than the original implementation. We were given an implementation of othello using genetic programming. The genetic programming package is written in Java and includes all of the usual GP features such as crossover, mutation, and ADFs. The othello implementation runs on top of this GP package and consists of 13 different primitives. Four of the primitives are arithmetic operators (+, -, *, /) to be used at non-terminal nodes in a GP tree. The remaining 9 primitives are terminals (black, black_corners, black_near_corners, black_edges, white, white_corners, white_near_corners, white_edges, 10). '10' represents a constant which can be used to weight the other terminals, which are numerical values representing the state of the board (number of black pieces, number of black pieces in the corner, etc.).

We were given 2 players with this implementation: a random player that always chooses a random move, and EDGAR, a smart player that can defeat many opponents. These players can be used to test and train our GP-based players.

To create a baseline, I trained GP players using the original implementation, playing against both a random player and EDGAR. Population sizes of 100 and 200 were used, based on the fact that they require less running time (a major factor in this project) than large populations, and that larger populations did not seem to improve results significantly in the previous years' projects.

I decided to add two new terminals to the othello primitives, based on the concept of surroundedness. Surroundedness measures the number of pieces immediately surrounding (in the 8 spaces adjacent to) a possible move. See the figure below for an example.

Key: {B = BLACK, W = WHITE, x = potential move, E = EMPTY}

white_surr = 2

black_surr = 3

total_surr = 5

The motivation behind adding a surroundedness primitive is two-fold. On one hand, a more surrounded piece is less likely to be flipped by your opponent, because there are fewer possible moves around a more-surrounded space than a less-surrounded space. The other (and perhaps contrasting) effect is that a more-surrounded space is less likely to be beneficial in the future, since there are likewise fewer empty squares around the surrounded space to make future plays in.

Initially I added the two primitives white_surr and black_surr, which respectively correspond to the number of white and black pieces surrounding a move. It was unclear as to how I should count the surroundedness of moves along the border of the othello board. For example, a move in the top left corner can only be surrounded by 3 pieces maximum, but the remaining 5 adjacent spaces lie outside of the game board, which in a sense contributes to the surroundedness of the move. It is also unclear whether these outside spaces should contribute to white_surr or black_surr, since they are not actual pieces and thus belong to neither player.

In the first implementation I ignored adjacent spaces that were outside of the game board (in other words, a corner move has a maximum surroundedness of 3). My rationale was that the other primitives (white_corners, black_corners, white_edges, black_edges) would be able to cover for the special-case of moves along the border. The GP player was again trained against a random player and against EDGAR, in population sizes of 100 and 200.

In the second implementation I combined the two primitives (white_surr and black_surr) into one primitive (surrounded), which represents the number of pieces surrounding the possible move regardless of color. Now the ambiguity as to which color the spaces lying outside the border should contribute to is resolved. A move along the border now counts adjacent spaces that lie outside the border as part of its surroundedness. For example, a corner move how has a minimum surroundedness of 5, and a maximum of 8. The GP player was again trained against a random player and against EDGAR, in population sizes of 100 and 200.

After training the original implementation against a random player, and then testing it against both random players and EDGAR, it became clear that there is little purpose in training against a random player. Within 2 generations, a GP player was always produced that could completely shut-out a particular random player (allowing him 0 moves), and also perform very well (with an 80 - 90% success rate) against any other random players. However, these players faired miserably against EDGAR (with an 80 - 90% failure rate!). Thus I concluded that training against a random player was not very meaningful unless you only wanted to play against random players. My goal was to create a GP player that could defeat EDGAR and perform well against random players as well. This was best accomplished by training the GP players against EDGAR, and then testing them against random players to evaluate their success.

All of the below implementations were trained against EDGAR. Population size varied between 100 and 200. Number of generations was limited to 15 after experimentation revealed little improvement between generations 15 and 31. GoodRuns was set to 5, which is somewhat noisy, but time constraints again would not allow for a higher number of good runs. After reviewing the results of the previous years' writeups, and doing a little of my own experimentation, ComplexityAffectsFitness was turned off as it contributed very little to the GP players' success.

All of the GP players below defeat EDGAR. Avg. fitness against EDGAR is the average number of pieces that EDGAR had after the game was over.

It appears that the addition of the surroundedness primitive did indeed help the GPOthello player defeat EDGAR while playing more successfully against random players that the original implementation. Success rate against random players rose from around 60% in the original implementation, to around 70% in the first modification, and then up to around 85% in the second modification.

It is also interesting to note that the modifications helped the GPOthello players beat EDGAR more strongly than the original implementation. After the 1^st and 2^nd modifications, EDGAR capture less than 10 pieces on average, as opposed to around 22 pieces using the original implementation!

Although the results are somewhat noisy because of the huge amount of time required to produce a GPOthello player (and the limited amount of time we had to do this project), it is still quite clear that adding the surroundedness primitive did improve the GPOthello players' performance. The first modification (adding white_surr and black_surr) resulted in some improvement in both performance against random players and in defeating EDGAR "more badly." The second modification (adding color-blind surroundedness and taking corners and edges into account) resulted in further improvement to the success rate of the player at defeating random players and EDGAR. Therefore, I conclude that surroundedness is a worthy primitive to be added to the GPOthello implementation. It would be interesting to combine this primitive with other successful primitives from earlier years, in an attempt to create a superior GPOthello player.