Difference between revisions of "Extensions"

From Chessprogramming wiki
Jump to: navigation, search
(3 intermediate revisions by the same user not shown)
Line 58: Line 58:
  
 
=Conditions/Restrictions=  
 
=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 Types|node type]]. For example, in an expected [[Node Types#ALL|All-node]], it might use 1/2 a ply extension for a pawn to the 7th, but a full ply on the [[Node Types#PV|PV-node]] research.
+
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|search explosion]]). Some programs vary the extension based on the expected [[Node Types|node type]]. For example, in an expected [[Node Types#ALL|All-node]], it might use 1/2 a ply extension for a pawn to the 7th, but a full ply on the [[Node Types#PV|PV-node]] research.
  
 
==Non-reductions==  
 
==Non-reductions==  
Line 91: Line 91:
 
==1996 ...==  
 
==1996 ...==  
 
* [https://groups.google.com/d/msg/rec.games.chess.computer/1uVIWZFB41k/VUcAUkzyFd0J Fractional depth increments] by S. Read, [[Computer Chess Forums|rgcc]], January 18, 1996
 
* [https://groups.google.com/d/msg/rec.games.chess.computer/1uVIWZFB41k/VUcAUkzyFd0J Fractional depth increments] by S. Read, [[Computer Chess Forums|rgcc]], January 18, 1996
 +
* [https://groups.google.com/d/msg/rec.games.chess.computer/tcjwWnFhXt4/ifkLE7GwfSEJ Crafty V11.3] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], October 22, 1996 » [[Crafty]]
 
* [https://www.stmintz.com/ccc/index.php?id=12201 "Suspicious move" extension] by [[David Eppstein]], [[CCC]], November 20, 1997
 
* [https://www.stmintz.com/ccc/index.php?id=12201 "Suspicious move" extension] by [[David Eppstein]], [[CCC]], November 20, 1997
 +
* [https://www.stmintz.com/ccc/index.php?id=13993 Extensions?!] by [[Daniel Homan]], [[CCC]], January 13, 1998
 
* [https://www.stmintz.com/ccc/index.php?id=17954 Move Extensions] by [[Roberto Waldteufel]], [[CCC]], May 04, 1998
 
* [https://www.stmintz.com/ccc/index.php?id=17954 Move Extensions] by [[Roberto Waldteufel]], [[CCC]], May 04, 1998
 
* [https://www.stmintz.com/ccc/index.php?id=20167 Extend or not extend in a nullmove tree] by [[Roland Pfister]], [[CCC]], June 08, 1998 » [[Null Move Pruning]]
 
* [https://www.stmintz.com/ccc/index.php?id=20167 Extend or not extend in a nullmove tree] by [[Roland Pfister]], [[CCC]], June 08, 1998 » [[Null Move Pruning]]
Line 111: Line 113:
 
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=1754&p=8190 Limiting extensions] by [[David B. Weller]], [[Computer Chess Forums|Winboard Forum]], February 23, 2005 » [[GES]]
 
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=1754&p=8190 Limiting extensions] by [[David B. Weller]], [[Computer Chess Forums|Winboard Forum]], February 23, 2005 » [[GES]]
 
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4952 Worthless extension ideas...] by [[Mark Lefler|mjlef]], [[Computer Chess Forums|Winboard Forum]], June 06, 2006
 
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4952 Worthless extension ideas...] by [[Mark Lefler|mjlef]], [[Computer Chess Forums|Winboard Forum]], June 06, 2006
* [http://www.talkchess.com/forum/viewtopic.php?t=14594 PVS extension up] by [[Ed Schroder|Ed Schröder]], [[CCC]], June 21, 2007 <ref>[http://www.top-5000.nl/authors/rebel/chess840.htm#PVS Extension Techniques in REBEL (PVS extensions)]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=15216 @Ed about PV extension] by [[Peter Fendrich]], [[CCC]], Jul 19, 2007</ref>
+
* [http://www.talkchess.com/forum/viewtopic.php?t=14594 PVS extension up] by [[Ed Schroder|Ed Schröder]], [[CCC]], June 21, 2007  
 
* [http://www.talkchess.com/forum/viewtopic.php?t=14860 Delaying Extensions Idea (does anyone do this)?] by [[Mark Lefler]], [[CCC]], July 03, 2007
 
* [http://www.talkchess.com/forum/viewtopic.php?t=14860 Delaying Extensions Idea (does anyone do this)?] by [[Mark Lefler]], [[CCC]], July 03, 2007
 
* [http://www.talkchess.com/forum/viewtopic.php?t=20680 Threat extension] by [[Harm Geert Muller]], [[CCC]], April 15, 2008
 
* [http://www.talkchess.com/forum/viewtopic.php?t=20680 Threat extension] by [[Harm Geert Muller]], [[CCC]], April 15, 2008
Line 131: Line 133:
 
* [http://www.talkchess.com/forum/viewtopic.php?t=67131 Depth extensions and effect on transposition queries] by [[Kenneth Jones]], [[CCC]], April 16, 2018 » [[Transposition Table]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=67131 Depth extensions and effect on transposition queries] by [[Kenneth Jones]], [[CCC]], April 16, 2018 » [[Transposition Table]]
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=67823 Horizon effect and extensions] by [[Vivien Clauzon]], [[CCC]], June 25, 2018 » [[Horizon Effect]]
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=67823 Horizon effect and extensions] by [[Vivien Clauzon]], [[CCC]], June 25, 2018 » [[Horizon Effect]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70165 delaying tactics: prune or extend?] by [[Harm Geert Muller]], [[CCC]], March 10, 2019 » [[Selectivity]], [[Tactics]]
  
 
=External Links=  
 
=External Links=  
Line 136: Line 139:
 
* [http://web.archive.org/web/20070607151732/www.brucemo.com/compchess/programming/extensions.htm Search Extension] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070607231311/www.brucemo.com/compchess/programming/index.htm Programming Topics]
 
* [http://web.archive.org/web/20070607151732/www.brucemo.com/compchess/programming/extensions.htm Search Extension] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070607231311/www.brucemo.com/compchess/programming/index.htm Programming Topics]
 
* [http://www.frayn.net/beowulf/theory.html#extend Computer Chess Programming Theory - Search Extensions] by [[Colin Frayn]]
 
* [http://www.frayn.net/beowulf/theory.html#extend Computer Chess Programming Theory - Search Extensions] by [[Colin Frayn]]
* [http://www.top-5000.nl/authors/rebel/chess840.htm Programmer Corner ] by [[Ed Schroder|Ed Schröder]] <ref>How Rebel Plays Chess is also available as [http://members.home.nl/matador/Inside%20Rebel.pdf pdf reprint]</ref>
 
: [http://www.top-5000.nl/authors/rebel/chess840.htm#EXTENSIONS Extension Techniques in REBEL]
 
 
* [http://www.3dkingdoms.com/chess/implementation.htm Programming Details - Slow Chess | Extensions Used, Detailed Description] by [[Jonathan Kreuzer]] » [[Slow Chess]]
 
* [http://www.3dkingdoms.com/chess/implementation.htm Programming Details - Slow Chess | Extensions Used, Detailed Description] by [[Jonathan Kreuzer]] » [[Slow Chess]]
 
==Misc==
 
==Misc==

Revision as of 22:29, 29 July 2019

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.

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] :

  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.
  2. Loss-seeking extension: If I stop searching now I'll fail high, but I think I'm in trouble.
  3. 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

Late Move Reductions

Publications

1980 ...

1990 ...

2000 ...

2010 ...

Forum Posts

1996 ...

2000 ...

2005 ...

2010 ...

2015 ...

External Links

Search Extension

Misc

References

Up one level