1. initialization: randomly generate n 70-bit chromosomes
2. evaluate fitness of each chromosome of a population
3. if (N generations is reached OR fitness value > threshold ) terminate
repeat until n offspring are generated
a. select pair of parents from current population based on fitness criterion
b. with probability p, apply crossover to generate two offspring
c. mutate the two offspring by randomly flipping some bits
4. replace the old population with the newly generated population
5. goto 2
Learning Result
With a population size of 10, a crossover rate of 0.75, mutation rate of 0.05, and 50 generations, following search parameters were learned after 35 hours, as noted, not necessarily the best parameter set for every chess program [15]:
^Yngvi Björnsson, Tony Marsland (2002). Learning Control of Search Extensions. Proceedings of the 6th Joint Conference on Information Sciences (JCIS 2002), pp. 446-449. pdf
a strong private chess engine [1] by Omid David and successor of Omid's earlier program Genesis. Falcon participated at three World Computer Chess Championships, the WCCC 2003 in Graz, the WCCC 2004 in Ramat Gan, and the WCCC 2008 in Beijing [2], as well the CCT6 on-line tournament. Book authors were Eros Riccio in 2004, and Erdogan Günes in 2008.
Falcon applies NegaScout/PVS with null move pruning, internal iterative deepening, dynamic move ordering by history and killer heuristic, multi-cut pruning, selective extensions, transposition table, and futility pruning near leaf nodes [3], and blockade detection in endgames [4].
Table of Contents
Genetic Algorithm
Omid David has combined his secret efforts with scientific publications, since Falcon was test-bed and object in research of verified null-move pruning [6], extended null-move reductions [7], and Genetic Algorithms in evaluation [8] [9] and search tuning [10], the latter on optimizing 18 search control parameters packed into a 70-bit chromosome. The fitness function is the total node count up to the solutions found, from the 879 most tactical positions of the Encyclopedia of Chess Middlegames [11], as already used by Yngvi Björnsson and Tony Marsland in Learning Control of Search Extensions [12], the lower the fitter. A one-point crossover uses the chromosomes of two parents, selected based on fitness criterion [13], and creates two offspring. The mutation operator randomly flips some bits with low probability.Falcon Breeding
Falcon's GA procedure as pseudo code [14]:1. initialization: randomly generate n 70-bit chromosomes 2. evaluate fitness of each chromosome of a population 3. if (N generations is reached OR fitness value > threshold ) terminate repeat until n offspring are generated a. select pair of parents from current population based on fitness criterion b. with probability p, apply crossover to generate two offspring c. mutate the two offspring by randomly flipping some bits 4. replace the old population with the newly generated population 5. goto 2Learning Result
With a population size of 10, a crossover rate of 0.75, mutation rate of 0.05, and 50 generations, following search parameters were learned after 35 hours, as noted, not necessarily the best parameter set for every chess program [15]:Selected Games
WCCC 2004 round 11, Falcon - Shredder [18]See also
Publications
Forum Posts
External Links
Falcon Chess Variant
Falcons
Common Kestrel from Wikipedia
Gyrfalcon from Wikipedia
Peregrine Falcon from Wikipedia
Saker Falcon from Wikipedia
Falconry
The Maltese Falcon
The Maltese Falcon (novel) from Wikipedia
The Maltese Falcon (1941 film) from Wikipedia
The Maltese Falcon (yacht) from Wikipedia
Misc
Falcón from Wikipedia
References
What links here?
Up one Level