25,161
edits
Changes
Created page with "'''Home * Engines * Falcon''' [[FILE:FalcoMinorKeulemans.jpg|border|right|thumb| [https://en.wikipedia.org/wiki/Peregrine_falcon Falco minor] <ref>Source [h..."
'''[[Main Page|Home]] * [[Engines]] * Falcon'''
[[FILE:FalcoMinorKeulemans.jpg|border|right|thumb| [https://en.wikipedia.org/wiki/Peregrine_falcon Falco minor]
<ref>Source [https://en.wikipedia.org/wiki/John_Gerrard_Keulemans John Gerrard Keulemans] ('''1874'''). ''[https://commons.wikimedia.org/wiki/Catalogue_of_the_birds_in_the_British_Museum#Volume_1:_Accipitres,_or_diurnal_birds_of_prey_(1874) Catalogue of the birds in the British Museum]''. Vol. 1, Plate XII</ref> ]]
'''Falcon''',<br/>
a strong private chess engine <ref>[http://computer-chess.org/doku.php?id=computer_chess:wiki:lists:private_engine_list Private Engine List] from [[Ron Murawski|Ron Murawski's]] [http://computer-chess.org/doku.php?id=home Computer-Chess Wiki]</ref> by [[Omid David]] and successor of Omid's earlier program [[Genesis IL|Genesis]]. Falcon participated at three [[World Computer Chess Championship|World Computer Chess Championships]], the [[WCCC 2003]] in [https://en.wikipedia.org/wiki/Graz Graz], the [[WCCC 2004]] in [https://en.wikipedia.org/wiki/Ramat_Gan Ramat Gan], and the [[WCCC 2008]] in [https://en.wikipedia.org/wiki/Beijing Beijing] <ref>[https://www.game-ai-forum.org/icga-tournaments/program.php?id=108 Falcon's ICGA Tournaments]</ref>, as well the [[CCT6]] on-line tournament. Book authors were [[Eros Riccio]] in 2004, and [[Erdogan Günes]] in 2008.
=Features=
Falcon applies [[NegaScout]]/[[Principal Variation Search|PVS]] with [[Null Move Pruning|null move pruning]], [[Internal Iterative Deepening|internal iterative deepening]], [[Move Ordering|dynamic move ordering]] by [[History Heuristic|history]] and [[Killer Heuristic|killer heuristic]], [[Multi-Cut|multi-cut pruning]], [[Extensions|selective extensions]], [[Transposition Table|transposition table]], and [[Futility Pruning|futility pruning]] near [[Leaf Node|leaf nodes]] <ref>[[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Genetic Algorithms for Automatic Search Tuning''. [[ICGA Journal#33_2|ICGA Journal, Vol. 33, No. 2]]</ref>, and [[Blockage Detection|blockade detection]] in [[Endgame|endgames]] <ref>[[Omid David]], [[Ariel Felner]], [[Nathan S. Netanyahu]] ('''2004'''). ''Blockage Detection in Pawn Endgames''. [[ICGA Journal#27_3|ICGA Journal, Vol. 27, No. 3]]</ref>.
<span id="GA"></span>
=Genetic Algorithm=
Omid David has combined his secret efforts with scientific publications, since Falcon was test-bed and object in research of [[Null Move Pruning#ZugzwangVerification|verified null-move pruning]] <ref>[[Omid David]], [[Nathan S. Netanyahu]] ('''2002'''). ''Verified null-move pruning.'' [[ICGA Journal#25_3|ICGA Journal, Vol. 25, No. 3]]</ref>, [[Null Move Reductions|extended null-move reductions]] <ref>[[Omid David]], [[Nathan S. Netanyahu]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_19 Extended Null-Move Reductions]''. [[CG 2008]], [http://www.oedavid.com/pubs/nmr.pdf pdf]</ref>, and [[Genetic Programming#GeneticAlgorithm|Genetic Algorithms]] in [[Evaluation|evaluation]] <ref>[[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2008'''). ''Genetic Algorithms for Mentor-Assisted Evaluation Function Optimization''. ACM Genetic and Evolutionary Computation Conference ([http://www.sigevo.org/gecco-2008/ GECCO '08])</ref> <ref>[[Omid David]], [[Jaap van den Herik]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2009'''). ''Simulating Human Grandmasters: Evolution and Coevolution of Evaluation Functions''. [[ACM]] Genetic and Evolutionary Computation Conference ([http://www.sigevo.org/gecco-2009/ GECCO '09])</ref> and [[Search|search]] [[Automated Tuning|tuning]] <ref>[[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Genetic Algorithms for Automatic Search Tuning''. [[ICGA Journal#33_2|ICGA Journal, Vol. 33, No. 2]]</ref>, the latter on optimizing 18 search control parameters packed into a 70-bit [https://en.wikipedia.org/wiki/Chromosome chromosome]. The [https://en.wikipedia.org/wiki/Fitness_function fitness function] is the total [[Node|node]] count up to the solutions found, from the 879 most [[Tactics|tactical]] positions of the [[Test-Positions#ECM|Encyclopedia of Chess Middlegames]] <ref>[https://en.wikipedia.org/wiki/Nikolai_Krogius Nikolai Krogius], [http://www.goodreads.com/author/show/4451033.A_Livsic A. Livsic], [https://en.wikipedia.org/wiki/Bruno_Parma Bruno Parma], [https://en.wikipedia.org/wiki/Mark_Taimanov Mark Taimanov] ('''1980'''). ''[http://www.amazon.com/Encyclopedia-Chess-Middlegames-Nikolai-Krogius/dp/B000UNPDTA Encyclopedia of Chess Middlegames]''. [https://en.wikipedia.org/wiki/Chess_Informant Chess Informant]</ref>, as already used by [[Yngvi Björnsson]] and [[Tony Marsland]] in ''Learning Control of Search Extensions'' <ref>[[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. [http://www.ru.is/faculty/yngvi/pdf/BjornssonM02.pdf pdf]</ref>, the lower the fitter. A [https://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29#One-point_crossover one-point crossover] uses the chromosomes of two [https://en.wikipedia.org/wiki/Parent parents], [https://en.wikipedia.org/wiki/Selection selected] based on fitness criterion <ref>[http://chaos4.phy.ohiou.edu/~thomas/complex/ga.html Genetic algorithms]</ref>, and creates two [https://en.wikipedia.org/wiki/Offspring offspring]. The [https://en.wikipedia.org/wiki/Mutation_%28genetic_algorithm%29 mutation] operator randomly flips some bits with low probability.
==Falcon Breeding==
Falcon's GA procedure as pseudo code <ref>[[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Genetic Algorithms for Automatic Search Tuning''. [[ICGA Journal#33_2|ICGA Journal, Vol. 33, No. 2]], 4.2 Generic Algorithms</ref>:
<pre>
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
</pre>
==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 [[Learning|learned]] after 35 hours, as noted, not necessarily the best parameter set for every chess program <ref>[[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Genetic Algorithms for Automatic Search Tuning''. [[ICGA Journal#33_2|ICGA Journal, Vol. 33, No. 2]], 5. Experimental Results</ref>:
{| class="wikitable"
|-
! Parameter
! Value range
! Bits
! Learned
! Unit
|-
| [[Null Move Pruning|Null-move]] use
| style="text-align:right;" | 0-1
| style="text-align:right;" | 1
! 1
| style="text-align:right;" | Boolean
|-
| style="text-align:center;" | Null Move [[Depth Reduction R|R]]
| style="text-align:right;" | 0-7
| style="text-align:right;" | 3
! 4
| style="text-align:right;" | [[Ply|plies]]
|-
| style="text-align:center;" | Null Move [[Null Move Pruning#AdaptiveNullMovePruning|adaptivity]]
| style="text-align:right;" | 0-1
| style="text-align:right;" | 1
! 1
| style="text-align:right;" | Boolean
|-
| style="text-align:center;" | Null Move adaptivity depth <ref>if (adaptivity && depth <= adaptivity_depth) use R-1</ref>
| style="text-align:right;" | 0-7
| style="text-align:right;" | 3
! 6
| style="text-align:right;" | plies
|-
| [[Futility Pruning|Futility]] depth
| style="text-align:right;" | 0-3
| style="text-align:right;" | 2
! 3
| style="text-align:right;" | plies
|-
| style="text-align:center;" | Futility threshold depth-1
| style="text-align:right;" | 0-1023
| style="text-align:right;" | 10
! 106
| style="text-align:right;" | [[Centipawns|centipawns]]
|-
| style="text-align:center;" | Futility threshold depth-2
| style="text-align:right;" | 0-1023
| style="text-align:right;" | 10
! 219
| style="text-align:right;" | centipawns
|-
| style="text-align:center;" | Futility threshold depth-3
| style="text-align:right;" | 0-1023
| style="text-align:right;" | 10
! 512
| style="text-align:right;" | centipawns
|-
| [[Multi-Cut|Mult-cut]] use
| style="text-align:right;" | 0-1
| style="text-align:right;" | 1
! 1
| style="text-align:right;" | Boolean
|-
| style="text-align:center;" | Mult-cut R
| style="text-align:right;" | 0-7
| style="text-align:right;" | 3
! 4
| style="text-align:right;" | plies
|-
| style="text-align:center;" | Mult-cut depth <ref>Apply Mult-cut only if depth >= Mult-cut_depth</ref>
| style="text-align:right;" | 0-7
| style="text-align:right;" | 3
! 6
| style="text-align:right;" | plies
|-
| style="text-align:center;" | Mult-cut M
| style="text-align:right;" | 0-31
| style="text-align:right;" | 5
! 14
| style="text-align:right;" | number of moves
|-
| style="text-align:center;" | Mult-cut C
| style="text-align:right;" | 0-7
| style="text-align:right;" | 3
! 3
| style="text-align:right;" | number of moves
|-
| [[Check Extensions|Check extension]]
| style="text-align:right;" | 0-4
| style="text-align:right;" | 3
! 2
| style="text-align:right;" | [[Depth#FractionalPlies|quarter plies]]
|-
| [[One Reply Extensions|One-reply extension]]
| style="text-align:right;" | 0-4
| style="text-align:right;" | 3
! 4
| style="text-align:right;" | quarter plies
|-
| [[Recapture Extensions|Recapture extension]]
| style="text-align:right;" | 0-4
| style="text-align:right;" | 3
! 2
| style="text-align:right;" | quarter plies
|-
| [[Passed Pawn Extensions|Passed pawn extension]], 7th
| style="text-align:right;" | 0-4
| style="text-align:right;" | 3
! 3
| style="text-align:right;" | quarter plies
|-
| [[Mate Threat Extensions|Mate thread extension]]
| style="text-align:right;" | 0-4
| style="text-align:right;" | 3
! 1
| style="text-align:right;" | quarter plies
|-
!
!
! style="text-align:right;" | 70
! bit
!
|}
=Selected Games=
[[WCCC 2004]] round 11, [[Falcon]] - [[Shredder]] <ref>[https://www.game-ai-forum.org/icga-tournaments/round.php?tournament=24&round=11&id=5 Ramat-Gan 2004 - Chess - Round 11 - Game 5 (ICGA Tournaments)]</ref>
<pre>
[Event "WCCC 2004"]
[Site "Ramat Gan, Israel"]
[Date "2004.07.12"]
[Round "11"]
[White "Falcon"]
[Black "Shredder"]
[Result "1/2-1/2"]
1.e4 c5 2.Nf3 d6 3.d4 cxd4 4.Nxd4 Nf6 5.Nc3 a6 6.Be3 e6 7.f3 b5 8.g4 h6
9.Qd2 Nbd7 10.O-O-O Bb7 11.h4 d5 12.Bh3 b4 13.Na4 dxe4 14.g5 hxg5 15.hxg5
exf3 16.g6 Rxh3 17.Rxh3 Qa5 18.b3 Ne5 19.gxf7+ Kxf7 20.Bg5 Ne4 21.Qf4+ Kg8
22.Nxe6 Ng6 23.Rh8+ Nxh8 24.Rd7 Nf6 25.Bxf6 Ng6 26.Qd4 Qf5 27.Nxf8 Qxf6
28.Qxf6 gxf6 29.Nh7 Ne5 30.Nxf6+ Kf8 31.Nh7+ Kg8 32.Nf6+ Kf8 33.Nh7+ Kg8
34.Nf6+ 1/2-1/2
</pre>
=See also=
* [[Genesis IL|Genesis]]
=Publications=
* [[Omid David]], [[Nathan S. Netanyahu]] ('''2002'''). ''Verified null-move pruning.'' [[ICGA Journal#25_3|ICGA Journal, Vol. 25, No. 3]]
* [[Omid David]], [[Ariel Felner]], [[Nathan S. Netanyahu]] ('''2004'''). ''Blockage Detection in Pawn Endgames''. [[ICGA Journal#27_3|ICGA Journal, Vol. 27, No. 3]]
* [[Omid David]], [[Nathan S. Netanyahu]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_19 Extended Null-Move Reductions]''. [[CG 2008]], [http://www.oedavid.com/pubs/nmr.pdf pdf]
* [[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2008'''). ''Genetic Algorithms for Mentor-Assisted Evaluation Function Optimization''. [http://www.sigevo.org/gecco-2008/ GECCO '08]
* [[Omid David]] ('''2009'''). ''Genetic Algorithms Based Learning for Evolving Intelligent Organisms''. Ph.D. Thesis
* [[Omid David]], [[Jaap van den Herik]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2009'''). ''Simulating Human Grandmasters: Evolution and Coevolution of Evaluation Functions''.[http://www.sigevo.org/gecco-2009/ GECCO '09]
* [[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''[http://www.springerlink.com/content/3346t8432n718821 Expert-Driven Genetic Algorithms for Simulating Evaluation Functions]''.
* [[Omid David]], [[Nathan S. Netanyahu]], Yoav Rosenberg, Moshe Shimoni ('''2010'''). ''Genetic Algorithms for Automatic Classification of Moving Objects''. [http://www.sigevo.org/gecco-2010/ GECCO '10]
* [[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Genetic Algorithms for Automatic Search Tuning''. [[ICGA Journal#33_2|ICGA Journal, Vol. 33, No. 2]]
* [[Omid David]], [[Jaap van den Herik]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2014'''). ''Genetic Algorithms for Evolving Computer Chess Programs''. [[IEEE#EC|IEEE Transactions on Evolutionary Computation]], [http://www.genetic-programming.org/hc2014/David-Paper.pdf pdf] <ref>[http://www.liacs.nl/nieuws/jaap-van-den-herik-wint-humies-award-2014/ Jaap van den Herik wint Humies Award 2014 - LIACS - Leiden Institute of Advanced Computer Science]</ref> <ref>[http://www.sigevo.org/gecco-2014/humies.html GECCO 2014]</ref>
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=362359 Objective proposal Falcon - Crafty] by [[Vincent Diepeveen]], [[CCC]], April 29, 2004
* [https://www.stmintz.com/ccc/index.php?id=362605 Diep and Falcon #2 and 3] by Chessfun, [[CCC]], April 30, 2004
* [https://www.stmintz.com/ccc/index.php?id=376363 Re: Are you planning to make an SMP version of Falcon?] by [[Omid David]], [[CCC]], July 13, 2004
* [http://www.talkchess.com/forum/viewtopic.php?t=41768 Falcon by Omid David Tabibi] by [[Norbert Raimund Leisner]], [[CCC]], January 03, 2012
=External Links=
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=108 Falcon's ICGA Tournaments]
* [http://www.chessgames.com/perl/chessplayer?pid=29489 The chess games of Falcon] from [http://www.chessgames.com/index.html chessgames.com]
==Falcon Chess Variant==
* [http://www.chessvariants.org/large.dir/falcon.html Falcon Chess] from [http://www.chessvariants.org/ The Chess Variant Pages]
* [http://home.hccnet.nl/h.g.muller/falcon.html Falcon Chess] by [[Harm Geert Muller]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=22411 Falcon Chess] by [[Harm Geert Muller]], [[CCC]], July 17, 2008</ref>
==Falcons==
* [https://en.wikipedia.org/wiki/Falcon_%28disambiguation%29 Falcon (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Falcon Falcon from Wikipedia]
* [https://en.wikipedia.org/wiki/Sibley-Ahlquist_taxonomy_of_birds Sibley-Ahlquist taxonomy of birds from Wikipedia]
* [https://en.wikipedia.org/wiki/Falconiformes Falconiformes from Wikipedia]
* [https://en.wikipedia.org/wiki/Falconidae Falconidae from Wikipedia]
* [https://en.wikipedia.org/wiki/List_of_Falconidae List of Falconidae]
: [https://en.wikipedia.org/wiki/Common_Kestrel Common Kestrel from Wikipedia]
: [https://en.wikipedia.org/wiki/Gyrfalcon Gyrfalcon from Wikipedia]
: [https://en.wikipedia.org/wiki/Peregrine_Falcon Peregrine Falcon from Wikipedia]
: [https://en.wikipedia.org/wiki/Saker_Falcon Saker Falcon from Wikipedia]
* [http://www.bbc.co.uk/nature/life/Peregrine_Falcon BBC Nature - Peregrine falcon videos, news and facts]
* [http://www.ntu.ac.uk/ecoweb/biodiversity/falcons/index.html?campaignid=falcons Falcons - EcoWeb - Nottingham Trent University]
* [http://www.bbc.co.uk/news/uk-england-nottinghamshire-13358253 BBC News - Rare peregrine falcons raise four chicks in Nottingham]
* [http://www.falconcam-cmnh.org/news.php News - CMNH Falcon Cam]
* [http://www2.ucsc.edu/scpbrg/index.htm Santa Cruz Predatory Bird Research Group at UCSC - HOME]
* [http://www2.ucsc.edu/scpbrg/nestcamSF.htm SCPBRG: Peregrine Falcon Web Cam, San Francisco]
* [http://www.nickdunlop.com/ Nick Dunlop Photography]
==Falconry==
* [https://en.wikipedia.org/wiki/Falconry Falconry from Wikipedia]
* [https://en.wikipedia.org/wiki/De_arte_venandi_cum_avibus De arte venandi cum avibus] by [https://en.wikipedia.org/wiki/Frederick_II,_Holy_Roman_Emperor Frederick II - Wikipedia]
* [http://www.falconry.ca/index.htm Falconry Canada]
* [http://www.davidmaritz.com/stories/falconry/falconry.htm Falconry] by [http://www.davidmaritz.com/bio/bio.htm David Maritz]
* [http://www.nicolas-falcons.com/ Falconry - Falkenhorst Schloss Aschbach]
* [http://www.falconry.com/ Falconry Information Clearinghouse]
* [http://www.nad.ae/ Nad Al Shiba Falcons]
* [http://www.scottish-falcon-breeders.com/ Scottish Falcon Breeders]
==The Maltese Falcon==
* [https://en.wikipedia.org/wiki/The_Maltese_Falcon The Maltese Falcon (disambiguation) from Wikipedia]
: [https://en.wikipedia.org/wiki/The_Maltese_Falcon_%28novel%29 The Maltese Falcon (novel) from Wikipedia]
: [https://en.wikipedia.org/wiki/The_Maltese_Falcon_%281941_film%29 The Maltese Falcon (1941 film) from Wikipedia]
: [https://en.wikipedia.org/wiki/The_Maltese_Falcon_%28yacht%29 The Maltese Falcon (yacht) from Wikipedia]
==Misc==
* [https://en.wikipedia.org/wiki/Falc%C3%B3n_%28disambiguation%29 Falcón (disambiguation) from Wikipedia]
: [https://en.wikipedia.org/wiki/Falc%C3%B3n Falcón from Wikipedia]
* [https://en.wikipedia.org/wiki/Falcon_%28programming_language%29 Falcon (programming language) from Wikipedia]
* [https://en.wikipedia.org/wiki/Falcon_Northwest Falcon Northwest from Wikipedia]
* [https://en.wikipedia.org/wiki/Falkenberg_%28disambiguation%29 Falkenberg (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Falkenburg Falkenburg (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Valkenburg Valkenburg (disambiguation) from Wikipedia]
=References=
<references />
'''[[Engines|Up one Level]]'''
[[FILE:FalcoMinorKeulemans.jpg|border|right|thumb| [https://en.wikipedia.org/wiki/Peregrine_falcon Falco minor]
<ref>Source [https://en.wikipedia.org/wiki/John_Gerrard_Keulemans John Gerrard Keulemans] ('''1874'''). ''[https://commons.wikimedia.org/wiki/Catalogue_of_the_birds_in_the_British_Museum#Volume_1:_Accipitres,_or_diurnal_birds_of_prey_(1874) Catalogue of the birds in the British Museum]''. Vol. 1, Plate XII</ref> ]]
'''Falcon''',<br/>
a strong private chess engine <ref>[http://computer-chess.org/doku.php?id=computer_chess:wiki:lists:private_engine_list Private Engine List] from [[Ron Murawski|Ron Murawski's]] [http://computer-chess.org/doku.php?id=home Computer-Chess Wiki]</ref> by [[Omid David]] and successor of Omid's earlier program [[Genesis IL|Genesis]]. Falcon participated at three [[World Computer Chess Championship|World Computer Chess Championships]], the [[WCCC 2003]] in [https://en.wikipedia.org/wiki/Graz Graz], the [[WCCC 2004]] in [https://en.wikipedia.org/wiki/Ramat_Gan Ramat Gan], and the [[WCCC 2008]] in [https://en.wikipedia.org/wiki/Beijing Beijing] <ref>[https://www.game-ai-forum.org/icga-tournaments/program.php?id=108 Falcon's ICGA Tournaments]</ref>, as well the [[CCT6]] on-line tournament. Book authors were [[Eros Riccio]] in 2004, and [[Erdogan Günes]] in 2008.
=Features=
Falcon applies [[NegaScout]]/[[Principal Variation Search|PVS]] with [[Null Move Pruning|null move pruning]], [[Internal Iterative Deepening|internal iterative deepening]], [[Move Ordering|dynamic move ordering]] by [[History Heuristic|history]] and [[Killer Heuristic|killer heuristic]], [[Multi-Cut|multi-cut pruning]], [[Extensions|selective extensions]], [[Transposition Table|transposition table]], and [[Futility Pruning|futility pruning]] near [[Leaf Node|leaf nodes]] <ref>[[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Genetic Algorithms for Automatic Search Tuning''. [[ICGA Journal#33_2|ICGA Journal, Vol. 33, No. 2]]</ref>, and [[Blockage Detection|blockade detection]] in [[Endgame|endgames]] <ref>[[Omid David]], [[Ariel Felner]], [[Nathan S. Netanyahu]] ('''2004'''). ''Blockage Detection in Pawn Endgames''. [[ICGA Journal#27_3|ICGA Journal, Vol. 27, No. 3]]</ref>.
<span id="GA"></span>
=Genetic Algorithm=
Omid David has combined his secret efforts with scientific publications, since Falcon was test-bed and object in research of [[Null Move Pruning#ZugzwangVerification|verified null-move pruning]] <ref>[[Omid David]], [[Nathan S. Netanyahu]] ('''2002'''). ''Verified null-move pruning.'' [[ICGA Journal#25_3|ICGA Journal, Vol. 25, No. 3]]</ref>, [[Null Move Reductions|extended null-move reductions]] <ref>[[Omid David]], [[Nathan S. Netanyahu]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_19 Extended Null-Move Reductions]''. [[CG 2008]], [http://www.oedavid.com/pubs/nmr.pdf pdf]</ref>, and [[Genetic Programming#GeneticAlgorithm|Genetic Algorithms]] in [[Evaluation|evaluation]] <ref>[[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2008'''). ''Genetic Algorithms for Mentor-Assisted Evaluation Function Optimization''. ACM Genetic and Evolutionary Computation Conference ([http://www.sigevo.org/gecco-2008/ GECCO '08])</ref> <ref>[[Omid David]], [[Jaap van den Herik]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2009'''). ''Simulating Human Grandmasters: Evolution and Coevolution of Evaluation Functions''. [[ACM]] Genetic and Evolutionary Computation Conference ([http://www.sigevo.org/gecco-2009/ GECCO '09])</ref> and [[Search|search]] [[Automated Tuning|tuning]] <ref>[[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Genetic Algorithms for Automatic Search Tuning''. [[ICGA Journal#33_2|ICGA Journal, Vol. 33, No. 2]]</ref>, the latter on optimizing 18 search control parameters packed into a 70-bit [https://en.wikipedia.org/wiki/Chromosome chromosome]. The [https://en.wikipedia.org/wiki/Fitness_function fitness function] is the total [[Node|node]] count up to the solutions found, from the 879 most [[Tactics|tactical]] positions of the [[Test-Positions#ECM|Encyclopedia of Chess Middlegames]] <ref>[https://en.wikipedia.org/wiki/Nikolai_Krogius Nikolai Krogius], [http://www.goodreads.com/author/show/4451033.A_Livsic A. Livsic], [https://en.wikipedia.org/wiki/Bruno_Parma Bruno Parma], [https://en.wikipedia.org/wiki/Mark_Taimanov Mark Taimanov] ('''1980'''). ''[http://www.amazon.com/Encyclopedia-Chess-Middlegames-Nikolai-Krogius/dp/B000UNPDTA Encyclopedia of Chess Middlegames]''. [https://en.wikipedia.org/wiki/Chess_Informant Chess Informant]</ref>, as already used by [[Yngvi Björnsson]] and [[Tony Marsland]] in ''Learning Control of Search Extensions'' <ref>[[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. [http://www.ru.is/faculty/yngvi/pdf/BjornssonM02.pdf pdf]</ref>, the lower the fitter. A [https://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29#One-point_crossover one-point crossover] uses the chromosomes of two [https://en.wikipedia.org/wiki/Parent parents], [https://en.wikipedia.org/wiki/Selection selected] based on fitness criterion <ref>[http://chaos4.phy.ohiou.edu/~thomas/complex/ga.html Genetic algorithms]</ref>, and creates two [https://en.wikipedia.org/wiki/Offspring offspring]. The [https://en.wikipedia.org/wiki/Mutation_%28genetic_algorithm%29 mutation] operator randomly flips some bits with low probability.
==Falcon Breeding==
Falcon's GA procedure as pseudo code <ref>[[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Genetic Algorithms for Automatic Search Tuning''. [[ICGA Journal#33_2|ICGA Journal, Vol. 33, No. 2]], 4.2 Generic Algorithms</ref>:
<pre>
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
</pre>
==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 [[Learning|learned]] after 35 hours, as noted, not necessarily the best parameter set for every chess program <ref>[[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Genetic Algorithms for Automatic Search Tuning''. [[ICGA Journal#33_2|ICGA Journal, Vol. 33, No. 2]], 5. Experimental Results</ref>:
{| class="wikitable"
|-
! Parameter
! Value range
! Bits
! Learned
! Unit
|-
| [[Null Move Pruning|Null-move]] use
| style="text-align:right;" | 0-1
| style="text-align:right;" | 1
! 1
| style="text-align:right;" | Boolean
|-
| style="text-align:center;" | Null Move [[Depth Reduction R|R]]
| style="text-align:right;" | 0-7
| style="text-align:right;" | 3
! 4
| style="text-align:right;" | [[Ply|plies]]
|-
| style="text-align:center;" | Null Move [[Null Move Pruning#AdaptiveNullMovePruning|adaptivity]]
| style="text-align:right;" | 0-1
| style="text-align:right;" | 1
! 1
| style="text-align:right;" | Boolean
|-
| style="text-align:center;" | Null Move adaptivity depth <ref>if (adaptivity && depth <= adaptivity_depth) use R-1</ref>
| style="text-align:right;" | 0-7
| style="text-align:right;" | 3
! 6
| style="text-align:right;" | plies
|-
| [[Futility Pruning|Futility]] depth
| style="text-align:right;" | 0-3
| style="text-align:right;" | 2
! 3
| style="text-align:right;" | plies
|-
| style="text-align:center;" | Futility threshold depth-1
| style="text-align:right;" | 0-1023
| style="text-align:right;" | 10
! 106
| style="text-align:right;" | [[Centipawns|centipawns]]
|-
| style="text-align:center;" | Futility threshold depth-2
| style="text-align:right;" | 0-1023
| style="text-align:right;" | 10
! 219
| style="text-align:right;" | centipawns
|-
| style="text-align:center;" | Futility threshold depth-3
| style="text-align:right;" | 0-1023
| style="text-align:right;" | 10
! 512
| style="text-align:right;" | centipawns
|-
| [[Multi-Cut|Mult-cut]] use
| style="text-align:right;" | 0-1
| style="text-align:right;" | 1
! 1
| style="text-align:right;" | Boolean
|-
| style="text-align:center;" | Mult-cut R
| style="text-align:right;" | 0-7
| style="text-align:right;" | 3
! 4
| style="text-align:right;" | plies
|-
| style="text-align:center;" | Mult-cut depth <ref>Apply Mult-cut only if depth >= Mult-cut_depth</ref>
| style="text-align:right;" | 0-7
| style="text-align:right;" | 3
! 6
| style="text-align:right;" | plies
|-
| style="text-align:center;" | Mult-cut M
| style="text-align:right;" | 0-31
| style="text-align:right;" | 5
! 14
| style="text-align:right;" | number of moves
|-
| style="text-align:center;" | Mult-cut C
| style="text-align:right;" | 0-7
| style="text-align:right;" | 3
! 3
| style="text-align:right;" | number of moves
|-
| [[Check Extensions|Check extension]]
| style="text-align:right;" | 0-4
| style="text-align:right;" | 3
! 2
| style="text-align:right;" | [[Depth#FractionalPlies|quarter plies]]
|-
| [[One Reply Extensions|One-reply extension]]
| style="text-align:right;" | 0-4
| style="text-align:right;" | 3
! 4
| style="text-align:right;" | quarter plies
|-
| [[Recapture Extensions|Recapture extension]]
| style="text-align:right;" | 0-4
| style="text-align:right;" | 3
! 2
| style="text-align:right;" | quarter plies
|-
| [[Passed Pawn Extensions|Passed pawn extension]], 7th
| style="text-align:right;" | 0-4
| style="text-align:right;" | 3
! 3
| style="text-align:right;" | quarter plies
|-
| [[Mate Threat Extensions|Mate thread extension]]
| style="text-align:right;" | 0-4
| style="text-align:right;" | 3
! 1
| style="text-align:right;" | quarter plies
|-
!
!
! style="text-align:right;" | 70
! bit
!
|}
=Selected Games=
[[WCCC 2004]] round 11, [[Falcon]] - [[Shredder]] <ref>[https://www.game-ai-forum.org/icga-tournaments/round.php?tournament=24&round=11&id=5 Ramat-Gan 2004 - Chess - Round 11 - Game 5 (ICGA Tournaments)]</ref>
<pre>
[Event "WCCC 2004"]
[Site "Ramat Gan, Israel"]
[Date "2004.07.12"]
[Round "11"]
[White "Falcon"]
[Black "Shredder"]
[Result "1/2-1/2"]
1.e4 c5 2.Nf3 d6 3.d4 cxd4 4.Nxd4 Nf6 5.Nc3 a6 6.Be3 e6 7.f3 b5 8.g4 h6
9.Qd2 Nbd7 10.O-O-O Bb7 11.h4 d5 12.Bh3 b4 13.Na4 dxe4 14.g5 hxg5 15.hxg5
exf3 16.g6 Rxh3 17.Rxh3 Qa5 18.b3 Ne5 19.gxf7+ Kxf7 20.Bg5 Ne4 21.Qf4+ Kg8
22.Nxe6 Ng6 23.Rh8+ Nxh8 24.Rd7 Nf6 25.Bxf6 Ng6 26.Qd4 Qf5 27.Nxf8 Qxf6
28.Qxf6 gxf6 29.Nh7 Ne5 30.Nxf6+ Kf8 31.Nh7+ Kg8 32.Nf6+ Kf8 33.Nh7+ Kg8
34.Nf6+ 1/2-1/2
</pre>
=See also=
* [[Genesis IL|Genesis]]
=Publications=
* [[Omid David]], [[Nathan S. Netanyahu]] ('''2002'''). ''Verified null-move pruning.'' [[ICGA Journal#25_3|ICGA Journal, Vol. 25, No. 3]]
* [[Omid David]], [[Ariel Felner]], [[Nathan S. Netanyahu]] ('''2004'''). ''Blockage Detection in Pawn Endgames''. [[ICGA Journal#27_3|ICGA Journal, Vol. 27, No. 3]]
* [[Omid David]], [[Nathan S. Netanyahu]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_19 Extended Null-Move Reductions]''. [[CG 2008]], [http://www.oedavid.com/pubs/nmr.pdf pdf]
* [[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2008'''). ''Genetic Algorithms for Mentor-Assisted Evaluation Function Optimization''. [http://www.sigevo.org/gecco-2008/ GECCO '08]
* [[Omid David]] ('''2009'''). ''Genetic Algorithms Based Learning for Evolving Intelligent Organisms''. Ph.D. Thesis
* [[Omid David]], [[Jaap van den Herik]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2009'''). ''Simulating Human Grandmasters: Evolution and Coevolution of Evaluation Functions''.[http://www.sigevo.org/gecco-2009/ GECCO '09]
* [[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''[http://www.springerlink.com/content/3346t8432n718821 Expert-Driven Genetic Algorithms for Simulating Evaluation Functions]''.
* [[Omid David]], [[Nathan S. Netanyahu]], Yoav Rosenberg, Moshe Shimoni ('''2010'''). ''Genetic Algorithms for Automatic Classification of Moving Objects''. [http://www.sigevo.org/gecco-2010/ GECCO '10]
* [[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Genetic Algorithms for Automatic Search Tuning''. [[ICGA Journal#33_2|ICGA Journal, Vol. 33, No. 2]]
* [[Omid David]], [[Jaap van den Herik]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2014'''). ''Genetic Algorithms for Evolving Computer Chess Programs''. [[IEEE#EC|IEEE Transactions on Evolutionary Computation]], [http://www.genetic-programming.org/hc2014/David-Paper.pdf pdf] <ref>[http://www.liacs.nl/nieuws/jaap-van-den-herik-wint-humies-award-2014/ Jaap van den Herik wint Humies Award 2014 - LIACS - Leiden Institute of Advanced Computer Science]</ref> <ref>[http://www.sigevo.org/gecco-2014/humies.html GECCO 2014]</ref>
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=362359 Objective proposal Falcon - Crafty] by [[Vincent Diepeveen]], [[CCC]], April 29, 2004
* [https://www.stmintz.com/ccc/index.php?id=362605 Diep and Falcon #2 and 3] by Chessfun, [[CCC]], April 30, 2004
* [https://www.stmintz.com/ccc/index.php?id=376363 Re: Are you planning to make an SMP version of Falcon?] by [[Omid David]], [[CCC]], July 13, 2004
* [http://www.talkchess.com/forum/viewtopic.php?t=41768 Falcon by Omid David Tabibi] by [[Norbert Raimund Leisner]], [[CCC]], January 03, 2012
=External Links=
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=108 Falcon's ICGA Tournaments]
* [http://www.chessgames.com/perl/chessplayer?pid=29489 The chess games of Falcon] from [http://www.chessgames.com/index.html chessgames.com]
==Falcon Chess Variant==
* [http://www.chessvariants.org/large.dir/falcon.html Falcon Chess] from [http://www.chessvariants.org/ The Chess Variant Pages]
* [http://home.hccnet.nl/h.g.muller/falcon.html Falcon Chess] by [[Harm Geert Muller]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=22411 Falcon Chess] by [[Harm Geert Muller]], [[CCC]], July 17, 2008</ref>
==Falcons==
* [https://en.wikipedia.org/wiki/Falcon_%28disambiguation%29 Falcon (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Falcon Falcon from Wikipedia]
* [https://en.wikipedia.org/wiki/Sibley-Ahlquist_taxonomy_of_birds Sibley-Ahlquist taxonomy of birds from Wikipedia]
* [https://en.wikipedia.org/wiki/Falconiformes Falconiformes from Wikipedia]
* [https://en.wikipedia.org/wiki/Falconidae Falconidae from Wikipedia]
* [https://en.wikipedia.org/wiki/List_of_Falconidae List of Falconidae]
: [https://en.wikipedia.org/wiki/Common_Kestrel Common Kestrel from Wikipedia]
: [https://en.wikipedia.org/wiki/Gyrfalcon Gyrfalcon from Wikipedia]
: [https://en.wikipedia.org/wiki/Peregrine_Falcon Peregrine Falcon from Wikipedia]
: [https://en.wikipedia.org/wiki/Saker_Falcon Saker Falcon from Wikipedia]
* [http://www.bbc.co.uk/nature/life/Peregrine_Falcon BBC Nature - Peregrine falcon videos, news and facts]
* [http://www.ntu.ac.uk/ecoweb/biodiversity/falcons/index.html?campaignid=falcons Falcons - EcoWeb - Nottingham Trent University]
* [http://www.bbc.co.uk/news/uk-england-nottinghamshire-13358253 BBC News - Rare peregrine falcons raise four chicks in Nottingham]
* [http://www.falconcam-cmnh.org/news.php News - CMNH Falcon Cam]
* [http://www2.ucsc.edu/scpbrg/index.htm Santa Cruz Predatory Bird Research Group at UCSC - HOME]
* [http://www2.ucsc.edu/scpbrg/nestcamSF.htm SCPBRG: Peregrine Falcon Web Cam, San Francisco]
* [http://www.nickdunlop.com/ Nick Dunlop Photography]
==Falconry==
* [https://en.wikipedia.org/wiki/Falconry Falconry from Wikipedia]
* [https://en.wikipedia.org/wiki/De_arte_venandi_cum_avibus De arte venandi cum avibus] by [https://en.wikipedia.org/wiki/Frederick_II,_Holy_Roman_Emperor Frederick II - Wikipedia]
* [http://www.falconry.ca/index.htm Falconry Canada]
* [http://www.davidmaritz.com/stories/falconry/falconry.htm Falconry] by [http://www.davidmaritz.com/bio/bio.htm David Maritz]
* [http://www.nicolas-falcons.com/ Falconry - Falkenhorst Schloss Aschbach]
* [http://www.falconry.com/ Falconry Information Clearinghouse]
* [http://www.nad.ae/ Nad Al Shiba Falcons]
* [http://www.scottish-falcon-breeders.com/ Scottish Falcon Breeders]
==The Maltese Falcon==
* [https://en.wikipedia.org/wiki/The_Maltese_Falcon The Maltese Falcon (disambiguation) from Wikipedia]
: [https://en.wikipedia.org/wiki/The_Maltese_Falcon_%28novel%29 The Maltese Falcon (novel) from Wikipedia]
: [https://en.wikipedia.org/wiki/The_Maltese_Falcon_%281941_film%29 The Maltese Falcon (1941 film) from Wikipedia]
: [https://en.wikipedia.org/wiki/The_Maltese_Falcon_%28yacht%29 The Maltese Falcon (yacht) from Wikipedia]
==Misc==
* [https://en.wikipedia.org/wiki/Falc%C3%B3n_%28disambiguation%29 Falcón (disambiguation) from Wikipedia]
: [https://en.wikipedia.org/wiki/Falc%C3%B3n Falcón from Wikipedia]
* [https://en.wikipedia.org/wiki/Falcon_%28programming_language%29 Falcon (programming language) from Wikipedia]
* [https://en.wikipedia.org/wiki/Falcon_Northwest Falcon Northwest from Wikipedia]
* [https://en.wikipedia.org/wiki/Falkenberg_%28disambiguation%29 Falkenberg (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Falkenburg Falkenburg (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Valkenburg Valkenburg (disambiguation) from Wikipedia]
=References=
<references />
'''[[Engines|Up one Level]]'''
