In this project, I have studied the ability of a computer system to learn to play checkers, using a genetic algorithm to find the optimum coefficients for a simple utility function. The computer learns the game by playing itself, and in the final system, a human plays checkers against the computer.

The game of checkers has been well-studied over the past 50 years. Its search space is much smaller than that of chess, which translates to a simpler utility function, a much smaller branching factor in its search tree, and therefore a more successful machine player given the same resources. A world-champion checkers player is well within the range of desktop computing power.

Genetic algorithms, which attempt to mimic evolution, form an interesting and relatively new branch of artificial intelligence. The goal of this project has been to evaluate the performance of the genetic algorithm as a local search method for this type of problem.

The basic genetic algorithm is simple and straightforward: A population consists of individuals of varying fitness. Those individuals who are most fit are most likely to survive to reproduce. In reproduction, the offspring receive some of their traits from one parent and some from the other parent, subject to a small probability of mutation. The algorithm repeats until some arbitrary fitness is attained or some number of generations have been simulated.

Here, "fitness" is taken to be checkers-playing ability. The "traits" are the coefficients for the utility function, which determines the desirability of a given game state. When playing a game, the "individual" always chooses the move that results in the most desirable state.