Mate Threat Extensions
Home * Search * Selectivity * Extensions * Mate Threat Extensions
Mate Threat Extensions are extensions caused by a mate threat of the opponent detected after making a null move in a fail-soft framework, or alternatively with a low shifted, or full window. Some programs detect mate in one threats statically, i.e. as part or byproduct of king safety in evaluation, to extend near or at the horizon.
Contents
Threat Extensions
Mate threat extensions are special cases of the more general Threat extensions not only restricted to mate scores but losing some material. According to Ernst A. Heinz, the Deep Thought team already used fail-low null move scores to detect threats before 1990 [1], descibed by Thomas Anantharaman in his thesis [2] and ICCA Journal paper [3], 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 [4]. 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, while the static evaluation indicates a fail high. He further states [5]:
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 (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 [6]:
In order to avoid possibly explosive growth of the 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
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. ICCA Journal, Vol. 14, No. 2, pp. 47-65
- Chrilly Donninger (1993). Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs. ICCA Journal, Vol. 16, No. 3, pp. 137-143
- Ernst A. Heinz (1997). How DarkThought Plays Chess. ICCA Journal, Vol. 20, No. 3, pp. 166-176 » Extension Heuristics
Forum Posts
- Deep Search Extension by Stuart Cracraft, CCC, January 18, 1998
- Null move mate extension by James Robertson, CCC, June 25, 1999
- The "same threat extension" as effective way to resolve horizon problem by Sergei Markoff, CCC, October 01, 2003
- mate threat extension/null move by Rick Bischoff, CCC, September 25, 2004
- Re: mate threat extension/null move by Don Beal, CCC, October 04, 2004 » WAC booster
- null move threat extension by Andrew Short, CCC, October 23, 2008
External Links
- Extension Heuristics from Ernst A. Heinz (1997). How DarkThought Plays Chess. ICCA Journal, Vol. 20, No. 3, pp. 166-176
- Programming Details - Slow Chess | Extensions Used, Detailed Description by Jonathan Kreuzer » Slow Chess
References
- ↑ Re: Deep Search Extension by Ernst A. Heinz, CCC, January 19, 1998
- ↑ 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. ICCA Journal, Vol. 14, No. 2, pp. 47-65
- ↑ Chrilly Donninger (1993). Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs. ICCA Journal, Vol. 16, No. 3, pp. 137-143
- ↑ Re: Deep Search Extension by Ernst A. Heinz, CCC, January 22, 1998
- ↑ Extension Heuristics from Ernst A. Heinz (1997). How DarkThought Plays Chess. ICCA Journal, Vol. 20, No. 3, pp. 166-176