Carleton University - School of Computer Science Honours Project
Winter 2019
A Darwinian Approach to Checkers
SCS Honours Project Image
ABSTRACT
Checkers is a strategy board game played between two players. Strategy board games have extensively been studied in AI. Minimax is at the heart of every AI algorithm used in computer board games. So far, most of the research has focused on variations of the algorithm to improve its efficiency. These include alpha-beta pruning, negamax, negascount, etc. Not much research has been done in the application of genetic strategies to board games. Genetic algorithms in general have been found to be very effective and efficient at finding optimal solutions in other fields. For example, genetic algorithms can find an optimal solution to the travelling salesman problem (which is NP hard) within a reasonable amount of time. In this report, we investigate a variation of minimax that makes use of genetic algorithms to find an optimal solution quickly. A genetic minimax strategy for Checkers is implemented and tested against minimax. Our experiments show that the genetic approach beats minimax at all ply levels greater than one as well as outperforming it in execution time.