Evolving chess playing programs with Genetic Programming
Genetic Programming (GP) is a subspecies of evolutionary algorithms. It works on computer program representations rather than bit strings or real-valued vectors.
First, random programs are created. Then, in an ongoing cycle, the best programs according to a fitness function are selected and generate offspring (by some kind of recombination and mutation). The programs in the population are expected to get better by iterating this cycle.
GP was selected due to the fact that human chess programmers have not yet developed enough knowledge in the domain of chess that their efforts would be more than just iterated guessing of heuristics.
One can say, GP does the same, but in an organized manner.
The goal of this project was to evolve a chess program that plays a decent game of chess (and occasionally scores a win).
The project work led to a three-layered hierarchical representation of chess programs.
Modules were evolved seperately, first the 'a' ones, followed by 'b' and 'c'.
- Evaluation of a board position. Several criteria (like attack and defense, or greedy grabbing of opposing pieces) were considered in different fitness functions.
- Generating reasonable lists of candidate moves. It was allowed to call modules of type 'a'. Again, different fitness functions were used in parallel.
- Choice of one final move among the move lists generated from 'b' modules. 'A' modules were also ready to call. The general idea of this construction was to allow "reasoning" like this: if module a[n] regards the actual position as an attacking position, then pick a move suggested by the aggressive b[m] module.
The evolved programs played rather poor from an objective point of view.
Nevertheless, individual programs were evolved that were significally successful against their fellow programs, just by exploiting certain common program structures that were created by the genetic operators.
PeopleChessGP was a one year student project at the Computer Science Department of the University of Dortmund. It took place during the terms in winter 1999/2000 and in summer 2000.
People involved in the project group:
Students: Hassan Aburaya, Keno Albrecht, Roderich Groß, Patrick Gundlach, Martin Kleefeld, Andre Skusa, Martin Villwock, Thomas Vogd.
Tutors (from the Chair of Systems Analysis): Jens Busch and Wolfgang Kantschik
ChessGP project report (3.6 MB)