Difference between revisions of "Fail-High Reductions"
GerdIsenberg (talk | contribs) (Created page with "'''Home * Search * Selectivity * Reductions * Fail-High Reductions''' '''Fail-high reductions''' (FHR), <br/> as proposed and examined by Rainer F...") |
GerdIsenberg (talk | contribs) |
||
Line 2: | Line 2: | ||
'''Fail-high reductions''' (FHR), <br/> | '''Fail-high reductions''' (FHR), <br/> | ||
− | as proposed and examined by [[Rainer Feldmann]] <ref>[[Rainer Feldmann]] ('''1997'''). ''Fail-High Reductions.'' [[Advances in Computer Chess 8]], available as [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=4399933A9FAE32A9C855DED714120C66?doi=10.1.1.51.4897&rep=rep1&type=pdf pdf] from [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.4897 CiteSeerX]</ref>, and implemented in the program [[Zugzwang (Program)|Zugzwang]], are based on the [[Null Move Observation]] (NMO) - similar to the [[Null Move Pruning|Null Move Heuristic]] (NMH). The idea is to search to shallower [[Depth|depth]] at [[Chess Position|positions]] that are seemingly quiet and where the side to move has established a substantial advantage, according to a static [[Evaluation|evaluation]]. Apart from the [[evaluation function]], the heuristic requires an additional function that returns a value indicating threats against the side to move and therefor the quietness of a position. | + | as proposed and examined by [[Rainer Feldmann]] <ref>[[Rainer Feldmann]] ('''1997'''). ''Fail-High Reductions.'' [[Advances in Computer Chess 8]], available as [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=4399933A9FAE32A9C855DED714120C66?doi=10.1.1.51.4897&rep=rep1&type=pdf pdf] from [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.4897 CiteSeerX]</ref>, and implemented in the program [[Zugzwang (Program)|Zugzwang]], are based on the [[Null Move Observation]] (NMO) - similar to the [[Null Move Pruning|Null Move Heuristic]] (NMH). The idea is to search to shallower [[Depth|depth]] at [[Chess Position|positions]] that are seemingly quiet and where the side to move has established a substantial advantage, according to a static [[Evaluation|evaluation]]. Apart from the [[Evaluation Function|evaluation function]], the heuristic requires an additional function that returns a value indicating threats against the side to move and therefor the quietness of a position. |
=Implementation= | =Implementation= |
Latest revision as of 16:09, 16 May 2018
Home * Search * Selectivity * Reductions * Fail-High Reductions
Fail-high reductions (FHR),
as proposed and examined by Rainer Feldmann [1], and implemented in the program Zugzwang, are based on the Null Move Observation (NMO) - similar to the Null Move Heuristic (NMH). The idea is to search to shallower depth at positions that are seemingly quiet and where the side to move has established a substantial advantage, according to a static evaluation. Apart from the evaluation function, the heuristic requires an additional function that returns a value indicating threats against the side to move and therefor the quietness of a position.
Implementation
FHR is applied at expected Fail-high or Cut-Nodes recursively inside a NegaScout-framework. Feldmann's implementation did no re-search with the original depth, if the shallow search didn't confirm the fail high. While NMH relies on a dynamic search, but cuts the whole subtree - FHR uses a static threat detection. FHR is not as vulnerable as NMH in situations, where the NMO fails - namely in zugzwang.
eval, threat := evaluate(...); if ( eval - threat >= beta && alpha == beta - 1) reduce depth by one
See also
- Double Null Move
- Late Move Reductions
- Multi-Cut
- Null Move Pruning
- Null Move Reductions
- ProbCut
- Zugzwang
- Zugzwang (Program)
Publications
- Rainer Feldmann (1997). Fail-High Reductions. Advances in Computer Chess 8, available as pdf from CiteSeerX
- Rainer Feldmann, Burkhard Monien (1998). Selective Game Tree Search on a Cray T3E. ps
- Yngvi Björnsson, Tony Marsland (2000). Selective Depth-First Search Methods. Games in AI Research (eds. Jaap van den Herik and Hiroyuki Iida), pp. 31-45. Universiteit Maastricht, Maastricht, The Netherlands. ISBN 90-621-6416-1. pdf preprint
Forum Posts
- Fail High reductions by Jon Dart, rgcc, October 7, 1996
- Fail high reductions by Russell Reagan, CCC, July 01, 2003
- Fail High Reductions - question about researches by milix, CCC, November 11, 2004
References
- ↑ Rainer Feldmann (1997). Fail-High Reductions. Advances in Computer Chess 8, available as pdf from CiteSeerX