Spring 2000 Machine Learning Homework 4: Genetic Programming

Project: Othello
By Brian Whitman and Grace Junxin Zhang

• Motivation
• Overview of Solution
• Approach
• Code Modified
• Results
• Conclusions

During testing and example play, we found that the provided Othello project GP packet using the default settings (GPOthello.ini) to train GP Player is not very effective to generate good Othello GP Players: it will give a best individual such as (- white black) and then stop. After some experiment and analysis of the result, we found there are several things could be improved besides changing the settings to increase the standard for a good Player:

• Fitness measurement during the learning process
• hypothesis space / new terminals

1. Fitness measurement during the learning process

Let scoreEdgar be the score that Edgar get for a game against the GP player
Let scoreRandom_N be the sum of the scores that the Random Player get for N games against the GP player
Let scoreLength be the complexity of the hypothesis measured in terms of length

The original Fitness of a GP player is measured this way:

• The GP player will play 5 games against the random player.
  
• The fitness score = scoreRandom_5 + scoreLength
  
• The lower the score the better, so scoreLength serves as a penalty for the fitness.
  

Playing five games against the random player is not enough to train a good GP player because most of the time, the random player plays poorly. But if we play more than 5 games we will increase the training time significantly.

Therefore we change our fitness measurement:

• GP player will play one game against Edgar and 4 games against random player
  
• The fitness score of GP player = scoreEdgar + 15 * scoreRandom_4 + 0.2 * scoreLength (this is known as formula 1 below)
  

Our heuristic to use this formula is as following:
If we assume Edgar is a "good" Othello player, we can use it to distinguish between a good and poor GP player. Since both Edgar and the GP player play Othello deterministically, they can only play one game (all others would return the same result). But playing only one game against Edgar will result a player whose performance is rather unstable (a hypothesis that is not general enough, shaped only by one game). So, we let the GP player play four more games against the random player. According to the experiment, the score that a random player gets against a good GP player can be as low as 1, while Edgar usually gets at least 20.

So we should increase the weight of scoreRandom_N to make it more effective. In the original measurement, it favors too much of a shorter hypothesis. Intuitively, since Othello is a complex game, a good hypothesis for evaluating a board shouldn't be too simple. So we decrease the weight of the complexity penalty which is expressed in scoreLength.

2. Variations on the Hypothesis

We add following primitives to the GP tree:

• number of choices this move gives apponent: num_op_pos_moves
  

  Reasons for adding this primitive:
  

  1. num_of_pos_moves of a board is a potential effective measurement of the board.
     
  2. Currently, the primitives are '+', '-', '%', white, black, white_edges, black_edges, white_corners, black_corners, white_near_corners, black_near_corners, 10 (we are not using ADF). Since num_op_pos_moves should not be a linear conbination of these primitives, adding it should not be redundant. Even if it is redundant, it may somehow shorten the length of a hypothesis, which is our goal.
     
     
• white clusterness / black clusterness: white_clusters, black_clusters:
  
  Here white_clusters is 6, black_clusters is 22
  

  Reasons for adding this primitive:
  

  1. Cluster size can show control of the game through the particular strategy of collecting 'islands' of your color.
  2. Allows the GP player to choose a strategy-based metric besides the corner estimations

Since Edgar is fixed to play WHITE, we modified the program so that the GP player plays BLACK and the random player plays WHITE. This way the GP player can play against both Edgar and the Random Player with a minimum of future modifications.

We conduct the following experiments to verify our solutions. To save time, we modified goodRuns to 2 in the default setting.

For detail of the variables please refer to the Results section

1. use original packet and default setting as the baseline
   
   Train the GP player
   java GPOthello exp1
   Test the GP player
   java OthelloCache scoreonly "<function>"
   GP player played BLACK, Edgar played WHITE, they played 1 game
   GP player played BLACK, Random player played WHITE, they played 49 games against each other
   
   
2. Modify the fitness measurement and settings
   Train the GP player
   java GPOthello exp2
   Test the GP player
   java OthelloCache scoreonly "<function>"
   GP player played BLACK, Edgar played WHITE, they played 1 game
   GP player played BLACK, Random player played WHITE, they played 49 games against each other
   
   
3. Add num_op_pos_moves to original primitives, use the same fitness measurement and settings as in experiment 2.
   Train the GP player
   java GPOthello exp3
   Test the GP player
   java OthelloCache scoreonly "<function>"
   GP player played BLACK, Edgar played WHITE, they played 1 game
   GP player played BLACK, Random player played WHITE, they played 49 games against each other
   
   
4. Add white_clusters and black_clusters to original primitives (do NOT include num_op_pos_moves), use the same fitness measurement and settings as in experiment 2.
   Train the GP player
   java GPOthello exp4
   Test the GP player
   java OthelloCache scoreonly "<function>"
   GP player played BLACK, Edgar played WHITE, they played 1 game
   GP player played BLACK, Random player played WHITE, they played 49 games against each other
   

Code modified:

For fitness measurement:
GPOthello.java GPOthelloGP.evaluate()
scoreEdgar+10*scoreRandom+0.2*scoreLength

For testing against both Edgar and Random player:
OthelloCache.java OthelloCache()
play 1 game against Edgar, 49 games against random

For adding num_op_pos_moves
* OthelloBoard.java
Add two Statistics data member:
OthelloBoard.num_white_clusters and OthelloBoard.num_black_clusters
OthelloBoard.updateBoardStatistics()

* GPOthello.java
GPOthello.createNodeSet()
GPOthelloGene.evaluate()
places that call OthelloGPTester

* OthelloGPPlayer.java
OthelloGPPlayer.evalFunction()
OthelloGPPlayer.evalSubFunction()
OthelloGPPlayer.evalMove()

* OthelloGPTester.java (similar to OthelloGPPlayer.java)
OthelloGPTester.evalFunction()
OthelloGPTester.evalMove()

*OthelloCache places that call OthelloGPPlayer

For adding white_clusters, black_clusters,
* GPOthello.java
GPOthello.createNodeSet()
GPOthelloGene.evaluate()

* OthelloGPPlayer.java
OthelloGPPlayer.evalFunction()
OthelloGPPlayer.evalSubFunction()
OthelloGPPlayer.evalMove()

* OthelloGPTester.java (similar to OthelloGPPlayer.java)
OthelloGPTester.evalFunction()
OthelloGPTester.evalMove()

Results

RPB_1: ( * ( - ( - ( * black_corners black_corners ) white_near_corners ) white_near_corners ) ( * ( * ( - ( * black_corners black_edges ) white_near_corners ) black_edges ) black_edges ))

RPB_2: ( + ( * ( * white_near_corners ( / black_edges white_near_corners )) white_corners ) black_edges )

RPB_3: ( * black ( / ( * black ( - black num_op_pos_moves )) white_edges ))

PRP_4: ( / ( + ( + ( + black_corners 10 ) ( - black white )) ( - ( - ( - black white ) ( + num_op_pos_moves white_near_corners )) ( - white white_corners ))) ( - white white_corners ))

RPB_5: ( + ( - ( / ( + ( + ( - white black_edges ) ( * black_edges black_clusters )) ( + ( - white_clusters 10 ) ( - white black_edges ))) ( * ( + ( - ( + ( / ( + black black_near_corners ) ( * ( / black black ) ( * 10 white_near_corners ))) ( * black_edges black_clusters )) ( / ( * ( * white_corners white_edges ) ( / white_edges white )) ( + ( / white_edges white ) ( * black_edges black_clusters )))) ( / black_clusters black_corners )) ( * 10 white_near_corners ))) ( / ( - white_clusters 10 ) ( - white_clusters 10 ))) ( + black_corners ( * ( * ( * 10 white_near_corners ) ( / ( + black black_near_corners ) ( + black black_near_corners ))) ( / ( / ( - white_clusters 10 ) ( - white_clusters 10 )) ( + ( / white_edges white ) ( * black_edges black_clusters ))))))

RPB_6: ( + ( - ( / ( + ( - white black_edges ) ( * black_edges black_clusters )) ( * ( + black black_near_corners ) ( * 10 white_near_corners ))) ( / ( - white_clusters 10 ) ( - white_clusters 10 ))) ( + black_corners ( * ( * 10 white_near_corners ) ( / ( * white_corners white_edges ) ( + black_corners white_clusters )))))

Footnotes

(**)
after 26 runs it still can not get a good run. We choose 2 individuals with the top fitness out of all the generations of all the runs.

(***)
At run 16, the program was killed unexpectedly, so we only got one good run before that.

Conclusions

Using the original fitness measurement can't generate a good GP player most of the time. We show this in experiment 1.

A modified fitness measurement can result in a GP player that is capable of defeating Edgar. We show this in experiments 2 and 3.

By adding the two new primitives num_op_pos_moves and white_clusters, black_clusters: (contrast experiments 3 and 4 with experiment 2)

• the overall fitness of best GP player of each generation is improved (reflected in the .stc files, not shown in Result section)
• possibility of achieving higher fitness (lower score) compared to without the primitive given the same training time with num_op_pos_moves.