From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * ACPP

Structure of ACCP [1]

ACPP, (Advanced Chess Playing Program)
an experimental chess program by William Tunstall-Pedoe, which was research vehicle on genetic algorithms and automated tuning, described in the September 1991 ICCA Journal, and before in his 1991 CST Part II Dissertation. While Tunstall-Pedoe mentioned the applicability of GA in search parameter tuning for instance with impact in move ordering, he focused on evaluation weights. A population of 50 individual chess playing programs was used with randomly initialized chromosomes representing the concatenated weights to optimize. Inside the optimization loop, the genetic operator determines the fitness of all individuals, to breed the new generation favouring parent selection towards fitter individuals.



Feature weights are defined by a fixed base value, plus a variable delta range coded by a number of consecutive bits inside a chromosome - a bit array of 145 bits in total. For instance material weights uses four 11-bit delta scores to modify the weights of queens, rooks, bishops and knights in a millipawn resolution, to add up to 2048 to its appropriate base values (2000, 2000, 4000, 8000), while pawns have a fixed weight of 1000.


The fitness function of a chess entity deals with measuring or estimating its relative playing strength. The obvious approach by pitting all individuals in the population against one another and assess fitness by the score achieved in a tournament, was too time consuming in 1991 - at least 1250 games need to be played per generation with a reasonable minimal search depth, and the known objections against such single-replica round-robin tournaments. The method eventually adopted was using a set of about 28,000 grandmaster positions to apply Move adaption with a shallow one ply plus quiescence search. The fitness was defined as the number of times in a random sample of 500 positions that the individual's choice of move matched the Grandmaster move [2]. Despite the relative efficiency of the fitness function used compared with one from game playing, the algorithm is still very slow, taking about four hours per generation. ACCP ran at 180 nodes per second.


The generational process was repeated with a crossover probability of 0.5 and a mutation probability of 0.001. Fitness scaling [3] [4] was used to enhance the fittest members' fitness in each generation to twice the average fitness while keeping the average the same.


The graph shows the raw unscaled fitness against generation number [5].


The "learned" values, in particular material weights, showed little correlation with established point values. Careful consideration of the fitness function provides a possible explanation for this discrepancy. Although any single move results in immediate changes to most positional features, the only way it affects material scores is if it is a capture. At the time of the publication, the open question remained whether tuning designed to mimic Grandmasters will make the program so tuned optimal in game playing.

See also


External Links


  1. Structure of the ACPP protein. Based on PyMOL rendering of PDB 1cvi, image created by Emw, December 15, 2009, Wikimedia Commons
  2. William Tunstall-Pedoe (1991). Genetic Algorithms Optimizing Evaluation Functions. ICCA Journal, Vol. 14, No. 3
  3. David E. Goldberg (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, pp. 76-80
  4. Fitness Scaling - MATLAB & Simulink
  5. William Tunstall-Pedoe (1991). Genetic Algorithms Optimizing Evaluation Functions. ICCA Journal, Vol. 14, No. 3, image pp. 124

Up one Level