Difference between revisions of "Extensions"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
Line 107: | Line 107: | ||
* [https://www.stmintz.com/ccc/index.php?id=208272 Extensions] by [[Benny Antonsson]], [[CCC]], January 18, 2002 | * [https://www.stmintz.com/ccc/index.php?id=208272 Extensions] by [[Benny Antonsson]], [[CCC]], January 18, 2002 | ||
* [https://www.stmintz.com/ccc/index.php?id=247564 I need help with Search/Selective Extension] by [[Scott Farrell]], [[CCC]], August 24, 2002 | * [https://www.stmintz.com/ccc/index.php?id=247564 I need help with Search/Selective Extension] by [[Scott Farrell]], [[CCC]], August 24, 2002 | ||
+ | * [http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=43060 wacnew.epd & single search improvements (extensions)] by [[Stefan Knappe]], [[Computer Chess Forums|Winboard Forum]], June 19, 2003 » [[Matador]], [[Win at Chess]] | ||
* [https://www.stmintz.com/ccc/index.php?id=303131 Problem with extending to maxdepth] by [[Albert Bertilsson]], [[CCC]], June 26, 2003 | * [https://www.stmintz.com/ccc/index.php?id=303131 Problem with extending to maxdepth] by [[Albert Bertilsson]], [[CCC]], June 26, 2003 | ||
* [https://www.stmintz.com/ccc/index.php?id=338851 Evaluation-based Reductions and/or Extensions] by [[Tom Likens]], [[CCC]], December 28, 2003 » [[Reductions]] | * [https://www.stmintz.com/ccc/index.php?id=338851 Evaluation-based Reductions and/or Extensions] by [[Tom Likens]], [[CCC]], December 28, 2003 » [[Reductions]] |
Latest revision as of 21:12, 20 November 2020
Home * Search * Selectivity * Extensions
Many programs extend certain moves to try and find better moves faster, or to resolve tactical "noise" resulting from the horizon effect. To extend a move, its search depth (draft) is incremented by some amount, typically one ply.
Contents
Inside the Loop
Some extensions may be determined inside the move loop before or after making the move, the latter case often delayed to the recursively called search routine by some programs:
for each move m € of all moves { makeMove(m); int ext = determineExtension( m, depth, node_type, ...); /* 0 or 1 */ score = -search(ply + 1, depth + ext - 1, -beta, -alpha); unmakeMove(m); ... }
Classification
Bruce Moreland has classified extensions as either win-seeking, loss-seeking, or neutral [1] :
- Win-seeking extension: If I stop searching now I'll fail low, but I think there might be something good here if I look a little further.
- Loss-seeking extension: If I stop searching now I'll fail high, but I think I'm in trouble.
- Neutral extension: This is a forcing sequence, and if I stop searching now I won't know how it ends.
Types
type | typical class |
---|---|
Botvinnik-Markoff Extension | loss-seeking |
Capture Extensions | neutral |
Check Extensions | neutral |
Mate Threat Extensions | win-seeking |
One Reply Extensions | loss-seeking |
Passed Pawn Extensions | neutral |
PV Extensions | neutral |
Recapture Extensions | neutral |
Singular Extensions | neutral |
Fractional Extensions
This technique involves passing fractional depths to the search function. This is typically implemented by defining one ply to be a number greater than one. Then an extension can be added that does not yet extend the search, but further down the tree may cause an extension when another fractional extension causes the net extension to exceed one ply. Fractional extensions were first described by David Levy's, David Broughton's and Mark Taylor's paper on their SEX Algorithm, in conjunction with "negative" extensions aka. fractional reductions and even LMR [2].
Conditions/Restrictions
Some programs restrict extensions, with either a maximum limit, or via other conditions, such as depth or iteration. Care must be taken so that the search is not extended infinitely (see search explosion). Some programs vary the extension based on the expected node type. For example, in an expected All-node, it might use 1/2 a ply extension for a pawn to the 7th, but a full ply on the PV-node research.
Non-reductions
In contemporary, heavily reducing programs former typical extensions are often used in an inverted manner: to flag moves as exempt from reductions.
See also
Publications
1980 ...
- Hermann Kaindl (1983). Searching to Variable Depth in Computer Chess. Proceedings of IJCAI 83, pp. 760-762. Karlsruhe. pdf
- Thomas Anantharaman, Murray Campbell, Feng-hsiung Hsu (1988). Singular extensions: Adding Selectivity to Brute-Force Searching. AAAI Spring Symposium, Computer Game Playing, pp. 8-13. Also published in ICCA Journal, Vol. 11, No. 4, republished (1990) in Artificial Intelligence, Vol. 43, No. 1, pp. 99-109. ISSN 0004-3702.
- David Levy, David Broughton, Mark Taylor (1989). The SEX Algorithm in Computer Chess. ICCA Journal, Vol. 12, No. 1
1990 ...
- Thomas Anantharaman (1991). Extension Heuristics. ICCA Journal, Vol. 14, No. 2
- Chun Ye (1992). Experiments in Selective Search Extensions. MSc. thesis, Department of Computing Science, University of Alberta, pdf
- Chun Ye, Tony Marsland (1992). Experiments in Forward Pruning with Limited Extensions. ICCA Journal, Vol. 15, No. 2
- Chun Ye, Tony Marsland (1992). Selective Extensions in Game-Tree Search. Heuristic Programming in AI 3
- Don Beal, Martin C. Smith (1995). Quantification of Search-Extension Benefits. ICCA Journal, Vol. 18, No. 4
2000 ...
- Yngvi Björnsson, Tony Marsland (2001). Learning Search Control in Adversary Games. Advances in Computer Games 9, pp. 157-174. pdf
- Yoshimasa Tsuruoka, Daisaku Yokoyama, Takashi Chikayama (2002). Game-Tree Search Algorithm based on Realization Probability. ICGA Journal, Vol. 25, No. 3, pdf, pdf
- David Levy (2002) SOME COMMENTS ON REALIZATION PROBABILITIES AND THE SEX ALGORITHM. ICGA Journal, Vol. 25, No. 3
2010 ...
- Pálmi Skowronski, Yngvi Björnsson, Mark Winands (2010). Automated Discovery of Search-Extension Features. Advances in Computer Games 12, pdf [3]
Forum Posts
1996 ...
- Fractional depth increments by S. Read, rgcc, January 18, 1996
- Crafty V11.3 by Robert Hyatt, rgcc, October 22, 1996 » Crafty
- "Suspicious move" extension by David Eppstein, CCC, November 20, 1997
- Extensions?! by Daniel Homan, CCC, January 13, 1998
- Move Extensions by Roberto Waldteufel, CCC, May 04, 1998
- Extend or not extend in a nullmove tree by Roland Pfister, CCC, June 08, 1998 » Null Move Pruning
- Selective deepening and Hashtables by Werner Inmann, CCC, June 30, 1998
- search extension by Werner Inmann, CCC, July 08, 1998
- King danger extensions by James Robertson, CCC, February 16, 1999
- full-ply search extension leads to crash city! by Dave Gomboc, CCC, March 07, 1999
- Extensions and Futility Pruning by James Robertson, CCC, May 04, 1999 » Futility Pruning
- Q. about Rebel extensions by Rémi Coulom, CCC, May 18, 1999 » Rebel
2000 ...
- What is the use of extensions? by Leonid, CCC, January 09, 2000
- No explosions by Matthias Gemuh, CCC, January 11, 2002 » Search Explosion
- Extensions by Benny Antonsson, CCC, January 18, 2002
- I need help with Search/Selective Extension by Scott Farrell, CCC, August 24, 2002
- wacnew.epd & single search improvements (extensions) by Stefan Knappe, Winboard Forum, June 19, 2003 » Matador, Win at Chess
- Problem with extending to maxdepth by Albert Bertilsson, CCC, June 26, 2003
- Evaluation-based Reductions and/or Extensions by Tom Likens, CCC, December 28, 2003 » Reductions
- extensions + reductions + pruning = confusion by Johan de Koning, CCC, March 24, 2004 (was Shredder 8 secret: search depth?)
2005 ...
- Limiting extensions by David B. Weller, Winboard Forum, February 23, 2005 » GES
- Worthless extension ideas... by mjlef, Winboard Forum, June 06, 2006
- PVS extension up by Ed Schröder, CCC, June 21, 2007
- Delaying Extensions Idea (does anyone do this)? by Mark Lefler, CCC, July 03, 2007
- Threat extension by Harm Geert Muller, CCC, April 15, 2008
- Search extensions at promising trajectories by Reinhard Scharnagl, CCC, May 28, 2008
- extensions by Daniel Shawul, Winboard programming Forum, August 26, 2008
- Extensions, anyone? by Gregory Strong, CCC, February 20, 2009
- Extensions: everywhere or near the tips? by Alvaro Cardoso, CCC, March 15, 2009
- Stupid Extension Problem/Question by John Merlino, CCC, December 23, 2009 » Repetitions
2010 ...
- Problem with exploding tree because of extensions by Oliver Brausch, CCC, January 05, 2010 » Search Explosion
- Restricting extensions to the left most branches? by Michael Sherwin, CCC, February 27, 2010
- "Automated Discovery of Search Extensions" by Mark Watkins, OpenChess - Programming and Technical Discussions, June 22, 2010
- Loss-seeking extension/threatened pieces by Evert Glebbeek, CCC, November 03, 2011
- search extensions by Robert Hyatt, CCC, November 08, 2014 » Singular Extensions
2015 ...
- Adding an Extension Results in Deeper General Search! by Steve Maughan, CCC, May 10, 2015 » Passed Pawn Extensions
- Search extensions by ppyvabw, OpenChess Forum, March 17, 2016
- Extensions in the days of LMR? by Martin Fierz, CCC, March 22, 2016 » LMR
- Depth extensions and effect on transposition queries by Kenneth Jones, CCC, April 16, 2018 » Transposition Table
- Horizon effect and extensions by Vivien Clauzon, CCC, June 25, 2018 » Horizon Effect
- delaying tactics: prune or extend? by Harm Geert Muller, CCC, March 10, 2019 » Selectivity, Tactics
External Links
Search Extension
- Search Extension from Bruce Moreland's Programming Topics
- Computer Chess Programming Theory - Search Extensions by Colin Frayn
- Programming Details - Slow Chess | Extensions Used, Detailed Description by Jonathan Kreuzer » Slow Chess
Misc
- Extension from Wikipedia
- Extension (metaphysics) from Wikipedia
- Extension (music) from Wikipedia
- Jazz chord - Extensions from Wikipedia
References
- ↑ Search Extension from Bruce Moreland's Programming Topics
- ↑ David Levy, David Broughton, Mark Taylor (1989). The SEX Algorithm in Computer Chess. ICCA Journal, Vol. 12, No. 1
- ↑ "Automated Discovery of Search Extensions" by Mark Watkins, OpenChess - Programming and Technical Discussions, June 22, 2010