25,161
edits
Changes
Created page with "'''Home * Search * Selectivity * Extensions * Mate Threat Extensions''' '''Mate Threat Extensions''' are extensions caused by a mate threat of the o..."
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Extensions]] * Mate Threat Extensions'''
'''Mate Threat Extensions''' are extensions caused by a mate threat of the opponent [[Null Move Pruning#ThreatDetection|detected]] after making a [[Null Move|null move]] in a [[Fail-Soft|fail-soft]] framework, or alternatively with a low shifted, or full window. Some programs detect [[Mate at a Glance|mate in one threats]] statically, i.e. as part or byproduct of [[King Safety|king safety]] in [[Evaluation|evaluation]], to extend near or at the [[Horizon Node|horizon]].
=Threat Extensions=
Mate threat extensions are special cases of the more general ''Threat extensions'' not only restricted to [[Score#MateScores|mate scores]] but losing some [[Material|material]]. According to [[Ernst A. Heinz]], the [[Deep Thought]] team already used fail-low null move scores to detect threats before 1990 <ref>[https://www.stmintz.com/ccc/index.php?id=14327 Re: Deep Search Extension] by [[Ernst A. Heinz]], [[CCC]], January 19, 1998</ref>, descibed by [[Thomas Anantharaman]] in his thesis <ref>[[Thomas Anantharaman]] ('''1990'''). ''A Statistical Study of Selective Min-Max Search in Computer Chess''. Doctoral Thesis. UMI Order Number: AAI9111467, [[Carnegie Mellon University]]</ref> and [[ICGA Journal|ICCA Journal]] paper <ref>[[Thomas Anantharaman]] ('''1991'''). ''Extension Heuristics''. [[ICGA Journal|ICCA Journal]], Vol. 14, No. 2, pp. 47-65</ref>, where he mentioned fall 1986 implementation in [[ChipTest]].
==Deep-Search Extensions==
The term ''Deep-search extension'' was coined by [[Chrilly Donninger]] in his ''Null Move and Deep Search'' paper <ref>[[Chrilly Donninger]] ('''1993'''). ''Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs.'' [[ICGA Journal|ICCA Journal]], [http://people.csail.mit.edu/heinz/iccaj_db/node4.html Vol. 16, No. 3], pp. 137-143</ref>. As pointed out by Ernst A. Heinz, Donninger's idea was to extend the search by one ply if a null move near the horizon does not fail high and the null move score plus a constant margin is below [[Alpha|alpha]], while the [[Evaluation|static evaluation]] indicates a fail high. He further states <ref>[https://www.stmintz.com/ccc/index.php?id=14492 Re: Deep Search Extension] by [[Ernst A. Heinz]], [[CCC]], January 22, 1998</ref>:
Donninger's idea is to extend the search one ply if a null move near the horizon (e.g. at depths <= 3) does not fail high and the null move score plus a constant margin (e.g. minor piece value) is <= alpha while the static evaluation at the node is >= [[Beta|beta]] (i.e. fails high). In order to get meaningful results for the null move score, you need to do it with a full alpha-beta window instead of a zero window (this is a known error in Donninger's original article).
==DarkThought==
Citing ''How DarkThought Plays Chess'' <ref>''[http://people.csail.mit.edu/heinz/dt/node11.html Extension Heuristics]'' from [[Ernst A. Heinz]] ('''1997'''). ''[http://people.csail.mit.edu/heinz/dt/node2.html How DarkThought Plays Chess].'' [[ICGA Journal|ICCA Journal]], Vol. 20, No. 3, pp. 166-176</ref>:
In order to avoid possibly [[Search Explosion|explosive growth]] of the [[Search Tree|search tree]] as caused by excessive deep search extensions in the case of repeated mutual mating threats, [[DarkThought]] restricts them to null moves at depth = 2 in the first "2 * iteration-number" plies on all paths.
=See also=
* [[Botvinnik-Markoff Extension]]
* [[Mate Killers]]
* [[Null Move Pruning#ThreatDetection|Threat Detection]]
=Publications=
* [[Thomas Anantharaman]] ('''1990'''). ''A Statistical Study of Selective Min-Max Search in Computer Chess''. Doctoral Thesis. UMI Order Number: AAI9111467, [[Carnegie Mellon University]]
* [[Thomas Anantharaman]] ('''1991'''). ''Extension Heuristics''. [[ICGA Journal|ICCA Journal]], Vol. 14, No. 2, pp. 47-65
* [[Chrilly Donninger]] ('''1993'''). ''Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs.'' [[ICGA Journal|ICCA Journal]], [http://people.csail.mit.edu/heinz/iccaj_db/node4.html Vol. 16, No. 3], pp. 137-143
* [[Ernst A. Heinz]] ('''1997'''). ''[http://people.csail.mit.edu/heinz/dt/node2.html How DarkThought Plays Chess].'' [[ICGA Journal|ICCA Journal]], Vol. 20, No. 3, pp. 166-176 » [http://people.csail.mit.edu/heinz/dt/node11.html Extension Heuristics]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=14259 Deep Search Extension] by [[Stuart Cracraft]], [[CCC]], January 18, 1998
* [https://www.stmintz.com/ccc/index.php?id=57953 Null move mate extension] by [[James Robertson]], [[CCC]], June 25, 1999
* [https://www.stmintz.com/ccc/index.php?id=318833 The "same threat extension" as effective way to resolve horizon problem] by [[Sergei Markoff]], [[CCC]], October 01, 2003
* [https://www.stmintz.com/ccc/index.php?id=389013 mate threat extension/null move] by Rick Bischoff, [[CCC]], September 25, 2004
: [https://www.stmintz.com/ccc/index.php?id=390268 Re: mate threat extension/null move] by [[Don Beal]], [[CCC]], October 04, 2004 » [[Win at Chess|WAC]] booster
* [http://www.talkchess.com/forum/viewtopic.php?t=24543 null move threat extension] by [[Andrew Short]], [[CCC]], October 23, 2008
=External Links=
* [http://people.csail.mit.edu/heinz/dt/node11.html Extension Heuristics] from [[Ernst A. Heinz]] ('''1997'''). ''[http://people.csail.mit.edu/heinz/dt/node2.html How DarkThought Plays Chess].'' [[ICGA Journal|ICCA Journal]], Vol. 20, No. 3, pp. 166-176
* [http://www.3dkingdoms.com/chess/implementation.htm Programming Details - Slow Chess | Extensions Used, Detailed Description] by [[Jonathan Kreuzer]] » [[Slow Chess]]
=References=
<references />
'''[[Extensions|Up one Level]]'''
'''Mate Threat Extensions''' are extensions caused by a mate threat of the opponent [[Null Move Pruning#ThreatDetection|detected]] after making a [[Null Move|null move]] in a [[Fail-Soft|fail-soft]] framework, or alternatively with a low shifted, or full window. Some programs detect [[Mate at a Glance|mate in one threats]] statically, i.e. as part or byproduct of [[King Safety|king safety]] in [[Evaluation|evaluation]], to extend near or at the [[Horizon Node|horizon]].
=Threat Extensions=
Mate threat extensions are special cases of the more general ''Threat extensions'' not only restricted to [[Score#MateScores|mate scores]] but losing some [[Material|material]]. According to [[Ernst A. Heinz]], the [[Deep Thought]] team already used fail-low null move scores to detect threats before 1990 <ref>[https://www.stmintz.com/ccc/index.php?id=14327 Re: Deep Search Extension] by [[Ernst A. Heinz]], [[CCC]], January 19, 1998</ref>, descibed by [[Thomas Anantharaman]] in his thesis <ref>[[Thomas Anantharaman]] ('''1990'''). ''A Statistical Study of Selective Min-Max Search in Computer Chess''. Doctoral Thesis. UMI Order Number: AAI9111467, [[Carnegie Mellon University]]</ref> and [[ICGA Journal|ICCA Journal]] paper <ref>[[Thomas Anantharaman]] ('''1991'''). ''Extension Heuristics''. [[ICGA Journal|ICCA Journal]], Vol. 14, No. 2, pp. 47-65</ref>, where he mentioned fall 1986 implementation in [[ChipTest]].
==Deep-Search Extensions==
The term ''Deep-search extension'' was coined by [[Chrilly Donninger]] in his ''Null Move and Deep Search'' paper <ref>[[Chrilly Donninger]] ('''1993'''). ''Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs.'' [[ICGA Journal|ICCA Journal]], [http://people.csail.mit.edu/heinz/iccaj_db/node4.html Vol. 16, No. 3], pp. 137-143</ref>. As pointed out by Ernst A. Heinz, Donninger's idea was to extend the search by one ply if a null move near the horizon does not fail high and the null move score plus a constant margin is below [[Alpha|alpha]], while the [[Evaluation|static evaluation]] indicates a fail high. He further states <ref>[https://www.stmintz.com/ccc/index.php?id=14492 Re: Deep Search Extension] by [[Ernst A. Heinz]], [[CCC]], January 22, 1998</ref>:
Donninger's idea is to extend the search one ply if a null move near the horizon (e.g. at depths <= 3) does not fail high and the null move score plus a constant margin (e.g. minor piece value) is <= alpha while the static evaluation at the node is >= [[Beta|beta]] (i.e. fails high). In order to get meaningful results for the null move score, you need to do it with a full alpha-beta window instead of a zero window (this is a known error in Donninger's original article).
==DarkThought==
Citing ''How DarkThought Plays Chess'' <ref>''[http://people.csail.mit.edu/heinz/dt/node11.html Extension Heuristics]'' from [[Ernst A. Heinz]] ('''1997'''). ''[http://people.csail.mit.edu/heinz/dt/node2.html How DarkThought Plays Chess].'' [[ICGA Journal|ICCA Journal]], Vol. 20, No. 3, pp. 166-176</ref>:
In order to avoid possibly [[Search Explosion|explosive growth]] of the [[Search Tree|search tree]] as caused by excessive deep search extensions in the case of repeated mutual mating threats, [[DarkThought]] restricts them to null moves at depth = 2 in the first "2 * iteration-number" plies on all paths.
=See also=
* [[Botvinnik-Markoff Extension]]
* [[Mate Killers]]
* [[Null Move Pruning#ThreatDetection|Threat Detection]]
=Publications=
* [[Thomas Anantharaman]] ('''1990'''). ''A Statistical Study of Selective Min-Max Search in Computer Chess''. Doctoral Thesis. UMI Order Number: AAI9111467, [[Carnegie Mellon University]]
* [[Thomas Anantharaman]] ('''1991'''). ''Extension Heuristics''. [[ICGA Journal|ICCA Journal]], Vol. 14, No. 2, pp. 47-65
* [[Chrilly Donninger]] ('''1993'''). ''Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs.'' [[ICGA Journal|ICCA Journal]], [http://people.csail.mit.edu/heinz/iccaj_db/node4.html Vol. 16, No. 3], pp. 137-143
* [[Ernst A. Heinz]] ('''1997'''). ''[http://people.csail.mit.edu/heinz/dt/node2.html How DarkThought Plays Chess].'' [[ICGA Journal|ICCA Journal]], Vol. 20, No. 3, pp. 166-176 » [http://people.csail.mit.edu/heinz/dt/node11.html Extension Heuristics]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=14259 Deep Search Extension] by [[Stuart Cracraft]], [[CCC]], January 18, 1998
* [https://www.stmintz.com/ccc/index.php?id=57953 Null move mate extension] by [[James Robertson]], [[CCC]], June 25, 1999
* [https://www.stmintz.com/ccc/index.php?id=318833 The "same threat extension" as effective way to resolve horizon problem] by [[Sergei Markoff]], [[CCC]], October 01, 2003
* [https://www.stmintz.com/ccc/index.php?id=389013 mate threat extension/null move] by Rick Bischoff, [[CCC]], September 25, 2004
: [https://www.stmintz.com/ccc/index.php?id=390268 Re: mate threat extension/null move] by [[Don Beal]], [[CCC]], October 04, 2004 » [[Win at Chess|WAC]] booster
* [http://www.talkchess.com/forum/viewtopic.php?t=24543 null move threat extension] by [[Andrew Short]], [[CCC]], October 23, 2008
=External Links=
* [http://people.csail.mit.edu/heinz/dt/node11.html Extension Heuristics] from [[Ernst A. Heinz]] ('''1997'''). ''[http://people.csail.mit.edu/heinz/dt/node2.html How DarkThought Plays Chess].'' [[ICGA Journal|ICCA Journal]], Vol. 20, No. 3, pp. 166-176
* [http://www.3dkingdoms.com/chess/implementation.htm Programming Details - Slow Chess | Extensions Used, Detailed Description] by [[Jonathan Kreuzer]] » [[Slow Chess]]
=References=
<references />
'''[[Extensions|Up one Level]]'''
