Falcon

From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * Falcon

Falco minor [1]

Falcon,
a private chess engine [2] by Eli David and successor of Eli'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 [3], as well the CCT6 on-line tournament. Book authors were Eros Riccio in 2004, and Erdogan Günes in 2008.

Features

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 [4], and blockade detection in endgames [5].

Genetic Algorithm

Eli 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 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]:

Parameter Value range Bits Learned Unit
Null-move use 0-1 1 1 Boolean
Null Move R 0-7 3 4 plies
Null Move adaptivity 0-1 1 1 Boolean
Null Move adaptivity depth [16] 0-7 3 6 plies
Futility depth 0-3 2 3 plies
Futility threshold depth-1 0-1023 10 106 centipawns
Futility threshold depth-2 0-1023 10 219 centipawns
Futility threshold depth-3 0-1023 10 512 centipawns
Mult-cut use 0-1 1 1 Boolean
Mult-cut R 0-7 3 4 plies
Mult-cut depth [17] 0-7 3 6 plies
Mult-cut M 0-31 5 14 number of moves
Mult-cut C 0-7 3 3 number of moves
Check extension 0-4 3 2 quarter plies
One-reply extension 0-4 3 4 quarter plies
Recapture extension 0-4 3 2 quarter plies
Passed pawn extension, 7th 0-4 3 3 quarter plies
Mate thread extension 0-4 3 1 quarter plies
70 bit

Selected Games

WCCC 2004 round 11, Falcon - Shredder [18] 

[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

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
Pat Metheny, Lyle Mays, Pedro Aznar, Steve Rodby, Paul Wertico, the Ambrosian Singers conducted by John McCarthy (Psalm 121),
and the National Philharmonic Orchestra conducted by Steve Rodby (Flight of the Falcon)

References

  1. ↑ Source John Gerrard Keulemans (1874). Catalogue of the birds in the British Museum. Vol. 1, Plate XII
  2. ↑ Private Engine List from Ron Murawski's Computer-Chess Wiki
  3. ↑ Falcon's ICGA Tournaments
  4. ↑ Omid David, Moshe Koppel, Nathan S. Netanyahu (2010). Genetic Algorithms for Automatic Search Tuning. ICGA Journal, Vol. 33, No. 2
  5. ↑ Omid David, Ariel Felner, Nathan S. Netanyahu (2004). Blockage Detection in Pawn Endgames. ICGA Journal, Vol. 27, No. 3
  6. ↑ Omid David, Nathan S. Netanyahu (2002). Verified null-move pruning. ICGA Journal, Vol. 25, No. 3
  7. ↑ Omid David, Nathan S. Netanyahu (2008). Extended Null-Move Reductions. CG 2008, pdf
  8. ↑ Omid David, Moshe Koppel, Nathan S. Netanyahu (2008). Genetic Algorithms for Mentor-Assisted Evaluation Function Optimization. ACM Genetic and Evolutionary Computation Conference (GECCO '08)
  9. ↑ 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 (GECCO '09)
  10. ↑ Omid David, Moshe Koppel, Nathan S. Netanyahu (2010). Genetic Algorithms for Automatic Search Tuning. ICGA Journal, Vol. 33, No. 2
  11. ↑ Nikolai Krogius, A. Livsic, Bruno Parma, Mark Taimanov (1980). Encyclopedia of Chess Middlegames. Chess Informant
  12. ↑ 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
  13. ↑ Genetic algorithms
  14. ↑ Omid David, Moshe Koppel, Nathan S. Netanyahu (2010). Genetic Algorithms for Automatic Search Tuning. ICGA Journal, Vol. 33, No. 2, 4.2 Generic Algorithms
  15. ↑ Omid David, Moshe Koppel, Nathan S. Netanyahu (2010). Genetic Algorithms for Automatic Search Tuning. ICGA Journal, Vol. 33, No. 2, 5. Experimental Results
  16. ↑ if (adaptivity && depth <= adaptivity_depth) use R-1
  17. ↑ Apply Mult-cut only if depth >= Mult-cut_depth
  18. ↑ Ramat-Gan 2004 - Chess - Round 11 - Game 5 (ICGA Tournaments)
  19. ↑ Jaap van den Herik wint Humies Award 2014 - LIACS - Leiden Institute of Advanced Computer Science
  20. ↑ GECCO 2014
  21. ↑ Falcon Chess by Harm Geert Muller, CCC, July 17, 2008

Up one Level

Retrieved from "https://www.chessprogramming.org/index.php?title=Falcon&oldid=18517"