CS 4771 Machine Learning - Othello
Introduction
Othello is a game where two players use black and white tiles on a 8 x 8 board trying to have as many tiles as she/he can on it by the end of the game. All tiles between two same color tiles become the same color as them. At the end of the game, whoever has the most tiles on the board wins. In this project, genetic programming is used to evolve players that play Othello. How players evolved depend on many attributes of the evolution, such as the number of instances(players) in a population, number of generation in the evolution, and most of all, how the next generation is generated. The goal of this project is to experiment how these attributes effect the players that the evolution generates.
Approach
There are four main categories in this experiment.
Population = 100, Generation = 10.
Population = 100, Generation = 50.
Population = 500, Generation = 10.
Population = 500, Generation = 50.
In each category, the creation probability (0 or 90), swap mutation probability (0 or 90), and Add-Best instances to next generation (True or False) are altered. Ten runs are performed for each variation and the best player, against Random Player, is shown in the next table. Other attributes of the evolution remain the same.
Results
Population |
Generation |
Creation Probability |
Swap Mutation Probability |
Add Best to Next Gen |
vs. Edgar |
vs. Random (# won out of 50) |
---|---|---|---|---|---|---|
100 |
10 |
0 |
0 |
FALSE |
Lost |
white (44) |
100 |
10 |
90 |
0 |
FALSE |
Lost |
white (44) |
100 |
10 |
0 |
90 |
FALSE |
Lost |
( - white 10 ) (48) |
100 |
10 |
90 |
90 |
FALSE |
Lost |
( - white 10 ) (48) |
100 |
10 |
0 |
0 |
TRUE |
Lost |
( - 10 black ) (47) |
100 |
10 |
90 |
90 |
TRUE |
Lost |
|
100 |
50 |
0 |
0 |
FALSE |
Lost |
white (44) |
100 |
50 |
90 |
0 |
FALSE |
Lost |
white (44) |
100 |
50 |
0 |
90 |
FALSE |
Lost |
( - white 10 ) (48) |
|
|
|
|
|
Draw |
( / white black_near_corners ) (31) |
100 |
50 |
90 |
90 |
FALSE |
Lost |
( - white white_corners ) (44) |
100 |
50 |
0 |
0 |
TRUE |
Lost |
white (44) |
100 |
50 |
90 |
90 |
TRUE |
Lost |
white (44) |
500 |
10 |
0 |
0 |
FALSE |
Lost |
white (44) |
500 |
10 |
90 |
0 |
FALSE |
Lost |
white (44) |
500 |
10 |
0 |
90 |
FALSE |
Lost |
( - white 10 ) (48) |
500 |
10 |
90 |
90 |
FALSE |
Lost |
( + white black_corners ) (44) |
500 |
50 |
0 |
0 |
FALSE |
Lost |
white (44) |
500 |
50 |
90 |
0 |
FALSE |
Lost |
white (44) |
500 |
50 |
0 |
90 |
FALSE |
Lost |
white (44) |
500 |
50 |
90 |
90 |
FALSE |
Lost |
white (44) |
Analysis and Conclusion
The player that appeared most frequent in this experiment in all the variation is ( white ). It appear to be the most general, well performed player, although it's not the best. When the process to create the next generation have more variety, high creation probability and/or swap mutation probability, other (better) players emerge. There was a surprised that the only player that didn't lose to Edgar, which is a strong player, has the lowest score against Random Player. It's possible that because Edgar plays according to a certain rule and Random Players don't, the generated players happens to play against Edgar's rule. From the experiment result, we can conclude that the population size and the number of generations doesn't effect the resulting instances much. It's the way how each generation is created that effects the resulting instances.