25,161
edits
Changes
ACPP
,Created page with "'''Home * Engines * ACPP''' '''ACPP''', (Advanced Chess Playing Program)<br/> an experimental chess program by William Tunstall-Pedoe, which was researc..."
'''[[Main Page|Home]] * [[Engines]] * ACPP'''
'''ACPP''', (Advanced Chess Playing Program)<br/>
an experimental chess program by [[William Tunstall-Pedoe]], which was research vehicle on [[Genetic Programming#GeneticAlgorithm|genetic algorithms]] for [[Automated Tuning|automated tuning]], described and the September 1991 [[ICGA Journal#14_3|ICCA Journal]], and before in his 1991 CST Part II Dissertation.
While Tunstall-Pedoe mentioned the applicability of GA in [[Search|search]] parameter tuning for instance with impact in [[Move Ordering|move ordering]],
he focused on [[Evaluation|evaluation]] weights. A population of 50 individual chess playing programs was used with randomly initialized [https://en.wikipedia.org/wiki/Chromosome chromosomes] representing the concatenated weights to optimize.
Inside the optimization loop, the [https://en.wikipedia.org/wiki/Genetic_operator genetic operator] determines the [https://en.wikipedia.org/wiki/Fitness_function fitness] of all individuals, to breed the new generation favouring parent [https://en.wikipedia.org/wiki/Selection_(genetic_algorithm) selection] towards fitter individuals.
=Features=
* [[Material]]
* [[Mobility]]
* [[Center Control]]
* [[Development]]
* [[King Safety#KingTropism|Queen King Tropism]]
* [[King Safety#KingTropism|Rook King Tropism]]
* [[Rook on Open File|Rook on (Semi) Open Files]]
* [[Isolated Pawn|Isolated Pawns]]
* [[Passed Pawn|Passed Pawns]], Σ Number of Squares of [[Pawn Spans|Rearspan]]
* [[Square Control]] (Number of Squares Attacked in Opponent's Half)
=Weights=
Feature weights are defined by a fixed base value, plus a variable delta range coded by a number consecutive bits inside a [https://en.wikipedia.org/wiki/Chromosome chromosome] - a binary string of 145 bits in total.
For instance [[Material|material]] weights uses four 11 bit deltas to modify the weights of [[Queen|queens]], [[Rook|rooks]], [[Bishop|bishops]] and [[Knight|knights]] in a [[Millipawns|millipawn]] resolution, to add up to 2048 to its appropriate base values (2000, 2000, 4000, 8000), while [[Pawn|pawns]] have a fixed weight of 1000.
=Fitness=
The [https://en.wikipedia.org/wiki/Fitness_function fitness function] of a chess entity deals with measuring or estimating its relative [[Playing Strength|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 [[Depth|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 [[Automated Tuning#MoveAdaption|Move adaption]]
with a shallow one ply plus [[Quiescence Search|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 <ref>[[William Tunstall-Pedoe]] ('''1991'''). ''Genetic Algorithms Optimizing Evaluation Functions''. [[ICGA Journal#14_3|ICCA Journal, Vol. 14, No. 3]]</ref>.
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|nodes per second]].
=Results=
The generational process was repeated with a [https://en.wikipedia.org/wiki/Crossover_(genetic_algorithm) crossover] probability of 0.5
and a [https://en.wikipedia.org/wiki/Mutation_(genetic_algorithm) mutation probability] of 0.001. Fitness scaling
<ref>[[David E. Goldberg]] ('''1989'''). ''Genetic Algorithms in Search, Optimization, and Machine Learning''. [https://en.wikipedia.org/wiki/Addison-Wesley Addison-Wesley], pp. 76-80</ref> <ref>[https://www.mathworks.com/help/gads/fitness-scaling.html Fitness Scaling - MATLAB & Simulink]</ref>
was used to enhance the fittest members' fitness in each generation to twice the average fitness while keeping the average the same.
[[File:acppGA.jpg|none|border|text-bottom]]
The graph shows the raw unscaled fitness against generation number <ref>[[William Tunstall-Pedoe]] ('''1991'''). ''Genetic Algorithms Optimizing Evaluation Functions''. [[ICGA Journal#14_3|ICCA Journal, Vol. 14, No. 3]], image pp. 124</ref>.
=Conclusion=
The "learned" values, in particular material weights, showed little correlation with established [[Point Value|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 [[Captures|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=
* [[Cyber Chess]]
* [[Falcon]]
=Publications=
* [[William Tunstall-Pedoe]] ('''1991'''). ''An Advanced Chess-Playing Program''. CST Part II Dissertation, [https://en.wikipedia.org/wiki/University_of_Cambridge University of Cambridge] [http://www.cl.cam.ac.uk/ Computer Laboratory], England (unpublished, referred in ''Genetic Algorithms ...'')
* [[William Tunstall-Pedoe]] ('''1991'''). ''Genetic Algorithms Optimizing Evaluation Functions''. [[ICGA Journal#14_3|ICCA Journal, Vol. 14, No. 3]]
=External Links=
* [[:Category:The Who|The Who]] - [https://en.wikipedia.org/wiki/My_Generation My Generation] (live 1967), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=qjN5uHRIcjM|alignment=left|valignment=top}}
=References=
<references />
'''[[Engines|Up one Level]]'''
[[Category:Acronym]]
[[Category:Thesis]]
[[Category:The Who]]
'''ACPP''', (Advanced Chess Playing Program)<br/>
an experimental chess program by [[William Tunstall-Pedoe]], which was research vehicle on [[Genetic Programming#GeneticAlgorithm|genetic algorithms]] for [[Automated Tuning|automated tuning]], described and the September 1991 [[ICGA Journal#14_3|ICCA Journal]], and before in his 1991 CST Part II Dissertation.
While Tunstall-Pedoe mentioned the applicability of GA in [[Search|search]] parameter tuning for instance with impact in [[Move Ordering|move ordering]],
he focused on [[Evaluation|evaluation]] weights. A population of 50 individual chess playing programs was used with randomly initialized [https://en.wikipedia.org/wiki/Chromosome chromosomes] representing the concatenated weights to optimize.
Inside the optimization loop, the [https://en.wikipedia.org/wiki/Genetic_operator genetic operator] determines the [https://en.wikipedia.org/wiki/Fitness_function fitness] of all individuals, to breed the new generation favouring parent [https://en.wikipedia.org/wiki/Selection_(genetic_algorithm) selection] towards fitter individuals.
=Features=
* [[Material]]
* [[Mobility]]
* [[Center Control]]
* [[Development]]
* [[King Safety#KingTropism|Queen King Tropism]]
* [[King Safety#KingTropism|Rook King Tropism]]
* [[Rook on Open File|Rook on (Semi) Open Files]]
* [[Isolated Pawn|Isolated Pawns]]
* [[Passed Pawn|Passed Pawns]], Σ Number of Squares of [[Pawn Spans|Rearspan]]
* [[Square Control]] (Number of Squares Attacked in Opponent's Half)
=Weights=
Feature weights are defined by a fixed base value, plus a variable delta range coded by a number consecutive bits inside a [https://en.wikipedia.org/wiki/Chromosome chromosome] - a binary string of 145 bits in total.
For instance [[Material|material]] weights uses four 11 bit deltas to modify the weights of [[Queen|queens]], [[Rook|rooks]], [[Bishop|bishops]] and [[Knight|knights]] in a [[Millipawns|millipawn]] resolution, to add up to 2048 to its appropriate base values (2000, 2000, 4000, 8000), while [[Pawn|pawns]] have a fixed weight of 1000.
=Fitness=
The [https://en.wikipedia.org/wiki/Fitness_function fitness function] of a chess entity deals with measuring or estimating its relative [[Playing Strength|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 [[Depth|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 [[Automated Tuning#MoveAdaption|Move adaption]]
with a shallow one ply plus [[Quiescence Search|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 <ref>[[William Tunstall-Pedoe]] ('''1991'''). ''Genetic Algorithms Optimizing Evaluation Functions''. [[ICGA Journal#14_3|ICCA Journal, Vol. 14, No. 3]]</ref>.
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|nodes per second]].
=Results=
The generational process was repeated with a [https://en.wikipedia.org/wiki/Crossover_(genetic_algorithm) crossover] probability of 0.5
and a [https://en.wikipedia.org/wiki/Mutation_(genetic_algorithm) mutation probability] of 0.001. Fitness scaling
<ref>[[David E. Goldberg]] ('''1989'''). ''Genetic Algorithms in Search, Optimization, and Machine Learning''. [https://en.wikipedia.org/wiki/Addison-Wesley Addison-Wesley], pp. 76-80</ref> <ref>[https://www.mathworks.com/help/gads/fitness-scaling.html Fitness Scaling - MATLAB & Simulink]</ref>
was used to enhance the fittest members' fitness in each generation to twice the average fitness while keeping the average the same.
[[File:acppGA.jpg|none|border|text-bottom]]
The graph shows the raw unscaled fitness against generation number <ref>[[William Tunstall-Pedoe]] ('''1991'''). ''Genetic Algorithms Optimizing Evaluation Functions''. [[ICGA Journal#14_3|ICCA Journal, Vol. 14, No. 3]], image pp. 124</ref>.
=Conclusion=
The "learned" values, in particular material weights, showed little correlation with established [[Point Value|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 [[Captures|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=
* [[Cyber Chess]]
* [[Falcon]]
=Publications=
* [[William Tunstall-Pedoe]] ('''1991'''). ''An Advanced Chess-Playing Program''. CST Part II Dissertation, [https://en.wikipedia.org/wiki/University_of_Cambridge University of Cambridge] [http://www.cl.cam.ac.uk/ Computer Laboratory], England (unpublished, referred in ''Genetic Algorithms ...'')
* [[William Tunstall-Pedoe]] ('''1991'''). ''Genetic Algorithms Optimizing Evaluation Functions''. [[ICGA Journal#14_3|ICCA Journal, Vol. 14, No. 3]]
=External Links=
* [[:Category:The Who|The Who]] - [https://en.wikipedia.org/wiki/My_Generation My Generation] (live 1967), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=qjN5uHRIcjM|alignment=left|valignment=top}}
=References=
<references />
'''[[Engines|Up one Level]]'''
[[Category:Acronym]]
[[Category:Thesis]]
[[Category:The Who]]
