Othello Project

Introduction

The java implementation of the game was given. The player was able to play against Edgar (best player), a random player as well as a human being. The given cost function used to evaluate the move included 4 arithmetic operators "+,-,*,/" and 9 terminals: "white, black, white_edges, black_edges, white_corners, black_corners, white_near_corners, black_near_corners, 10". During the game, the initial population consisted of various hypothesis (function trees) was produced, and the crossover and mutation operations were applied to them.

Approaches

• I. Variations on the hypothesis:
  
  We want to maximize the number of moves our player can make and at the same time, minimize the number of moves our opponent can make. This approach looked like a good heuristic: if at the end of the game, the player can make more moves than the opponent, it should potentially increase the chance of winning.
  
  To achieve this, we added two other primitives:
  
  
  possible_moves_white
  possible_moves_black
  
  
  Now after each move, the player would calculate the number of possible moves for its opponent and use this information.
  
  
• II. Variations on the learning method:
  
  Competitive fitness measure - population plays against itself or competing population co-evolve.
  
  There is a known biology fact that no two populations can occupy the same niche. We intend to see if this holds true for the genetic programming. If this holds true, and we still have one population left after the competition, will this champion be a very good Othello player? If not, maybe there is something wrong with our fitness measure to begin with, that our "niche" does not correctly reflect the real Othello playing scenario.
  
  We have created two "OurPlayers" which played against each other. To implement this part, we had to make quite a lot of changes to the given code.
  
  Our implementation was done in the following way: We created two "OurPlayers" WHITE and BLACK. WHITE was the player who's performance we wanted to improve. We were trying to find such a tree of the WHITE player who's performance would result in the lowest fitness of the BLACK player. For each fitness measure we played 5 games and took an average fitness as a result. We did 10 runs with 31 generations for each run (or until our fitness reached 40 - the termination fitness) and picked best individual from each run.
  
  We used fitness roulette algorithm as a criterion for selecting the best individual. The algorithm works in a way that it selects the best individual with a probability related to its fitness. In particular, the probability is equal to the fitness of this individual divided by the sum total fitness of all individuals of the population.
  
  Here came the problem that we didn't notice. (Q2 on the final exam.). Our fitness results are biased. We didn't compute the absolute fitness, we rather computed relative fitness and based our results on it.
  
  
• III. Methods to evaluate results.
  
  How often does it win? This must be evaluated over a large number of games (at least 100). First we decided to play the games against people. Then, we found it easier to test our player against professional player Edgar, since we didn't want to spend other people's time for our experiment.
  
  
  

Initial parameters

Problems

Results

In the first experiment, we have our player, OthelloOurPlayer play against OthelloRandomPlayer:

Also worth nothing is that our OthelloOurPlayer was trained to be the WHITE player. In its match against Edgar, we simply switched the white primitives in the resulting trees to black ones and vice versa, for all the primitives. This might not accurately reflect the result.

It might be helpful if we could run a separate training in which we train our OthelloOurPlayer to play BLACK.

Conclusions:

1. The main conclusion that we draw from our experiments is that although the fitness is relative to other players in the population, it gets better in an absolute sense, as compared to random players.

2. Judging from the results on OthelloOurPlayer vs. OthelloRandomPlayer, we realize that corners are very important (see the first results table above, run # 2, 3, 4 against run # 5, 8).

   Our primitives possible_moves_white and possible_moves_black did not seem to help significantly in the evaluation of the board.

3. Judging from the results on Edgar vs. OthelloOurPlayer, we noticed that it might be helpful if we have our OthelloOurPlayer learned from Edgar rather than itself.

   Edgar apparently is a stronger opponent, and our OthelloOurPlayer might be able to learn more from it and become a better player.

   As it was mentioned earlier, our potential limitation is that we trained our player to be the WHITE player. Since Edgar always plays WHITE we were forced to play OthelloOurPlayer BLACK. This is potential limitation (results for Edgar might not be accurate).

4. If we were given more resources, e.g., more computational power, we could have trained our OthelloOurPlayer against Edgar and against OthelloRandomPlayer. In these scenarios, we could determine if the experiments are domain dependent.