parameter tuning. See also
http://talkchess.com/forum/viewtopic.ph ... 51&t=18864
While much of Rybka has been taken apart now, parameter tuning
remains one of Vas's secrets.
I tend to believe that his way of parameter tuning is superior to
both the approaches below. I also assume that it is not his skills as
IM that allows him to do this parameter tuning, but some automated
process that is unknown to the community.
There have been approaches to automatic parameter tuning before. One
is the deep blue way:
http://chessprogramming.wikispaces.com/Andreas+Nowatzyk
Another suggestion was made by Lars Bremer:
http://www.computerschach.de/index.php? ... &Itemid=41
See "Genetische Algorithmen in Denkspielen", link requires paid
registration and is in German.
Lars basically suggests to make a population where values for various
parameters are the genes. Copies of one chess engine that differ only
by the parameters decode the genes to engines. Fitness is playing
strength.
I tried to put this approach into practice, with some success but not
a breakthrough. I found weights for the basic evaluation features
(such as material - normalized to weight factor 1.0 - mobility, pawn
structure etc.). These weights were compiled into Onno and I kept them
in the released versions.
With the new values, Onno did better in my tests then before,
but I could not prove statistical significance. However, the new
weights where fairly different from the original weights, so this
procedure was definitely not one that "worked" by not changing
much. Random modification of weights by the same amount is
harmful. But I might just have been lucky with my GA results. Further
investigation by other people should answer that.
More computational power might help to improve the results. With
implementation of the genetic algorithm I followed the "Handbook of
Metaheuristics" by Glover/Kochenberger.
There is much room for improvement in the details below. I just post
how I did it:
Tournament style
================
Lars suggests to play Swiss tournaments. I opted for a smaller
population and played a round system. In later rounds, games between
individuals at the end of the table that do not influence the selected
individuals should be pruned (not implemented). I played 100000 nodes
per move.
Selection
=========
Selecting openings at random and playing not too many games introduces
enough randomness into the results. Therefore, I did the selection
deterministically. I select the first selected_size individuals. The
tournament winner gets the most "votes", runners up get a lower number
of votes. Overall like this:
Code: Select all
double rank_to_votes (int p_rank)
{
int boni = OperationsRc::selected_size - 1 - p_rank;
if (boni < 0)
{
return 0.0;
}
else
{
double k = OperationsRc::selected_size;
double n = OperationsRc::population_size;
double a = 2 * (n-k) / (n*k*(k-1));
return 1/n + a*boni;
}
}
individual is selected for the next population. This is done by the
d'Hondt algorithm:
http://en.wikipedia.org/wiki/D%27Hondt_method
Operations
==========
There is crossover and mutation. Details are not worth to be mentioned.
Selection of final individual
=============================
To find the individual that undergoes normal gameplay tests, average
values from the population seem to work better than the best
individual. Note that these average values differ much from the
average values in the first population.