Extensions

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