Project Othello

CS4770 Homework 4, Spring 2000

By Thomas Keerikattu


The goal of this project is to research different methods of applying genetic programming to evolve a program that can play Othello. For the assignment, we were provided with a Java implementation of genetic programming, Edgar (a program that was trained to play Othello using another learning mechanism), and a few other tools to evaluate the fitness of evolved hypothesis and to evaluate the results.

After reviewing the problem and the write-ups of previous results I decided to try the following:

1. Modify the mechanism that evaluates fitness so that it is, in my opinion, more direct, accurate and ‘goal oriented’.

2. Use a reduced and slightly modified set of primitives.


The Approach

The following is a description of the tests conducted and the motivation:

  1. As a first step, to baseline the system, I ran the Othello training program as provided. In this case each hypothesis plays five games against a player that makes random moves. Note that the mechanism to evaluate the fitness of the player is to sum the number of pieces of the opponent remaining on the board after the game. The player that left the least number of the opponent’s pieces on the board was selected as the best hypothesis. (Complexity affects fitness was switched off in all the tests). The ‘best’ resulting hypotheses were tested against Edgar.
  2. As a second baseline test, the program was modified so that the hypotheses were tested against Edgar. In this case, just one game was required against Edgar for each hypothesis because Edgar is deterministic. The resulting ‘best’ hypotheses were tested against Edgar.
  1. The problem with the first approach was that ‘random’ players were, well, random and most were not too difficult to defeat. The second method involved playing against a deterministic Edgar and so the resulting hypothesis though able to defeat Edgar, did not do well when tested against random players. I therefore used a combination of the two in the fitness measure for this test.

Also, the mechanism for evaluating fitness as provided is based on the number of pieces of the opponent left on the board. There could, possibly, be perfectly good strategies for playing the game that left a large number of pieces of the opponent on the board but nevertheless were good for winning games against a large variety of opponents. The fitness evaluation algorithm was therefore modified so that it was based on the number of victories against various opponents and not on the number the number of pieces of the opponent left on the board.

The modified the mechanism for evaluating the fitness of a hypothesis as follows:

Although it appears that the algorithm above requires a large number of games for the evaluation process, during the test most of the ‘bad’ hypotheses were immediately defeated by Edgar which acts as a ‘gatekeeper’ so that only the good ones made it all the way through 60 games with the random player. (The terminating fitness in the .ini file was set to 1.)The resulting ‘good’ hypotheses should, by definition, be able to defeat both Othello and a large number of random players.

  1. Conducted the test described in 3 above using a different set of primitives. Because the number of pieces on the board belonging to the opponent is not directly controlled by the player, all primitives related to the number of pieces of the opponent (in this case the white player) were removed. I also added a few numerical primitives to see if they would contribute to a successful hypothesis. The test was conducted with detailed print turned on. The following is a list of primitives used in this test and their descriptions:




The Addition Operator which takes two parameters


The Subtraction Operator which takes two parameters


The multiplication Operator which takes two parameters


The Division Operator which takes two parameters


Number of black pieces on the board


Number of black pieces on the edges of the board (rows 1 or 8 or columns 1 or 8)


Number of black pieces occupying a corner on the Othello Board


Number of white pieces near corners (the three squares surrounding any corners -- a total of 9 locations)


The constant 3


The constant 10


The constant 50


The constant 100



The Results

For tests 1 and 2, results were similar to those obtained by similar experiments in previous projects. Players that evolved to defeat Edgar lost a few games against ‘random’ players probably because of the deterministic nature of Edgar. Some players that were successful against ’random’ players could not defeat Edgar.

For test 3, while the system was able to come up with a hypothesis that beat Edgar and a large number (60) of random players, the resulting hypotheses appeared to be a bit too simplistic to be a complete solution to the problem. Primitives that should, intuitively, play a role in the hypothesis such as black_near_corner were completely ignored

Test 4 generated similar results. In this test only ‘black’ primitives were used and a number of ‘constant’ primitives were added. In the ini file, PrintPopulation was turned on for this test allowing me to see a number of successful hypotheses and not only the best one. The following is a sampling of the hypotheses that were able to defeat Edgar and sixty ‘random’ players.


The terminals used:

100, 50, 10, 3, black_near_corners, black_corners, black_edges, black


A sampling of successful hypotheses: (Fitness = 0.0)

1. ( - 100 black_corners )


2. ( - 50 black_corners )


3. ( - 50 ( * black_corners ( / ( / ( - black_near_corners black_corners ) ( / black_near_corners 3 )) black_corners )))


4. ( / ( + 10 ( - 10 black_corners )) 50 )


5. ( - ( * ( - 3 black_near_corners ) black_near_corners ) black_corners )




Primarily, two tests were conducted in this project:

1. Change the fitness evaluation mechanism.

Although the mechanism used here was successful in producing a player that was able to defeat Edgar and a large number of ‘random’ players, most the resulting hypothesis appeared to be too simplistic to be good enough to win against a strong opponent because they appeared to not factor in the fact that the near-corner areas are to be avoided.

This probably happens because Edgar is weak due to its deterministic nature and the ‘random’ players are not much stronger although they provide some variety. To remedy this, the algorithm described above can be expanded to include a few games with tougher players at the beginning. For example, a ‘randomized’ Edgar (an Edgar where the first few moves are random) may be a worthy contender.

The program could also be modified so that it plays a few games against the best players of the previous generation and in this way train itself. Note that this fitness evaluation method also acts as an automatic evaluator of the result.

  1. Change the primitives to ignore the opponent's counts.

The program was able to generate good hypotheses with this limited set of primitives. The hypotheses did use the new constants (50, 100,3) successfully although it is not clear how much more useful these were in generating good results than the primitive 10 that was used earlier.