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. 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


Publications

1980 ...

1990 ...

2000 ...

2010 ...


Forum Posts

1996 ...

2000 ...

2005 ...

2010 ...

2015 ...


External Links

Search Extension

Misc


References

  1. ^ Search Extension from Bruce Moreland's Programming Topics
  2. ^ David Levy, David Broughton, Mark Taylor (1989). The SEX Algorithm in Computer Chess. ICCA Journal, Vol. 12, No. 1
  3. ^ "Automated Discovery of Search Extensions" by Mark Watkins, OpenChess - Programming and Technical Discussions, June 22, 2010
  4. ^ Extension Techniques in REBEL (PVS extensions)
  5. ^ @Ed about PV extension by Peter Fendrich, CCC, Jul 19, 2007
  6. ^ How Rebel Plays Chess is also available as pdf reprint

Up one level