The primary goal of this project was to create a good Othello player using genetic programming techniques. Therefore, the temptation to use other game programming tools from aritificial intelligence (such as alpha-beta pruning) was not succumbed to; rather, variations were made in a single-ply board evaluation algorithm.
Two main genetic programming approaches were followed:
The modification of basic terminals involved eliminating most of the terminals available in the original package (such as black_edges, white_near_corners, etc.) because they have been made obsolete by symmetrical evaluation terminals. These provide the genetic tree with access to specific squares on the board, so that the evolution mechanism can determine the original terminals with greater specificity. The most basic terminals were retained to accelerate evolution, such as black and white to maintain the current score.
Mobility of pieces is an important concept in Othello, as it is directly related to a player's control over the opponent by limiting the move availability. This concept of mobility was also added as a terminals (white_mobility and black_mobility to accelerate evolution.
Finally, to add variability to the population's evolution, a random element was added (terminal random) as a means of providing adaptability to new species.
Upon addition of these terminals, Edgar proved to be a very weak player. Other good Othello software, although available, did not at first investigation appear to provide text-based interface capabilities. Because of this, and project time constraints, the approach was to use Edgar as an initial opponent for a new strickly black player (since Edgar only plays white). This black player was then pitted against a new white player, which evolved independently as a new species. Finally, the two species (Edgar's opponent and Edgar's opponent's opponent) were made to evolve against each other and create a third species which has genetic trees capabable of playing either as black or white.
Our results indicate that genetic programming can be successfully applied to the problem of Othello, as the evolved players were able to consistently defeat Edgar. In addition, the genetic players presented a substantial challenge for humans as well.