25,161
edits
Changes
Created page with "'''Home * Search * Selectivity * Reductions * Fail-High Reductions''' '''Fail-high reductions''' (FHR), <br/> as proposed and examined by Rainer F..."
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Reductions]] * Fail-High Reductions'''
'''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.
=Implementation=
FHR is applied at expected [[Node Types#CUT|Fail-high or Cut-Nodes]] [[Recursion|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|zugzwang]].
<pre>
eval, threat := evaluate(...);
if ( eval - threat >= beta && alpha == beta - 1)
reduce depth by one
</pre>
=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 [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]
* [[Rainer Feldmann]], [[Burkhard Monien]] ('''1998'''). ''[http://www2.cs.uni-paderborn.de/fachbereich/AG/monien/PUBLICATIONS/ABSTRACTS/FM_T3E.html Selective Game Tree Search on a Cray T3E]''. [http://www2.cs.uni-paderborn.de/fachbereich/AG/monien/PUBLICATIONS/POSTSCRIPTS/FM_T3E.ps.Z 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. [[Maastricht University|Universiteit Maastricht]], Maastricht, The Netherlands. ISBN 90-621-6416-1. [http://www.cs.ualberta.ca/%7Etony/RecentPapers/nec97w.pdf pdf preprint]
=Forum Posts=
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/548e7af6ccc53474 Fail High reductions] by [[Jon Dart]], [[Computer Chess Forums|rgcc]], October 7, 1996
* [https://www.stmintz.com/ccc/index.php?id=304136 Fail high reductions] by [[Russell Reagan]], [[CCC]], July 01, 2003
* [https://www.stmintz.com/ccc/index.php?id=395592 Fail High Reductions - question about researches] by [[Anastasios Milikas|milix]], [[CCC]], November 11, 2004
=References=
<references />
'''[[Reductions|Up one level]]'''
'''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.
=Implementation=
FHR is applied at expected [[Node Types#CUT|Fail-high or Cut-Nodes]] [[Recursion|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|zugzwang]].
<pre>
eval, threat := evaluate(...);
if ( eval - threat >= beta && alpha == beta - 1)
reduce depth by one
</pre>
=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 [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]
* [[Rainer Feldmann]], [[Burkhard Monien]] ('''1998'''). ''[http://www2.cs.uni-paderborn.de/fachbereich/AG/monien/PUBLICATIONS/ABSTRACTS/FM_T3E.html Selective Game Tree Search on a Cray T3E]''. [http://www2.cs.uni-paderborn.de/fachbereich/AG/monien/PUBLICATIONS/POSTSCRIPTS/FM_T3E.ps.Z 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. [[Maastricht University|Universiteit Maastricht]], Maastricht, The Netherlands. ISBN 90-621-6416-1. [http://www.cs.ualberta.ca/%7Etony/RecentPapers/nec97w.pdf pdf preprint]
=Forum Posts=
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/548e7af6ccc53474 Fail High reductions] by [[Jon Dart]], [[Computer Chess Forums|rgcc]], October 7, 1996
* [https://www.stmintz.com/ccc/index.php?id=304136 Fail high reductions] by [[Russell Reagan]], [[CCC]], July 01, 2003
* [https://www.stmintz.com/ccc/index.php?id=395592 Fail High Reductions - question about researches] by [[Anastasios Milikas|milix]], [[CCC]], November 11, 2004
=References=
<references />
'''[[Reductions|Up one level]]'''
