From Chessprogramming wiki
Jump to: navigation, search

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 {
  int ext = determineExtension( m, depth, node_type, ...); /* 0 or 1 */
  score = -search(ply + 1, depth + ext - 1, -beta, -alpha);


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.


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


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.


In contemporary, heavily reducing programs former typical extensions are often used in an inverted manner: to flag moves as exempt from reductions.

See also


1980 ...

1990 ...

2000 ...

2010 ...

Forum Posts

1996 ...

2000 ...

2005 ...

2010 ...

2015 ...

External Links