CS 4771 Machine Learning - Othello

Kuan-Hung Lin

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.

  1. Population = 100, Generation = 10.

  2. Population = 100, Generation = 50.

  3. Population = 500, Generation = 10.

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