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 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.

3. 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.

• Initialize the fitness of the hypothesis to 60.
• Allow the hypothesis to play against Edgar. If the player loses, return current fitness value.
• Play against a random player 60 times, reducing the fitness by one after each victory.
• If the player loses at any point, return immediately, the fitness value at that point.

3. 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:

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.

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.

2. 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.