Wikispaces : chessprogramming - items matching description

AEL-Pruning

GerdIsenberg — Sat, 22 Jun 2013 08:51:59 GMT

Home * Search * Selectivity * Pruning * AEL-Pruning

AEL-pruning,
a search technique by Ernst A. Heinz that combines Adaptive Null Move Pruning (i.e., Null Move pruning with variable depth reduction R), Extended Futility Pruning (futility pruning at pre-frontier nodes) and limited razoring.

The basic idea is to first check if the depth is pre-pre-frontier, pre-frontier, or frontier, and create a bound based on the razoring margin (likely a queen), extended futility margin (usually around a rook), or futility margin (usually around a minor piece) accordingly. If none applied, only then use Adaptive Null Move Pruning. Now, when you are searching the moves of this position, apply the created bound if it applies. If the bound, plus any immediate material gain by the move is less than or equal to alpha, you may prune this move. Typically, you don't apply extended futility pruning or razoring on nodes you're extending.

Pseudo-Code

In his paper ^[1], Ernst A. Heinz] gives the following C pseudo-code:

int search (int alpha, int beta, int move, node parent, int depth) {
   node current;
   int extend, fmax, fscore, tt_hit;
   /*declare the local variables that require constant initialization*/
   int fprune = 0;
   int fpruned_moves = 0;
   int score = -infinite_val;
   /*execute the opponent's move and determine how to extend the search*/
   make_move(parent, move, &current;
   extend = extensions(move, current, depth);
   depth += extend;
   /*decide about limited razoring at the pre-pre-frontier nodes*/
   fscore = (mat_balance(current) + razor_margin);
   if (!extend && (depth == pre_pre_frontier) && (fscore <= alpha)
       { fprune = 1; score = fmax = fscore; }
   /*decide about extended futility pruning at pre-frontier nodes*/
   fscore = (mat_balance(current) + extd_futil_margin);
   if (!extend && (depth == pre_frontier) && (fscore <= alpha))
       { fprune = 1; score = fmax = fscore; }
   /*decide about selective futility pruning at frontier nodes*/
   fscore = (mat_balance(current) + futil_margin);
   if (!check(move) && (depth == frontier) && (fscore <= alpha))
       { fprune = 1; score = fmax = fscore; }
 
   /* ... */
 
   /*probe the transposition tables at the current node*/
   tt_hit = probe_transposition_tables(current, depth, &tt_ref);
   if (tt_hit) {/* ... */} else {/* ... */}
   /*try the adaptive null-move search with a minimal window around*/
   /*"beta" only if it is allowed, desired, and really promises to cut off*/
   if (!fprune && !check(move) && null_okay(current, move)
         && try_null(alpha, beta, current, depth, move, tt_ref)) {
        /* ... */
        null_score = -search(-beta, -beta + 1, null_move, current,
                        depth - R_adpt(current, depth) - 1);
        if (null_score >= beta) return null_score;
        /* ... */              /*fail-high null-move cutoff*/
   }
 
   /* ... */
   /*now continue as usual but prune all futile moves if "fprune == 1"*/
   for (move = first(current), (move != 0), move = next(current, move))
       if (!fprune || check(move)                    /*recursive PVS part*/
                   || (fmax + mat_gain(move) > alpha)) {/* ... */}
       else fpruned_moves++;
   /*"fpruned_moves > 0" => the search was selective at the current node*/
   /* ... */
}

References

^ Ernst A. Heinz (2000). AEL-Pruning. ICGA Journal, Vol. 23, No. 1, zipped postscript, pdf

What links here?

Page	Date Edited
AEL-Pruning	Jun 22, 2013
Amundsen	Sep 3, 2013
Ernst A. Heinz	Mar 6, 2017
Fischerle	Aug 21, 2017
Futility Pruning	Aug 30, 2017
Napoleon	Jun 25, 2017
Pepito	Nov 27, 2014
Pruning	Jan 1, 2018
Razoring	Oct 5, 2015
RDChess	May 3, 2013
Reverse Futility Pruning	Jun 2, 2017
Selectivity	Jan 12, 2018
Warrior	Feb 23, 2015

Up one Level

Botvinnik-Markoff Extension

GerdIsenberg — Fri, 27 Nov 2015 19:08:39 GMT

Home * Search * Selectivity * Extensions * Botvinnik-Markoff Extension

The Botvinnik-Markoff Extension is an extension proposed by Sergei Markoff ^[1], inspired by Mikhail Botvinnik's work and publications on the program Pioneer, for instance to determine attack/defense targets for further analysis of attack/defense trajectories ^[2]. The extension is based on the threat move detection in null move pruning. If the threat move is the same on two consecutive plies (with one ply in between them to account for the side to move), the threat move is a serious one and the search is extended.

Forum Posts

Markoff - Botvinnik - Kaissa - Hsu - ABC - Berliner by Walter Faxon, CCC, June 09, 2003
The "same threat extension" as effective way to resolve horizon problem by Sergei Markoff, CCC, October 01, 2003, introducing the extension
Test match with the Botvinnik-Markoff extension by Tord Romstad, CCC, October 02, 2003
What is Botvinnik-Markov extension? by Maurizio Monge, CCC, October 26, 2005
Botvinnik Markov revisited by Don Dailey, CCC , Jun 24, 2010

References

^ The "same threat extension" as effective way to resolve horizon problem by Sergei Markoff, CCC, October 01, 2003
^ Mikhail Botvinnik (1982). Decision Making and Computers. Advances in Computer Chess 3

What links here?

Page	Date Edited
Botvinnik-Markoff Extension	Nov 27, 2015
Critter	Jan 25, 2014
Extensions	Apr 19, 2018
Mate Threat Extensions	Apr 14, 2012
Maurizio Monge	Nov 27, 2015
Mikhail Botvinnik	Jul 15, 2017
Null Move	Aug 9, 2017
Null Move Pruning	Dec 2, 2017
Selectivity	Jan 12, 2018
Sergei Markoff	Mar 12, 2018
SmarThink	Feb 2, 2018
Texel	Oct 9, 2017
Threat Move	Sep 10, 2017
Trajectory	Jan 3, 2015

Up one level

Capture Extensions

GerdIsenberg — Fri, 26 Oct 2012 14:12:42 GMT

Home * Search * Selectivity * Extensions * Capture Extensions

Capture Extensions were used early in brute-force chess programs to minimize some horizon effects. Due to the self-restricting nature of captures in Chess (max. 30 pieces may be captured per game), one may consider this a good idea. However, extending every capture was discarded by most programmers, and some constrains or conditions were applied, i.e. to extend only forced recaptures on the same target square.

Hans Berliner suggested to extend only those (re)captures, which restore the material balance at the root. Furthermore, capture extensions are often restricted to PV-nodes, or some programs assign fractional extensions to different kinds of captures, considering SEE, distance of target square to the opponent king, recapturing on the same square, and material balance as mentioned.

A lot of todays programs, more focused on reductions rather than extensions in the Scout part of their PVS, most often don't reduce captures, which makes it a kind of implicit extension relative to reduced late quiet moves. It also seems worth a try to reduce even captures with negative SEE while performing LMR.

However, it seems important to extend captures if a transition to certain late endgames occurs. Ed Schröder for instance extends three plies in Rebel if entering the pawn endgame, and the static, incremental updated score dominated by material is not outside a +-3 pawn window around zero: The extension is very powerful, it will often avoid REBEL entering a lost ending and vice versa ^[1].

Publications

David Levy, David Broughton, Mark Taylor (1989). The SEX Algorithm in Computer Chess. ICCA Journal, Vol. 12, No. 1, pp. 10-21.
Don Beal and Martin C. Smith (1995). Quantification of Search-Extension Benefits. ICCA Journal, Vol. 18, No. 4, pp. 205-218.
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

Forum Posts

Capture/recapture extensions by Andrew Williams, CCC, December 14, 1998
Search extensions at promising trajectories by Reinhard Scharnagl, CCC, May 28, 2008

External Links

References

^ Programmer Corner - How Rebel Plays Chess by Ed Schröder, Extension Techniques: Endgame, pdf reprint

What links here?

Page	Date Edited
Andrew Williams	Jan 7, 2016
Betsabe	Jul 23, 2017
Brainstorm	Jun 24, 2017
Capture Extensions	Oct 26, 2012
Captures	Oct 1, 2017
Counter	Nov 13, 2017
Extensions	Apr 19, 2018
MChess	Feb 26, 2018
Mephisto Lyon	Sep 1, 2017
MLChess	Jan 17, 2017
Pawn Endgame	Oct 11, 2017
Recapture Extensions	Feb 2, 2013
Selectivity	Jan 12, 2018
Smash	May 11, 2016
Wasp	Nov 24, 2017

Up one Level

Delta Pruning

lucasart — Tue, 02 Dec 2014 13:13:47 GMT

Home * Search * Selectivity * Pruning * Delta Pruning

Delta Pruning is a technique similar in concept to futility pruning, only used in the quiescence search. It works as follows: before we make a capture, we test whether the captured piece value plus some safety margin (typically around 200 centipawns) are enough to raise alpha for the current node.

For example, if the side to move is a rook down, it does not bother to test captures of pawns, since they are unlikely to improve matters. Capturing a minor piece, however, might be sufficient, given enough positional compensation. It follows that the safety margin (delta) should be around 200 centipawns, depending on the piece values used by the program.

For safety reasons, delta pruning should be switched off in the late endgame, since otherwise quiescence search would be blind to insufficient material issues and transitions into won endgames made at the expense of some material.

Sample Code

Some processing power may be saved by testing if any move can improve over alpha. Then in truly hopeless nodes we don't do move generation and testing each move against the delta margin. The following code shows how this is done on the CPW-engine (it represents a part of quiescence search responsible for handling a stand pat score):

// get a "stand pat" score
 
int val = eval( alpha, beta );
 
// check if it causes a beta cutoff
 
if( val >= beta )
   return beta;
 
// The next three lines test if alpha can be improved by greatest
// possible matrial swing.
 
int BIG_DELTA = 975; // queen value
if ( isPromotingPawn() ) BIG_DELTA += 775;
 
if ( val < alpha - BIG_DELTA ) {
   return alpha;
}
 
if( alpha < val )
   alpha = val;

Forum Posts

Comments on delta pruning by Bas Hamstra, CCC, October 05, 1999
Delta Pruning by Stuart Cracraft, CCC, August 10, 2004
Inverse delta pruning by Marcel van Kervinck, CCC, May 06, 2011
Qsearch Delta Pruning Rate? by Srdja Matovic, CCC, December 24, 2012

External Links

Fruit from WBEC-Ridderkerk

What links here?

Page	Date Edited
More Links
Beowulf	May 5, 2017
Bison	Sep 29, 2016
Cinnamon	Sep 23, 2017
Counter	Nov 13, 2017
CPW history	Jan 1, 2015
CPW-Engine	Dec 31, 2014
Defenchess	Mar 18, 2018
Delta	May 22, 2016
Delta (GB)	Dec 9, 2012
Delta Pruning	Dec 2, 2014
Donna	Aug 17, 2017
Ethereal	Mar 20, 2018
Exacto	Oct 3, 2015
Fischerle	Aug 21, 2017
Futility Pruning	Aug 30, 2017
Gk	Oct 9, 2017
Glass	May 24, 2017
Gogobello	Jul 30, 2017
Hagrid	Apr 12, 2016
Horizon Node	Sep 13, 2016
Ifrit	Feb 7, 2016
JFresh	Mar 2, 2016
Napoleon	Jun 25, 2017
Nemorino	Dec 21, 2017
Neurosis	Dec 23, 2017
Parity Pruning	Jan 14, 2013
Pawny	Jun 17, 2015
Plisk	Dec 31, 2014
Pruning	Jan 1, 2018
Quiescence Search	Aug 19, 2017
Quiescent Node	Feb 10, 2017
RuyDos	Feb 17, 2018
Selectivity	Jan 12, 2018
Smash	May 11, 2016
Snitch	Apr 7, 2016
Srdja Matovic	Apr 14, 2018
Static Exchange Evaluation	Dec 14, 2017
tomitankChess	Dec 8, 2017
Vajolet	Jan 25, 2018
Witz	Nov 14, 2017

Up one Level

Enhanced Forward Pruning

GerdIsenberg — Tue, 21 Oct 2014 20:33:08 GMT

Home * Search * Selectivity * Pruning * Enhanced Forward Pruning

		Enhanced Forward Pruning, a pruning technique introduced by Mark Winands et al. in 2003 ^[1] , which applies forward pruning like null move pruning and multi-cut ^[2] not only at expected Cut-nodes, but also at expected All-nodes based on considerations and modifications on the PVS framework.
Hannah Höch, Cut with the Dada ... ^[3] ^[4]

Pruning in the Null-Window Search

Pruning in the Null-Window Search

It has become practice to use forward-pruning methods only in the NWS part of the PVS framework. The idea is that it is too risky to prune forward at an expected PV-node, because a possible mistake causes an immediate change of the principal variation.

Cut-Node

If one erroneously prunes forward at some Cut-node and the resulting score is backed up all the way to a PV-node, it obtains a fail-low, due to the odd ply distance to its PV-ancestor, no re-search will be performed. The result of the mistake is that a possible new principal variation is overlooked in this position. Therefore, forward pruning at a Cut-node without further provisions is dangerous. However, by the large savings achieved it has proven worthwhile to implement further provisions making forward pruning at Cut-nodes more safe (and thus acceptable).

All-Node

If one erroneously forward prunes at some All-node and the resulting score is backed up all the way to a PV-node, it obtain a fail-high and a re-search will be performed. The algorithm is then searching for a new principal variation and regards the subsequent nodes as PV-nodes. Because no forward pruning is done at PV-nodes, it is possible to find out whether there exists a new PV or not. In this case the result of the mistake will be that an extra amount of nodes has been searched. In principle, forward pruning at an expected All-node is not dangerous but can trigger unnecessary re-searches.

Four Additions

To prevent that a backed-up value of a forward-pruned All-node causes a cutoff at the PV-node lying above, the forward-pruning mechanism should return a value equal to β in case of a cutoff (which is equal to α+1 at an All-node).
If the window of the PV-node was already closed and the NWS should return a value equal to β (α+1), we still have to do a re-search.
If we do a re-search and the returned value of the NWS equals α+1, we should do a re-search with α as lower bound.
Cut-nodes where a fail-low has occurred with a value equal to α are not stored in the transposition table because their values are uncertain.

Pseudo Code

enum {PV_NODE = 0, CUT_NODE = 1, ALL_NODE = -1};
 
int PVS(node, alpha, beta, depth, node_type)
{
   //Transposition table lookup, omitted
   ...
   if (depth == 0)
      return evaluate(pos);
   if (node_type != PV_NODE)
   {
      //Forward-pruning code, omitted
      ...
      if (forward_pruning condition holds) /* Addition 1 */
         return beta; 
   }
   next = firstSuccessor(node);
   best = -PVS(next, -beta, -alpha, depth-1, -node_type);
   if (best >= beta)
      goto Done;
   next = nextSibling(next);
   while (next != null)
   {
      alpha = max(alpha, best);
      //Null-Window Search Part
      value = -PVS(next, -alpha-1, -alpha, depth-1, (node_type == CUT_NODE)? ALL_NODE : CUT_NODE) );
      //Re-search
      if ( (value > alpha && value < beta) 
      ||   (node_type == PV_NODE && value == beta && beta == alpha+1) ) /* Addition 2 */
      {
         //Value is not a real lower bound
         if (value == alpha+1) /* Addition 3 */
            value = alpha;
         value = -PVS(next, -beta, -value, depth-1, node_type);
      }
      if (value > best)
      {
         best = value;
         if (best >= beta)
            goto Done;
      }
      next = nextSibling(next);
   }
   if (node_type == CUT_NODE && best == alpha)  /* Addition 4 */
      return best;
   Done: //Store in Transposition table, omitted
   ...
}

Publications

Mark Winands, Jaap van den Herik, Jos Uiterwijk, Erik van der Werf (2003, 2005). Enhanced forward pruning. Information Sciences, Vol. 175, No. 4, pdf preprint

Forum Posts

NMP on ALL nodes by Onno Garms, Winboard Forum, April 15, 2007 » Null Move Pruning, All Nodes

References

^ Mark Winands, Jaap van den Herik, Jos Uiterwijk, Erik van der Werf (2003). Enhanced forward pruning. pdf
^ Yngvi Björnsson and Tony Marsland (2001). Multi-cut Alpha-Beta Pruning in Game Tree Search. Theoretical Computer Science, Vol. 252, pp. 177-196. pdf
^ Hannah Höch - Cut with the Dada Kitchen Knife through the Last Weimar Beer-Belly Cultural Epoch in Germany, Collage of pasted papers, 90×144 cm, 1919, National Gallery, Berlin State Museums, Hannah Höch from Wikipedia, Dada from Wikipedia, Weimar culture from Wikipedia
^ le monde de kitchi: Great Women #1: Hannah Höch (German)

What links here?

Page	Date Edited
Enhanced Forward Pruning	Oct 21, 2014
Mark Winands	Sep 19, 2017
Multi-Cut	Jul 4, 2016
NegaScout	Jul 6, 2016
Node Types	Oct 22, 2017
Null Move Pruning	Dec 2, 2017
Principal Variation Search	Oct 22, 2017
ProbCut	Mar 25, 2016
Pruning	Jan 1, 2018
Selectivity	Jan 12, 2018
Uncertainty Cut-Offs	Jul 21, 2015

Up one Level

Extensions

GerdIsenberg — Thu, 19 Apr 2018 19:11:43 GMT

Classification

Types

Fractional Extensions

Conditions/Restrictions

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

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.

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
"Suspicious move" extension by David Eppstein, CCC, November 20, 1997
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
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 ^[4] ^[5]
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

External Links

Search Extension

Misc

Extension from Wikipedia
Extension (metaphysics) from Wikipedia
Extension (music) from Wikipedia
Jazz chord - Extensions from Wikipedia
Alex Hutchings 'Blues Extensions', YouTube Video

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
^ Extension Techniques in REBEL (PVS extensions)
^ @Ed about PV extension by Peter Fendrich, CCC, Jul 19, 2007
^ How Rebel Plays Chess is also available as pdf reprint

Up one level

Fail-High Reductions

GerdIsenberg — Thu, 06 Mar 2014 23:24:15 GMT

Home * Search * Selectivity * Reductions * Fail-High Reductions

Fail-high reductions (FHR), as proposed and examined by Rainer Feldmann ^[1], and implemented in the program Zugzwang, are based on the Null Move Observation (NMO) - similar to the Null Move Heuristic (NMH). The idea is to search to shallower depth at positions that are seemingly quiet and where the side to move has established a substantial advantage, according to a static evaluation. Apart from the evaluation function, the heuristic requires an additional function that returns a value indicating threats against the side to move and therefor the quietness of a position.

FHR is applied at expected Fail-high or Cut-Nodes recursively inside a NegaScout-framework. Feldmann's implementation did no re-search with the original depth, if the shallow search didn't confirm the fail high. While NMH relies on a dynamic search, but cuts the whole subtree - FHR uses a static threat detection. FHR is not as vulnerable as NMH in situations, where the NMO fails - namely in zugzwang.

eval, threat := evaluate(...);
if ( eval - threat >= beta && alpha == beta - 1) reduce depth by one

Publications

Rainer Feldmann (1997). Fail-High Reductions. Advances in Computer Chess 8, available as pdf from CiteSeerX
Rainer Feldmann, Burkhard Monien (1998). Selective Game Tree Search on a Cray T3E. ps
Yngvi Björnsson, Tony Marsland (2000). Selective Depth-First Search Methods. Games in AI Research (eds. Jaap van den Herik and Hiroyuki Iida), pp. 31-45. Universiteit Maastricht, Maastricht, The Netherlands. ISBN 90-621-6416-1. pdf preprint

Forum Posts

Fail High reductions by Jon Dart, rgcc, October 7, 1996
Fail high reductions by Russell Reagan, CCC, July 01, 2003
Fail High Reductions - question about researches by milix, CCC, November 11, 2004

References

^ Rainer Feldmann (1997). Fail-High Reductions. Advances in Computer Chess 8, available as pdf from CiteSeerX

What links here?

Page	Date Edited
AICE	Nov 29, 2017
Anastasios Milikas	Nov 29, 2017
Comet	Jan 8, 2016
Dictionary	Aug 24, 2017
Double Null Move	May 8, 2015
Fail-High	Oct 22, 2017
Fail-High Reductions	Mar 6, 2014
Hagrid	Apr 12, 2016
List (Program)	Jan 7, 2016
Null Move	Aug 9, 2017
Null Move Observation	Dec 30, 2015
Null Move Pruning	Dec 2, 2017
Null Move Reductions	Jun 22, 2015
Rainer Feldmann	Dec 19, 2016
Reductions	Nov 1, 2017
Russell Reagan	Aug 31, 2013
Selectivity	Jan 12, 2018
Snitch	Apr 7, 2016
Zugzwang	Dec 8, 2017
Zugzwang (Program)	Dec 19, 2016

Up one level

Futility Pruning

GerdIsenberg — Wed, 30 Aug 2017 18:51:59 GMT

Home * Search * Selectivity * Pruning * Futility Pruning

		Futility Pruning, in its pure form implemented at the frontier nodes (depth == 1) with one ply left to the horizon. It discards the moves that have no potential of raising alpha, which in turn requires some estimate of a potential value of a move. This is calculated by adding a futility margin (representing the largest conceivable positional gain) to the evaluation of the current position. If this does not exceed alpha then the futility pruning is triggered to skip this move (which further means setting a flag like f_prune = 1 to indicate not all moves were tried).
M. C. Escher, Relativity, 1953 ^[1]

Conditions

Extended Futility Pruning

Move Count Based Pruning

Deep Futility Pruning

Conditions

For tactical stability, even in such a node we ought to search the following moves:

captures (either all or less typically only those that are capable of raising the score above alpha + margin)
moves that give check

Futility pruning is not used when the side to move is in check , or when either alpha or beta are close to the mate value, since it would leave the program blind to certain checkmates. Tord Romstad reported that in his early program Gothmog one more condition was necessary - namely that futility pruning requires checking for the existence of at least one legal move ^[2] ^[3] to avoid returning erroneous stalemate scores. As replied by Omid David: then simply return alpha (to fail low but hard).

Extended Futility Pruning

Ernst A. Heinz advocated using so-called extended futility pruning ^[4]. It means employing similar algorithm at pre frontier nodes at depth == 2, only with the greater margin. If at depth 1 the margin does not exceed the value of a minor piece, at depth 2 it should be more like the value of a rook.

Move Count Based Pruning

A further variation of Extended Futility Pruning combining the ideas of Fruit's History Leaf Pruning and Late Move Reductions is called Move Count Based Pruning or Late Move Pruning (LMP) as implemented in Stockfish ^[5].

Deep Futility Pruning

Deep Futility Pruning was proposed by Harm Geert Muller ^[6]. It is applied at depths of 1<d<=3+R, i.e. with two moves to go:

if ( CurEval <= Alpha - PVal[FirstPiece(Opponent)] - PVal[SecondPiece(Opponent)] - 2*PosMargin )
   prune

Publications

Jonathan Schaeffer (1986). Experiments in Search and Knowledge. Ph.D. Thesis, University of Waterloo. Reprinted as Technical Report TR 86-12, Department of Computing Science, University of Alberta
Chun Ye, Tony Marsland (1992). Experiments in Forward Pruning with Limited Extensions. ICCA Journal, Vol. 15, No. 2
Ernst A. Heinz (1998). Extended Futility Pruning. ICCA Journal, Vol. 21, No. 2.

Forum Posts

1995 ...

futility cut-offs by Alessandro Damiani, rgcc, November 14, 1997
Extended Futility Pruning - anyone tried it? by Tom King, rgcc, August 16, 1998
Extensions and Futility Pruning by James Robertson, CCC, May 04, 1999 » Extensions
Extended futility pruning and hashtables by Gian-Carlo Pascutto, CCC, December 30, 1999 » Transposition Table

2000 ...

Futility Pruning (I think) Question by Brian Richardson, CCC, April 02, 2000
Caution K v KBN and lazy eval or futility by Brian Richardson, CCC, May 14, 2000 » KBNK Endgame, Lazy Evaluation
Something wrong with my futility pruning? by Severi Salminen, CCC, December 05, 2000
About history heuristics, killers and my futil. pruning code by Severi Salminen, CCC, December 06, 2000 » History Heuristic, Killer Heuristic
question about futility pruning and positional evaluation by Bert van den Akker, CCC, December 07, 2000 » Evaluation
Futility Cutoff futile? by Stuart Cracraft, CCC, August 29, 2001
Re: Futility Pruning by Vincent Diepeveen, CCC, December 20, 2002
To Stefan Knappe by Rahman Paidar, Winboard Forum, June 21, 2003 » Stefan Knappe
futility pruning? by Daniel Shawul, CCC, November 09, 2003
Unexpected problem with futility pruning ? by Geoff, CCC, December 29, 2003
Extended futility pruning not working by Cesar Contreras, CCC, August 03, 2004
Futility by Stuart Cracraft, CCC, October 14, 2004
Futility Prune question by Stuart Cracraft, CCC, October 17, 2004
Futility @ 1/Extended Futility @ 2/Limited Razoring @ 3 = % node reduce? by Stuart Cracraft, CCC, October 19, 2004

2005 ...

Does simple futility prune work by Rasjid Chan, Winboard Forum, March 27, 2005
Selective Futlity Condition at Quiescence Nodes by Pradu, Winboard Forum, October 26, 2005
Null move, futility and LMR by Harm Geert Muller, Winboard Forum, September 26, 2006 » Null Move Pruning, LMR
Hash Table handling with LMR/Futility pruning by Pradu, Winboard Forum, October 21, 2006
Extended futility reduction by Michael Sherwin, Winboard Forum, November 18, 2006
How much elo from futility? by Alessandro Scotti, CCC, September 05, 2007
LMR and futility by Pawel Koziol, CCC, October 28, 2007
Draw recognizers, futility... mess by Pawel Koziol, CCC, October 14, 2008
futility pruning - razoring by Don Dailey, CCC, September 16, 2009 » Razoring
Futility pruning, Ext futility pruning and Limited Razoring by Jesper Nielsen, CCC, November 26, 2009

2010 ...

Futility Idea based on total score by Mark Lefler, CCC, February 06, 2010
Confused by futility pruning by Michel Van den Bergh, CCC, March 03, 2010
move count based pruning by Tom King, CCC, September 02, 2010
LMR, Razoring, Futility.... with chess variant with drops? by Justin Madru, CCC, December 30, 2010
Futility Methods by kenny stanley, CCC, January 21, 2011
futility pruning in stockfish by Engin Üstün, CCC, May 25, 2011 » Stockfish
Reverse Futility Pruning by Matthew R. Brades, CCC, December 02, 2011 » Reverse Futility Pruning
How to get futility pruning to work? by Robert Purves, CCC, March 05, 2012
futility pruning, razoring question by Marco Belli, CCC, April 04, 2012 » Razoring
A search enhancement? by Daniel Homan, CCC, April 30, 2012 » Move Count Based Pruning
LMP in PV nodes by Peter Österlund, CCC, December 27, 2014 » PV-Node, Texel

2015 ...

Problem understanding futility pruning by Nicu Ionita, CCC, May 11, 2015
Razoring vs Futility pruning by Shawn Chidester, CCC, August 16, 2015 » Razoring

2016

futility pruning by Folkert van Heusden, CCC, February 20, 2016
Futile attempts at futility pruning by Martin Fierz, CCC, March 27, 2016 » Reverse Futility Pruning
Futility prunning by Daniel Anulliero, CCC, August 11, 2016 » Reverse Futility Pruning
Futility Pruning by David Cimbalista, CCC, October 11, 2016

2017

Futility pruning ? by Mahmoud Uthman, CCC, March 04, 2017 » Reverse Futility Pruning
futile futility pruning attempt by Folkert van Heusden, CCC, March 07, 2017
Futility pruning... by thevinenator, OpenChess Forum, April 07, 2017
increasing futility prunning depth by Alexandru Mosoi, CCC, April 28, 2017

External Links

Pruning

Misc

futility - Wiktionary
futile - Wiktionary
Futility from Wikipedia
The Wreck of the Titan: Or, Futility - Wikipedia
Porcupine Tree - Futile, Zeche Bochum, November 18, 2003, YouTube Video

References

^ Picture gallery "Back in Holland 1941 - 1954" from The Official M.C. Escher Website
^ Serious bug in Gothmog 0.2.6! by Tord Romstad, Winboard Forum, August 04, 2003
^ Re: Unexpected problem with futility pruning? by Tord Romstad, CCC, December 29, 2003
^ Ernst A. Heinz (1998). Extended Futility Pruning. ICCA Journal, Vol. 21, No. 2
^ move count based pruning by Tom King, CCC, September 02, 2010
^ Deep Futility Pruning by Harm Geert Muller

What links here?

Page	Date Edited
Abyss	Aug 5, 2017
AEL-Pruning	Jun 22, 2013
Amy	May 9, 2017
Amyan	Dec 10, 2013
Andscacs	Jan 16, 2018
Arion	Nov 28, 2014
Atlas (ESP)	Jan 28, 2018
Betsabe	Jul 23, 2017
Bison	Sep 29, 2016
BlackBishop	Nov 7, 2014
Carballo	Oct 2, 2016
Cheese	Feb 17, 2018
Cheng	Jul 30, 2017
ChessBrainVB	Jun 24, 2017
ChessV	Jan 21, 2018
Cinnamon	Sep 23, 2017
Coiled	Mar 12, 2017
Counter	Nov 13, 2017
CPW-Engine	Dec 31, 2014
Crafty	Jan 28, 2018
CuckooChess	Jan 17, 2017
Cyclone	Nov 24, 2013
Dan Homan	Oct 19, 2016
Daniel Anulliero	Oct 3, 2017
DarkThought	Jul 3, 2018
DayDreamer	Aug 22, 2016
Defenchess	Mar 18, 2018
Delfi	Jan 7, 2016
Delta Pruning	Dec 2, 2014
Deuterium	Jun 23, 2014
Diablo	May 17, 2016
Dictionary	Aug 24, 2017
Dimitri	Aug 22, 2017
Donna	Aug 17, 2017
Dorky	Oct 10, 2016
DrunkenMaster	Nov 1, 2016
Elephant	Sep 19, 2016
Engine Testing	Feb 1, 2018
Ernst A. Heinz	Mar 6, 2017
ESC	Aug 14, 2013
Ethereal	Mar 20, 2018
Exacto	Oct 3, 2015
EXchess	Jan 21, 2018
Extensions	Apr 19, 2018
Falcon	Sep 2, 2016
Fischerle	Aug 21, 2017
Flux	Jan 12, 2016
Fridolin	Jun 27, 2017
Frontier Nodes	Dec 29, 2013
Futility Pruning	Aug 30, 2017
Galjoen	Mar 19, 2018
Garbochess	Sep 23, 2017
Gaviota	Jan 21, 2018
Ghost	Feb 2, 2018
Gian-Carlo Pascutto	Jan 16, 2018
Gibbon	Dec 23, 2014
Glass	May 24, 2017
Gogobello	Jul 30, 2017
GopherCheck	Feb 3, 2017
Hagrid	Apr 12, 2016
Hakkapeliitta	Apr 26, 2016
History Leaf Pruning	Apr 15, 2013
Ifrit	Feb 7, 2016
ISA	Apr 2, 2018
Jeroen Carolus	Jun 2, 2016
JFresh	Mar 2, 2016
JikChess	Nov 29, 2015
Joker NL	Sep 15, 2017
KBNK Endgame	Nov 26, 2016
KingSlayer	Oct 17, 2016
Koundinya Veluri	Feb 2, 2013
Laser	Dec 27, 2017
Late Move Reduction Test Results	Sep 25, 2017
Late Move Reductions	Sep 25, 2017
Lazy Evaluation	Sep 1, 2017
Little Wing	Oct 26, 2017
Marco Belli	Jan 6, 2018
Mark Lefler	Nov 23, 2017
Martin Fierz	Apr 26, 2018
Marvin	Feb 10, 2018
Matador	Oct 30, 2015
Mate Search	Oct 22, 2016
Matthew R. Brades	Jun 9, 2017
Michel Van den Bergh	Mar 10, 2018
Napoleon	Jun 25, 2017
Natwarlal	Aug 26, 2013
Nebula	Feb 7, 2015
Nemorino	Dec 21, 2017
Nicu Ionita	May 3, 2017
Nirvanachess	Sep 30, 2017
Node Types	Oct 22, 2017
NoraGrace	Nov 23, 2014
Octochess	Aug 15, 2017
Orion	Oct 15, 2017
Ostrich	Dec 28, 2017
Parity Pruning	Jan 14, 2013
Pawny	Jun 17, 2015
Phalanx	May 2, 2016
Plisk	Dec 31, 2014
PostModernist	Jan 7, 2016
Pre Frontier Node	Mar 10, 2012
Prédateur	Nov 11, 2016
ProbCut	Mar 25, 2016
ProChess IT	Sep 30, 2015
Prophet	Sep 30, 2017
Protector	Oct 12, 2017
Pruning	Jan 1, 2018
Purple Haze	Oct 26, 2017
Ramjet	Sep 27, 2017
Rasjid Chan	Nov 26, 2014
RattateChess	Dec 2, 2014
Razoring	Oct 5, 2015
Rebel	Feb 25, 2018
RedQueen	Nov 13, 2017
Requiem	Feb 5, 2018
Reverse Futility Pruning	Jun 2, 2017
Rhetoric	Nov 15, 2017
Rodent	Jan 11, 2018
Sayuri	Oct 1, 2017
Scidlet	May 31, 2014
Search Instability	May 5, 2017
Selectivity	Jan 12, 2018
Senpai	Nov 10, 2017
Severi Salminen	May 7, 2015
Shawn Chidester	Aug 9, 2016
Shield	May 17, 2017
Simplex	Mar 6, 2016
Sinobyl	Jul 3, 2014
Sjeng	Aug 17, 2017
Sloppy	Sep 17, 2016
Smash	May 11, 2016
Snitch	Apr 7, 2016
Spike	Jan 7, 2016
Static Exchange Evaluation	Dec 14, 2017
Stefan Knappe	Jan 22, 2013
Stockfish	Apr 7, 2018
Sunsetter	Jun 1, 2017
Teki	Mar 29, 2018
Texel	Oct 9, 2017
The Baron	Jan 8, 2018
tomitankChess	Dec 8, 2017
Tornado	Dec 14, 2017
Tucano	Dec 16, 2017
Tunguska	Sep 16, 2017
Tytan	Nov 3, 2015
Vajolet	Jan 25, 2018
Volker Böhm	Jan 7, 2016
Wasp	Nov 24, 2017
Waxman	Aug 18, 2014
WildCat	Nov 11, 2016
Wing	Oct 26, 2017
Winter	Jan 23, 2018
WyldChess	Mar 10, 2018
Xiphos	Apr 22, 2018
Xpdnt	Sep 13, 2015
Zeus RU	Jun 6, 2015
Zurichess	Mar 12, 2018

Up one Level

History Leaf Pruning

GerdIsenberg — Mon, 15 Apr 2013 11:44:58 GMT

See also

Forum Posts

What links here?

Home * Search * Selectivity * Pruning * History Leaf Pruning

History leaf pruning is pruning based on history counters. The idea is to prune moves that are <= 0 depth after reductions and are below a given history threshold. History Leaf Pruning showed up as an option in Fruit 05/11/03 by Fabien Letouzey.

// example
if (node_type != NodePV) {
    if (!in_check && played_nb >= 5 && !extended) {
        value = sort->value; // history score
        if (value < HistoryThreshold) {
            new_depth -= 1;
            if (value < LeafThreshold) continue; // History Leaf pruning
            reduced = true;
        }
    }
}

Forum Posts

Re: Possible search improvment by Ryan Benitez, CCC, June 17, 2009 » ProbCut
Can someone explain this? by Michel Van den Bergh, CCC, October 07, 2009 » Toga

What links here?

Page	Date Edited
More Links
Arion	Nov 28, 2014
Bison	Sep 29, 2016
Butterfly Boards	Jan 27, 2015
Cyclone	Nov 24, 2013
Deuterium	Jun 23, 2014
Fruit	Sep 27, 2016
Futility Pruning	Aug 30, 2017
Gaviota	Jan 21, 2018
History Heuristic	Jul 19, 2017
History Leaf Pruning	Apr 15, 2013
Late Move Reduction Test Results	Sep 25, 2017
Late Move Reductions	Sep 25, 2017
Michel Van den Bergh	Mar 10, 2018
ProbCut	Mar 25, 2016
Pruning	Jan 1, 2018
Relative History Heuristic	Jun 8, 2015
Ryan Benitez	May 16, 2015
Sayuri	Oct 1, 2017
Selectivity	Jan 12, 2018
Toga	Dec 28, 2017

Up one Level

Late Move Reductions

GerdIsenberg — Mon, 25 Sep 2017 21:12:31 GMT

Home * Search * Selectivity * Reductions * Late Move Reductions

		Late Move Reductions (LMR), or its version known as History Pruning and History Reductions ^[1] , save search by reducing moves that are ordered closer to the end of likely fail-low nodes. Typically, most schemes search the first few moves (say 3-4) at full depth, then if no move fails high, many of the remaining moves are reduced in search depth. The technique has been used for many years in various forms, but it became very popular in 2005 after Fruit and Glaurung ^[2] used open source implementations based on the History Heuristic. LMR can often reduce the effective branching factor to less than 2, depending on the reduction conditions.
Samuel Bak - Other Rules ^[3]

Common Conditions

Less Common Conditions

Common Conditions

Most programs do not reduce these types of moves:

Tactical moves (captures and promotions)
Moves while in check
Moves which give check
Moves that cause a search extension
Anytime in a PV-Node in a PVS search
Depth < 3 (sometimes depth < 2)

Less Common Conditions

Less common conditions on moves not to reduce:

Passed Pawn Moves
Killer Moves
Moves threatening the King area
Tactically threatening moves
Moves with good past relative history ^[4]
Any Pawn Moves
Allowing reductions of "bad" captures (SEE < 0)
Moves of a threatened piece to safety (often detected via a Null Move search)

Reduction Depth

Classical implementation reduces by one ply only. Yet modern programs, most notably Stockfish, allow reductions of more than one ply and increase them for later moves. Reduction depth changes according to expected node type (being typically smaller in pv nodes), depth and move number. Here some sample formulas can be viewed:

Senpai reduces by one ply for the first 6 moves and by depth / 3 for remaining moves.
Fruit Reloaded uses formula: uint8( sqrt(double(depth-1)) + sqrt(double(moves-1))); for non-PV nodes. In PV-nodes it reduces by 2/3 of this value.

Re-searches

Classical implementation assumes a re-search at full depth if the reduced depth search returns a score above alpha.

Test Results

Some test results related to LMR can be found on

Late Move Reduction Test Results

Publications

David Levy, David Broughton, Mark Taylor (1989). The SEX Algorithm in Computer Chess. ICCA Journal, Vol. 12, No. 1
Daniel S. Abdi (2013). Analysis of pruned minimax trees. pdf » Alpha-Beta, Null Move Pruning

Forum Posts

2004

Forward pruning and some related techniques by Sergei Markoff, CCC, March 02, 2004

2005 ...

Reductions and null move refutations by Tord Romstad, Winboard Forum, April 18, 2005 » Null Move Pruning
What is History Pruning? by David Dahlem, CCC, July 03, 2005
History based pruning question by Alvaro Jose Povoa Cardoso, CCC, August 26, 2005
About history pruning... by Svein Bjørnar Myrvang, CCC, October 26, 2005
What is "history pruning"? by Vladimir Medvedev, Winboard Forum, November 07, 2005

2006

History pruning by Frank Phillips, CCC, February 27, 2006
late move reductions by Robert Hyatt, CCC, March 01, 2006
Re: late move reductions by Alessandro Scotti, CCC, March 01, 2006 » Kiwi
PHR (Peak History Reduction) idea by Daniel Mehrmann, CCC, March 01, 2006 » Homer, Relative History Heuristic
history pruning/ late move pruning by Tom King, Winboard Programming Forum, March 02, 2006
LMR question by Uri Blass, Winboard Programming Forum, July 13, 2006

2007

LMR in micro-Max by Harm Geert Muller, CCC, April 07, 2007 » Micro-Max
Fruit and History Reductions by Ed Schröder, CCC, July 19, 2007 » Fruit
LMR other conditions by Mark Lefler, CCC, July 23, 2007
Improving history tables by Michael Sherwin, CCC, July 25, 2007
LMR: history or not? by Alessandro Scotti, CCC, December 13, 2007 » Hamsters

2008

Extreme late move reductions? by Gary, CCC, March 05, 2008
LMR? by Martin Giepmans, CCC, April 12, 2008 » Anatoli
Adaptative LMR and TT by Fermin Serrano, CCC, December 23, 2008

2009

About LMR & History reductions by Joona Kiiski, CCC, February 24, 2009
LMR by Robert Hyatt, CCC, March 05, 2009
LMR and 'tactically connected' moves by Harm Geert Muller, CCC, March 10, 2009
LMR revisited by Robert Hyatt, CCC, April 01, 2009
LMR and null move selectivity by Don Dailey, CCC, April 20, 2009
LMR by Bas Hamstra, CCC, September 30, 2009
May I Ask What You Think Of This? by Christopher Conkie, CCC, October 20, 2009
Did people try replacing LMR by pruning by Uri Blass, CCC, December 31, 2009

2010 ...

The problem with LMR in suprtactical positions by Oliver Brausch, CCC, January 05, 2010
Researching if LMR-affected search improves Alpha? by John Merlino, CCC, January 22, 2010
Problems with LMR in late endgames by Luca Hemmerich, CCC, March 01, 2010
LMR algorithm by kenny stanley, CCC, March 15, 2010
LMR Conditions by kenny stanley, CCC, March 23, 2010
LMR at root of search tree - worthwhile? by Tom King, CCC, May 21, 2010
EPR, even better than LMR! by Michael Sherwin, CCC, May 27, 2010
Re: "Automated Discovery of Search Extensions" by Ed Schröder, OpenChess Forum, June 26, 2010
lmr at PV nodes? by Tom King, CCC, July 23, 2010
move count based pruning by Tom King, CCC, September 02, 2010
LMR differences in long vs short games by Jacob Børs Lind, CCC, November 08, 2010
fulitiy + lmr; funny results by Volker Böhm, CCC, December 28, 2010

2011

lmr in PV by Larry Kaufman, CCC, January 03, 2011

2012

Should reduction depend on depth? by Larry Kaufman, CCC, January 14, 2012 » Komodo
Possible LMR improvement using AB_FOOL by Ed Schroder, CCC, April 24, 2012
LMR Research by Matthew R. Brades, CCC, July 02, 2012
Adjustable search pruning depending on time control by Jerry Donald, CCC, December 20, 2012 » Time Management

2013

ROC analysis of Late Move Reductions by Gerard van Ewijk, CCC, March 22, 2013 ^[5]
Is LMR Sound by Henk van den Belt, CCC, May 29, 2013
Is LMR safe within NULL move reduction by Henk van den Belt, CCC, May 30, 2013
LMR at CUT nodes can be arbitrarily bad! by Michel Van den Bergh, CCC, June 20, 2013 » Node Types, Python
How much to reduce ? by Henk van den Belt, CCC, October 03, 2013 » R

2014

Null move and LMR by Laurie Tunnicliffe, CCC, March 12, 2014 » Null Move Pruning
LMR & TT interaction by Natale Galioto, CCC, April 29, 2014 » Transposition Table
A question about Stockfish and LMR or other pruning... by Forrest Hoch, CCC, November 20, 2014

2015 ...

About LMR , again :-) by Daniel Anulliero, CCC, March 01, 2015
LMR tuning by Shawn Chidester, CCC, May 11, 2015
Interpretation of LMR by Alexandru Mosoi, CCC, May 29, 2015
What's Your Engine's Maximum LMR Reduction? by Steve Maughan, CCC, June 08, 2015
New "smoothing" issue by Robert Hyatt, CCC, July 20, 2015
On LMR, and statically predicting moves by Matthew Lai, CCC, August 25, 2015
LMR by another name by Steven Edwards, CCC, September 02, 2015 » Spector
Ratio reduction by Steven Edwards, CCC, September 20, 2015 » Symbolic

2016

late move reduction by Folkert van Heusden, CCC, January 21, 2016
Extensions in the days of LMR? by Martin Fierz, CCC, March 22, 2016 » Extensions
LMR problems by Alvaro Cardoso, CCC, May 16, 2016
Reductions by Harm Geert Muller, CCC, May 22, 2016 » R
Disappointing LMR Results by David Cimbalista, CCC, August 04, 2016
Null Move in LMR by Laurie Tunnicliffe, CCC, August 10, 2016 » Null Move Pruning

2017

LMR and PVS by thevinenator, OpenChess Forum, February 10, 2017 » Principal Variation Search
Late move reductions ? by Mahmoud Uthman, CCC, March 22, 2017
Check extension vs LMR by Harm Geert Muller, CCC, April 04, 2017 » Check Extensions
LMR - [for starters] - [Advance] and [Expert] by Ed Schroder, CCC, May 01, 2017
LMR and killer by Harm Geert Muller, CCC, September 14, 2017 » Killer Heuristic
LMR prescription by Evert Glebbeek, CCC, September 24, 2017

External Links

Late Move Reductions

Late Move Reductions from Wikipedia
An Introduction to Late Move Reductions by Tord Romstad (dead link)
Mediocre Chess: [Guide] Late move reduction (LMR) by Jonatan Pettersson, March 26, 2007 » Mediocre
History Reductions in Pro Deo by Ed Schröder » Pro Deo
LMR advanced from Rebel 13 by Ed Schroder ^[6] » Rebel

Misc

Wolfgang Schmid - The Latest Kick, Bix Jazzclub Stuttgart, Summer 2010, YouTube Video

References

^ History Reductions in Pro Deo by Ed Schröder
^ An Introduction to Late Move Reductions by Tord Romstad
^ Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
^ Mark Winands, Erik van der Werf, Jaap van den Herik, and Jos Uiterwijk (2006). The Relative History Heuristic. Computers and Games, Lecture Notes in Computer Science (LNCS 3846) (eds. Jaap van den Herik, Yngvi Björnsson, and Nathan S. Netanyahu), pp. 262-272. pdf
^ Receiver operating characteristic (ROC) from Wikipedia
^ LMR - [for starters] - [Advance] and [Expert] by Ed Schroder, CCC, May 01, 2017

What links here?

Page	Date Edited
Alessandro Scotti	Feb 27, 2014
AliBaba	Aug 17, 2014
Alpha-Beta	Jan 28, 2018
Alvaro Cardoso	Jan 12, 2018
Amoeba	Mar 19, 2018
Amundsen	Sep 3, 2013
Amyan	Dec 10, 2013
Anatoli	Oct 22, 2014
Andscacs	Jan 16, 2018
Artificial Intelligence	Apr 9, 2018
Atlas (ESP)	Jan 28, 2018
Bagatur	Sep 10, 2016
Bas Hamstra	Feb 4, 2018
Betsabe	Jul 23, 2017
Bison	Sep 29, 2016
Bobcat	Jun 27, 2017
Booot	Jan 22, 2018
Brainless	Jun 24, 2017
Branching Factor	Jun 28, 2017
Bright	Oct 25, 2016
Butterfly Boards	Jan 27, 2015
Butterfly Heuristic	May 6, 2016
Capture Extensions	Oct 26, 2012
Carballo	Oct 2, 2016
Check Extensions	Apr 19, 2018
Cheese	Feb 17, 2018
Cheng	Jul 30, 2017
Chepla	May 10, 2013
chess22k	Apr 23, 2018
ChessBrainVB	Jun 24, 2017
ChessV	Jan 21, 2018
Christopher Conkie	May 17, 2016
Cinnamon	Sep 23, 2017
Clarabit	Nov 3, 2011
Clubfoot	Sep 8, 2015
Coiled	Mar 12, 2017
Counter	Nov 13, 2017
CPW history	Jan 1, 2015
Crafty	Jan 28, 2018
CuckooChess	Jan 17, 2017
Cupcake	May 19, 2016
CXG Sphinx	Jun 23, 2017
Cyrus 68K	Jan 7, 2016
DanaSah	Oct 9, 2017
Daniel Anulliero	Oct 3, 2017
Daniel Mehrmann	Dec 13, 2015
Daniel Shawul	Jan 28, 2018
DayDreamer	Aug 22, 2016
Defenchess	Mar 18, 2018
Delfi	Jan 7, 2016
Demolito	Mar 1, 2018
Depth	Feb 25, 2018
Depth Reduction R	Oct 4, 2017
Deuterium	Jun 23, 2014
Dictionary	Aug 24, 2017
Dimitri	Aug 22, 2017
DisasterArea	Mar 27, 2017
DiscoCheck	Jun 23, 2017
Donna	Aug 17, 2017
Dorky	Oct 10, 2016
Dorpsgek	Apr 2, 2018
Encoding Moves	Mar 27, 2016
Engine Testing	Feb 1, 2018
Ethereal	Mar 20, 2018
Eveann	Apr 3, 2017
Evert Glebbeek	Sep 25, 2017
Exacto	Oct 3, 2015
Extensions	Apr 19, 2018
Fail-High Reductions	Mar 6, 2014
FCP	Jun 15, 2013
Fermin Serrano	Nov 27, 2015
Fischerle	Aug 21, 2017
Flux	Jan 12, 2016
Folkert van Heusden	Nov 24, 2017
Frank Phillips	Sep 26, 2016
Fridolin	Jun 27, 2017
Fruit	Sep 27, 2016
Futility Pruning	Aug 30, 2017
Galjoen	Mar 19, 2018
Garbochess	Sep 23, 2017
Garbochess-JS	Sep 23, 2017
Gary Linscott	Jan 16, 2018
Gaviota	Jan 21, 2018
Ghost	Feb 2, 2018
Gibbon	Dec 23, 2014
Ginkgo	Jul 13, 2016
Glass	May 24, 2017
Glaurung	Mar 14, 2017
Go	Jan 24, 2018
Gogobello	Jul 30, 2017
GopherCheck	Feb 3, 2017
Hakkapeliitta	Apr 26, 2016
Hamsters	Apr 11, 2014
HaQiKi D	Jul 26, 2017
Harm Geert Muller	Mar 31, 2018
History Heuristic	Jul 19, 2017
History Leaf Pruning	Apr 15, 2013
Home	Jul 2, 2018
Homer	Dec 23, 2013
Horizon	Mar 17, 2013
iCE	Jan 4, 2016
Ifrit	Feb 7, 2016
ISA	Apr 2, 2018
JFresh	Mar 2, 2016
JikChess	Nov 29, 2015
John Merlino	Feb 26, 2015
Killer Heuristic	Sep 14, 2017
KingSlayer	Oct 17, 2016
Kiwi	Sep 2, 2016
Komodo	Mar 6, 2018
Larry Kaufman	Jan 28, 2018
Laser	Dec 27, 2017
Late Move Reduction Test Results	Sep 25, 2017
Late Move Reductions	Sep 25, 2017
Laurie Tunnicliffe	Jun 13, 2017
Little Wing	Oct 26, 2017
LittleThought	Nov 7, 2016
Lozza	Apr 18, 2018
Luca Hemmerich	Jun 19, 2017
MadChess	Jul 4, 2017
Mark Lefler	Nov 23, 2017
Martin Fierz	Apr 26, 2018
Marvin	Feb 10, 2018
Matthew R. Brades	Jun 9, 2017
Mediocre	Feb 27, 2015
Micro-Max	Aug 7, 2017
Murka	Nov 11, 2016
Napoleon	Jun 25, 2017
Naum	Nov 23, 2017
Nebula	Feb 7, 2015
Nemorino	Dec 21, 2017
Nirvanachess	Sep 30, 2017
Node Types	Oct 22, 2017
NoraGrace	Nov 23, 2014
Null Move Pruning	Dec 2, 2017
Obender	Apr 17, 2016
Octochess	Aug 15, 2017
OliThink	May 19, 2017
Oliver Brausch	May 19, 2017
Orion	Oct 15, 2017
Paladin	Jan 29, 2017
Parity Pruning	Jan 14, 2013
Path-Dependency	Oct 16, 2017
Pawny	Jun 17, 2015
Phalanx	May 2, 2016
Philidor	Jan 7, 2016
Plisk	Dec 31, 2014
Prédateur	Nov 11, 2016
Principal Variation Search	Oct 22, 2017
ProbCut	Mar 25, 2016
Protector	Oct 12, 2017
Pruning	Jan 1, 2018
PV Extensions	May 4, 2013
Python	Jan 31, 2018
RattateChess	Dec 2, 2014
Reductions	Nov 1, 2017
Relative History Heuristic	Jun 8, 2015
Rhetoric	Nov 15, 2017
Robert Hyatt	Dec 25, 2017
Robocide	May 11, 2016
Rodent	Jan 11, 2018
RomiChess	Jan 2, 2018
RuyDos	Feb 17, 2018
Rybka	Mar 27, 2017
Sayuri	Oct 1, 2017
Schooner	Feb 2, 2018
Search Instability	May 5, 2017
Selectivity	Jan 12, 2018
Senpai	Nov 10, 2017
SEX Algorithm	Nov 25, 2014
Shawn Chidester	Aug 9, 2016
Shield	May 17, 2017
Simplex	Mar 6, 2016
Sjaak (Glebbeek)	Oct 4, 2017
Sloppy	Sep 17, 2016
Soldat	Aug 20, 2017
Spark	Oct 19, 2017
Spector	Nov 11, 2016
Spike	Jan 7, 2016
Stockfish	Apr 7, 2018
Symbolic	May 8, 2017
Tactics	Jan 12, 2018
Teki	Mar 29, 2018
Texel	Oct 9, 2017
The Baron	Jan 8, 2018
The Turk (TR)	Apr 1, 2017
Tigran	Aug 16, 2015
Time Management	Mar 20, 2018
Tom King	Aug 19, 2017
tomitankChess	Dec 8, 2017
Tord Romstad	Dec 9, 2017
Tornado	Dec 14, 2017
TRACE	Feb 14, 2013
Transposition Table	Apr 19, 2018
Tucano	Dec 16, 2017
Tunguska	Sep 16, 2017
UCT	Jan 22, 2018
Uncertainty Cut-Offs	Jul 21, 2015
Vadim Demichev	Jul 26, 2013
Vajolet	Jan 25, 2018
Vladimir Medvedev	Jul 22, 2016
Volker Böhm	Jan 7, 2016
Wasp	Nov 24, 2017
WildCat	Nov 11, 2016
Wing	Oct 26, 2017
Winter	Jan 23, 2018
WyldChess	Mar 10, 2018
Xiphos	Apr 22, 2018
Ziggy IS	Sep 6, 2015
Zochova	Nov 9, 2014
Zurichess	Mar 12, 2018

Up one level

Mate Distance Pruning

GerdIsenberg — Fri, 02 Jun 2017 21:28:50 GMT

Home * Search * Selectivity * Pruning * Mate Distance Pruning

If a forced mate has been found, Mate Distance Pruning (MDP) will cut trees and adjust bounds of lines where no shorter mate is possible. Mate Distance Pruning is a safe type of pruning, as it only cuts irrelevant nodes. It will not add much to a programs playing strength as this pruning only comes into effect when a position is already decided, still it helps with analysis and solving "Mate in n" problems.

Mating Value

The prerequisit for Mate Distance Pruning is that decided positions are properly scored. So a position where the opponent is mated is scored SCORE_MATE (a very high value), a position where the victory is one move away is worth less SCORE_MATE - 1, Mate in 2 plies is scored SCORE_MATE - 2 and so on. On the other side, a position where the side to move is mated in n plies is evaluated -SCORE_MATE + n. The difference between the actual value and SCORE_MATE is always the number of plies the mate is away from the root position.

Upper Bound

Assume we are in a winning position. Through another line we have already found a forced mate in n plies. Thus our alpha is SCORE_MATE - n. From this information we can take that should we be searching a line that already is equal to or longer than n, we can impossibly increase alpha even if another mate was found. This means we could safely prune that tree.

Furthermore we can lower the upper bound. If we are n plies away from the root, the opponent can impossibly be evaluated > SCORE_MATE - n. Thus beta can be set to this value should it be higher.

mating_value = SCORE_MATE - RootDistance;
 
if (mating_value < beta) {
   beta = mating_value;
   if (alpha >= mating_value) return mating_value;
}

Lower Bound

Contrary to the pruning if we are in a winning position, scores can also be adjusted and trees pruned if we are in a loosing position.

mating_value = -SCORE_MATE + RootDistance;
 
if (mating_value > alpha) {
   alpha = mating_value;
   if (beta <= mating_value) return mating_value;
}

In Practice

Using the Chess Engine Glass 1.0 the treesize of a search without Mate Distance Pruning is compared to one with this feature enabled.

8/7K/8/8/8/8/R7/7k w - - 0 1

Depth	MDP Disabled (Score / Nodes) ^[1]	MDP Enabled (Score / Nodes)
1	1041 / 3	1041 / 3
2	1041 / 23	1041 / 23
3	1051 / 103	1051 / 103
4	1051 / 551	1051 / 551
5	1055 / 2151	1055 / 2151
6	1051 / 7638	1051 / 7638
7	1055 / 24353	1055 / 24353
8	1065 / 62692	1065 / 62692
9	1065 / 139241	1065 / 139241
10	1085 / 253338	1085 / 253338
11	1085 / 409101	1085 / 409101
12	1105 / 610285	1105 / 610285
13	1105 / 873959	1105 / 873959
14	1105 / 1417047	1105 / 1417047
15	1105 / 1907578	1105 / 1907578
16	M8 / 2846864	M8 / 2547293
17	M8 / 3715208	M8 / 2819164
18	M8 / 4842666	M8 / 3092833
19	M8 / 6181827	M8 / 3368068
20	M8 / 7774698	M8 / 3643489

From this table one can see that the treesize is equal for the first 15 plies, but then the Version with Mate Distance Pruning enabled found the exact mating line about 10% smaller. Furthermore the risk of treesize explosion for further iterations is greatly decreased. In this example the treesize of the Version with this type of Pruning enabled is less than half as big.

Forum Posts

Search questions by Sven Schüle, Winboard Forum, July 17, 2007» Fail-Soft
Discussion about Mate Distance Pruning by Don Dailey, CCC, March 14, 2009
mate distance pruning problems and static null move pruning by Pierre Bokma, CCC, December 04, 2011 » Reverse Futility Pruning

References

^ Nodes until PV is found

What links here?

Page	Date Edited
Amoeba	Mar 19, 2018
Bagatur	Sep 10, 2016
Betsabe	Jul 23, 2017
Bison	Sep 29, 2016
Carballo	Oct 2, 2016
Checkmate	Apr 13, 2018
Cheese	Feb 17, 2018
Cheng	Jul 30, 2017
ChessBrainVB	Jun 24, 2017
Coiled	Mar 12, 2017
Donna	Aug 17, 2017
Fail-Soft	Jun 2, 2017
Floyd	Sep 11, 2016
Flux	Jan 12, 2016
Garbochess-JS	Sep 23, 2017
Gogobello	Jul 30, 2017
GopherCheck	Feb 3, 2017
JFresh	Mar 2, 2016
Matant	Aug 14, 2013
Mate at a Glance	Sep 24, 2014
Mate Distance Pruning	Jun 2, 2017
Nemorino	Dec 21, 2017
Prédateur	Nov 11, 2016
Pruning	Jan 1, 2018
Reverse Futility Pruning	Jun 2, 2017
Robocide	May 11, 2016
Score	Apr 14, 2018
Selectivity	Jan 12, 2018
Simplex	Mar 6, 2016
Sloppy	Sep 17, 2016
Teki	Mar 29, 2018
Vajolet	Jan 25, 2018
WyldChess	Mar 10, 2018
Xpdnt	Sep 13, 2015

Up one level

Multi-Cut

GerdIsenberg — Mon, 04 Jul 2016 13:23:20 GMT

Home * Search * Selectivity * Pruning * Multi-Cut

		Multi-Cut, a speculative pruning mechanism for chessplaying programs created by Yngvi Björnsson ^[1] ^[2]. The basic idea is to perform a reduced search of the first C (i.e. 3) up to M (i.e. 6) moves, to prove an expected Cut-node is not singular, that is multiple (C) moves fail high, and to prune the whole subtree in that case by returning the hard beta bound. Mark Winands' enhanced forward pruning applies Multi-Cut even at expected All-nodes, with slight modifications on a PVS framework ^[3] . In his 2011 B.Sc. thesis Investigation of Multi-Cut Pruning in Game-Tree Search ^[4], Hrafn Eiríksson proposed to apply Multi-cut if a transposition table probe indicates a beta-cutoff without sufficient draft stored.
Katsushika Hokusai - Master Pine Pruner ^[5]

Abstract

from the Workshop Chess and Mathematics, 2008 ^[6] ^[7] :

The alpha-beta algorithm is the most popular method for searching game-trees in adversary board games such as chess. It is much more efficient than a plain brute-force minimax search because it allows a large portion of the game-tree to be pruned, while still backing up the correct game-tree value. However, the number of nodes visited by the algorithm still increases exponentially with increasing search depth. This obviously limits the scope of the search, since game-playing programs must meet external time constraints: often having only a few minutes to make a decision.

To somewhat alleviate this problem so-called speculative-pruning methods are used to cut off less interesting lines of play prematurely, while allowing interesting lines to be explored more deeply.

Here we discuss one such speculative-pruning method called multi-cut, which makes pruning decisions based not only on the risk of pruning off relevant lines of play, but also on the likelihood of such an erroneous pruning decision affecting the move decision at the root of the search tree. The method has been successfully employed by several of the world’s strongest commercial chess program for a number of years.

Pseudo Code

Multi-Cut inside a null window- or zero window search of a fail-hard PVS framework, applied at expected Cut-nodes:

// M is the number of moves to look at when checking for mc-prune.
// C is the number of cutoffs to cause an mc-prune, C < M.
// R is the search depth reduction for mc-prune searches.
 
int zwSearch( int beta, int depth, bool cut) {
   if ( depth <= 0 ) return quiesce( beta-1, beta );
 
   if ( depth >= R && cut ) {
      int c = 0;
      for ( first M moves )
         score = -zwSearch( 1-beta, depth-1-R, !cut);
         if ( score >= beta ) {
            if ( ++c == C )
               return beta; // mc-prune
         }
      }
   }
   for ( all moves ) {
      score = -zwSearch( 1-beta, depth-1, !cut);
      if ( score  >= beta )
         return beta;
   }
   return beta - 1;
}

Publications

Yngvi Björnsson, Tony Marsland (1998). Multi-cut Pruning in Alpha-Beta Search. CG 1998, see also MC2001 for an expanded version.
Yngvi Björnsson, Tony Marsland (2000). Risk Management in Game-tree Pruning. Information Sciences, Vol. 122, No. 1, pdf
Yngvi Björnsson, Tony Marsland (2001). Multi-cut Alpha-Beta Pruning in Game Tree Search. Theoretical Computer Science, Vol. 252, pdf
Yngvi Björnsson (2002). Selective Depth-First Game-Tree Search. Ph.D. thesis, University of Alberta
Mark Winands, Jaap van den Herik, Jos Uiterwijk, Erik van der Werf (2003). Enhanced forward pruning. pdf
Hrafn Eiríksson (2011). Investigation of Multi-Cut Pruning in Game-Tree Search. B.Sc. Thesis, Reykjavík University, pdf

Forum Posts

Mult-cut, SE and ETC by Ricardo Gibert, CCC, August 05, 2010 » Singular Extensions, Enhanced Transposition Cutoff
Re: Some thoughts on QS by Vincent Diepeveen, CCC, July 30, 2012
Multi-cut and fail-soft by Matthew R. Brades, CCC, June 30, 2016 » Fail-Soft

External Links

Björk - Big Time Sensuality, YouTube Video

References

^ Yngvi Björnsson, Tony Marsland (1998). Multi-cut Pruning in Alpha-Beta Search. CG 1998
^ Yngvi Björnsson, Tony Marsland (2001). Multi-cut Alpha-Beta Pruning in Game Tree Search. Theoretical Computer Science, Vol. 252, pdf
^ Mark Winands, Jaap van den Herik, Jos Uiterwijk, Erik van der Werf (2003). Enhanced forward pruning. pdf
^ Hrafn Eiríksson (2011). Investigation of Multi-Cut Pruning in Game-Tree Search. B.Sc. Thesis, Reykjavík University, pdf
^ Katsushika Hokusai - Master Pine Pruner cropped, ca. 1802, Series: Famous Views of the Eastern Capital, woodcuts, Current location: Los Angeles County Museum of Art, Category:Katsushika Hokusai, Wikimedia Commons
^ CHESS AND MATHEMATICS - Workshop Dresden, 21st - 23rd November 2008
^ Workshop Chess and Mathematics (pdf) agenda and abstracts

What links here?

Page	Date Edited
Amateur	Feb 25, 2012
Czolgista	Apr 20, 2013
Depth	Feb 25, 2018
Depth Reduction R	Oct 4, 2017
Enhanced Forward Pruning	Oct 21, 2014
Enhanced Transposition Cutoff	May 19, 2017
Fail-High Reductions	Mar 6, 2014
Fail-Soft	Jun 2, 2017
Falcon	Sep 2, 2016
Hrafn Eiríksson	Jan 8, 2014
Mark Winands	Sep 19, 2017
Mathematician	Apr 9, 2018
Matthew R. Brades	Jun 9, 2017
Multi-Cut	Jul 4, 2016
Null Move Pruning	Dec 2, 2017
Null Window	Nov 8, 2016
ProbCut	Mar 25, 2016
Pruning	Jan 1, 2018
Reductions	Nov 1, 2017
Selectivity	Jan 12, 2018
Singular Extensions	Jan 9, 2018
Tactics	Jan 12, 2018
The Turk	Apr 1, 2017
Uncertainty Cut-Offs	Jul 21, 2015
Workshop Chess and Mathematics	Mar 5, 2015
Yngvi Björnsson	Jun 26, 2017
Ziggy IS	Sep 6, 2015

Up one Level

Null Move Pruning

GerdIsenberg — Sat, 02 Dec 2017 22:13:31 GMT

Home * Search * Selectivity * Pruning * Null Move Pruning

		Null Move Pruning, also called Null Move Heuristic (NMH), is a method based on the Null Move Observation to reduce the search space by trying a "null" or "passing" move, then seeing if the score of the subtree search is still high enough to cause a beta cutoff. Nodes are saved by reducing the depth of the subtree under the null move. The value of this depth reduction is known as R.
Samuel Bak - Signals ^[1]

History

Mater II

In computer chess, Null Move was already used in threatening mate in one detection, as elaborated by George Baylor and Herbert Simon in A chess mating combinations program, 1966, the description of Mater II ^[2] .

Routine G17 asks if a proposed move threatens mate in one move. It determines the answer by assuming Black does nothing on his turn, that is, by playing a "No Move" and then seeing if White can enforce an immediate checkmate.

Kaissa

Null Move pruning was already used in Kaissa, as described by their authors 1975 in Some Methods of Controlling the Tree Search in Chess Programs ^[3] , at the end of chapter 2:

2. The Order of Move Considerations:
A less trivial idea was that sometimes an extension of the game tree by introducing of dummy move can lead to a reduction of the search tree. In positions with material advantage (with respect to limits) it was permitted to try a so-called "blank" move in which ones own pieces are not moved. Certainly in positions with "Zugzwang" (the side to move must weaken his position) this may lead to errors.

However, the standard of the program's play is still such that such errors do not essentially lower it. (We plan to develop in the future a procedure for recognizing "Zugzwang" positions, and to forbid a blank move in them.) The reduction of search takes place in this case, because the blank move proves to be a closing one and furthermore does not generate complex forcing variations.

Beal's NMQS

Null move was further examined by Don Beal, as already elaborated in his Advances in Computer Chess 5 lecture. He proposed a so called Null Move Quiescence Search (NMQS) as a selective layer between a regular full width search and quiescence search, later dubbed Generalized Quiescence Search ^[4]. The full width search was called with two depth parameters, both considered inside the transposition table, full-depth and q-depth. Full-depth was recursively decremented as usual, but instead of calling quiescence at the full-depth horizon, NMQS with q-depth was called - q-depth recursively decremented in this layer as well. As long as q-depth is greater than zero, the hash move, if any, is searched first regularly. Next, NMQS calls quiescence for the other side to move, to check for a possible null move beta-cutoff, before proceeding the remaining moves in usual manner. As pointed out by Chun Ye in his 1992 thesis ^[5], NMQS permits more flexible iterative deepening concerning full-depth in an outer and q-depth in an inner loop.

Schaeffer

In his 1987 ICCA Journal paper Speculative Computing, Jonathan Schaeffer mentioned The Null-Move Algorithm or Don Beal's null-move, and used it non-recursively up to once per search path in his tactical scout solver Minix (Mini-Phoenix), which up and then gave the parallel running Phoenix, which was a less deep searcher than Minix, some tactical hints ^[6].

Goetsch and Campbell

Gordon Goetsch and Murray Campbell published the results of some experiments with Null move pruning in 1988 and 1990 ^[7] ^[8], already considering recursive NMP with depth reduction of 1, also mentioned in Chun Ye's 1992 thesis with source code as implemented inside the Chinese Chess program Abyss ^[9] .

Morsch and Donninger

Null move pruning was used recursively to possibly occur multiple times inside a path of the search by Frans Morsch ^[10] inside his chess engines Quest and Fritz. Frans exchanged his ideas with Chrilly Donninger, who popularized null move by his Null Move and Deep Search paper in the ICCA Journal 1993 ^[11] .

Schemes

Most typical engines use recursive null move with an R value of 2 or 3. Recursive null move pruning is simply allowing more than one null move in one branch of the search. Fruit uses a depth reduction factor R=3, with no null move pruning when down to king and pawns for the side to move, or when in check. The default for Fruit is to try a null search if the static evaluation is greater than beta, or the depth less than four. Newer versions of Fruit as well as Toga default to always doing a null search, as long as there is at least one piece of value greater than a pawn for that side.

Adaptive Null Move Pruning

Ernst A. Heinz proposed refinements with Adaptive Null Move Pruning ^[12] . Some programs vary R with depth, or based on evaluation features, such as being in or near the endgame.

Restrictions on use

Obviously, the null move cannot be used when the side to move is in check, because that would result in an illegal position. But there are more less obvious restrictions on using null move safely. The theoretical basis of null move pruning, as coined by Christophe Théron, is the null move observation. The null move observation is the fact that in chess, in almost every position, the side to move will have a move to play that is better than doing nothing.

There are a few situations in which this assumption does not hold. The null move will produce very bad results in zugzwang positions - positions in which not moving would be the best move, if it were legal. For this reason, some conditions must be used for when the null move is tried in search. Most engines do not try the null move in the endgame, because that is where zugzwang positions are most likely to occur, because there are fewer pieces to move. It is debatable whether a programmer should allow the null move search descend directly to the quiescence search. Most probably it is worthwile only with more tactically aware versions of quiescence.

Some other ways to combat the negative effect of the null move observation are listed here:

Zugzwang Verification

Concerning null move failures in zugzwang ^[13] , there were proposals by Stefan Plenkner 1995, ^[14] ^[15] and later the Verified Null-Move Pruning approach by Omid David and Nathan S. Netanyahu ^[16] . Recently Robert Hyatt tested Verified Null-Move Pruning extensively with a lot of variations and depth reductions for the verified search, and concluded it does not help at all in Crafty ^[17] similar with extended null-move reductions ^[18] ^[19] . However, Marco Costalba states that verification search has almost nothing to do with zugzwang ^[20] .

Double Null Move

Widely discussed in computer chess forums was the Double Null Move idea by Vincent Diepeveen to perform two consecutive null moves to detect zugzwang ^[21] .

Variable NM Bound

The idea to permit a null move cutoff not only if the null move search returns a value greater than or equal to beta, but also if the value is slightly less - that is using a bound of beta minus some tempo bonus, was already proposed by Gordon Goetsch and Murray Campbell in 1988 as future research idea ^[22] . Yngvi Björnsson and Tony Marsland substantiated the idea as implemeted in The Turk, where the number of potentially good alternative moves (numPGAM) per side in the path from the root to the current node as estimated by positive scores of generated moves from the history heuristic, was used to determine a tempo bonus of 10 or 20 centipawns - the higher numPGAM, the lower the probability that an erroneous forward pruning decision will propagate up the tree ^[23] .

if ( nullMoveAllowed &&  ...) {
   int bound = beta;
   if ( inNullMoveSearch == 0 ) {
      tempo = 10*(numPGAM > 0) + 10* numPGAM > 15);
      bound -= tempo; // variable bound
   }
   makeNullMove(); ++inNullMoveSearch;
   score = -zwSearch(1-bound, depth-R-1)
   unmakeNullMove(); --inNullMoveSearch;
   if ( score >= bound ) {
      return beta; // null move pruning
   }
}

For zwSearch, see Zero Window Search inside the Principal Variation Search.

Threat Detection

Mate Threats

As suggested in Donninger's paper, concerning the deep search, null move is not only about pruning, but also about detecting threat moves by the opponent to improve further move ordering and to possibly trigger mate threat extensions ^[24] ^[25] ^[26] ^[27] . However, some kind of fail-soft framework is necessary to recognize "I get mated, if I do nothing", otherwise the hard bound of a null window null-move search around beta will limit the upper bound to beta-1 ^[28] . Another, possibly too expensive solution with a fail-hard framework, is to play a bit with the search window, if the null move doesn't fail high:

if ( nullMoveAllowed && depth >= X && ...) {
   makeNullMove()
   score = -zwSearch(1-beta, depth-R-1) // -AlphaBeta (0-beta, 1-beta, depth-R-1)
   if (score >= beta ) {
      // fail high on null move
      unmakeNullMove();
      return beta; // null move pruning
   } else {
      if ( zwSearch( VALUE_MATE/2, depth-R-1) > VALUE_MATE/2 )
         extend; // mate threat extension inside a fail hard framework
      unmakeNullMove();
   }
}

Botvinnik-Markoff Extension

Null move is also the base of the Botvinnik-Markoff Extension, as proposed by Sergei Markoff - as a tribute to the computer chess pioneer and former World Chess Champion Mikhail Botvinnik, who addressed related issues in his publications ^[29] .

Influence on Move Ordering

Most of the time, null move is refuted by a capture. Therefore it makes sense to extract a move that refuted null move from the transposition table, record the target square of such a move, to give a move ordering boost for escaping from that square. Also, there is a strong conjecture that in programs using history move ordering, even a failed null move search helps by filling the history tables faster.

Test Results

Null Move Pruning Test Results - various experimental test results of null move pruning
Null Move Test-Positions, where Null Move may fail due to zugzwang

Publications

1966

George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences, reprinted 1988 in Computer Chess Compendium

1975

Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (1975). Some Methods of Controlling the Tree Search in Chess Programs. Artificial Intelligence, Vol. 6, No. 4, pp. 361-371. ISSN 0004-3702. Reprinted (1988) in Computer Chess Compendium

1980 ...

Gordon Goetsch, Murray Campbell (1988). Experimenting with the Null Move Heuristic in Chess. AAAI Spring Symposium Proceedings, pp. 14-18.
Don Beal (1989). Experiments with the Null Move. Advances in Computer Chess 5, a revised version is published (1990) under the title A Generalized Quiescence Search Algorithm. Artificial Intelligence, Vol. 43, No. 1, pp. 85-98. ISSN 0004-3702, edited version in (1999). The Nature of MINIMAX Search. Ph.D. thesis, IKAT, ISBN 90-62-16-6348. Chapter 10, pp. 101-116

1990 ...

Don Beal (1990). A Generalized Quiescence Search Algorithm. Artificial Intelligence, Vol. 43, No. 1, pp. 85-98. ISSN 0004-3702
Gordon Goetsch, Murray Campbell (1990). Experiments with the Null-Move Heuristic. Computers, Chess, and Cognition, pp. 159-168
Chun Ye (1992). Experiments in Selective Search Extensions. M.Sc. thesis, Department of Computing Science, University of Alberta, pdf
Chrilly Donninger (1993). Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs. ICCA Journal, Vol. 16, No. 3
Stefan Plenkner (1995). A Null-Move Technique Impervious to Zugzwang. ICCA Journal, Vol. 18, No. 2
Ernst A. Heinz. (1999). Adaptive null-move pruning. ICCA Journal, Vol. 22, No. 3, ps

2000 ...

Yngvi Björnsson, Tony Marsland (2000). Selective Depth-First Search Methods. in Jaap van den Herik, Hiroyuki Iida (eds.) (2000). Games in AI Research. Universiteit Maastricht, pdf preprint
Omid David, Nathan S. Netanyahu (2002). Verified null-move pruning. ICGA Journal, Vol. 25 No. 3 ^[30] ^[31]
Don Beal (2006). Review of a nullmove-quiescence search mechanism from 1986. (Draft) ^[32]
Omid David, Nathan S. Netanyahu (2008). Extended Null-Move Reductions. CG 2008, pdf
Daniel S. Abdi (2013). Analysis of pruned minimax trees. pdf » Alpha-Beta, Late Move Reductions

Forum Posts

1995 ...

Null Move heuristic by Valavan Manohararajah, rec.games.chess, July 28, 1995

1997

Null move depth reductions by Tom King, rgcc, February 02, 1997 » Depth Reduction R
Null move? by MLC, rgcc, October 07, 1997
Searching correctly with the Nullmove ==> no zugzwang problems anymore by Vincent Diepeveen, rgcc, October 23, 1997

1998

During Null Move search by Peter Fendrich, CCC, June 02, 1998
Extend or not extend in a nullmove tree by Roland Pfister, CCC, June 08, 1998 » Extensions
Zero-width Window Null Move Search by Dezhi Zhao, CCC, June 15, 1998 » Null Window
search extension by Werner Inmann, CCC, July 08, 1998
Null move reductions by Roberto Waldteufel, CCC, October 04, 1998

1999

Singular Extensions, Nullmove deepsearch by Frank Schneider, CCC, February 16, 1999 » Singular Extensions
NULL MOVE by Sylvain Lacombe, CCC, February 24, 1999
To skin a cat (was Re: NULL MOVE) by Don Dailey, CCC, February 24, 1999
Null move around (beta-1, beta) by Tom King, rgcc, March 05, 1999
Null move mate extension by James Robertson, CCC, June 25, 1999

2000 ...

Pseudo C code for double nullmove + PVS by Vincent Diepeveen, CCC, August 06, 2000
is this nullmove? problems in pulsar algorithm by Mike Adams, CCC, September 20, 2000 » Pulsar

2001

Can nullmoves behave like this? by Severi Salminen, CCC, January 08, 2001
Nullmove: when to avoid it? by Leen Ammeraal, CCC, February 28, 2001
An idea for all you chess programmers. by Paul, Winboard Forum, March 16, 2001
Double Nullmove by David Rasmussen, CCC, March 30, 2001
Double Null move? by Steve Maughan, CCC, July 13, 2001
Null move R=2 vs Null move R=2/3 by Tom King, CCC, August 09, 2001 » Depth Reduction R

2002

Crafty-IsiChess,CCT4,r11 ==> A move to avoid? by José Antônio Fabiano Mendes, CCC, January 29, 2002
Double Nullmove by Andreas Herrmann, CCC, April 25, 2002
Null-Move: Difference between R = 2 and R = 3 in action by Omid David, CCC, July 11, 2002
Verified Null-Move Pruning, ICGA 25(3) by Omid David, CCC, November 20, 2002
new thoughts on verified null move by Scott Farrell, CCC, November 23, 2002

2003

An interesting forward pruning experiment - with pseudo description by Vincent Diepeveen, rgcc, February 08, 2003
The "same threat extension" as effective way to resolve horizon problem by Sergei Markoff, CCC, October 01, 2003 » Botvinnik-Markoff Extension
a question to Tord about detecting threats in null move by Uri Blass, CCC, October 03, 2003

2004

Re: not using nullmove? by Tord Romstad, CCC, February 13, 2004
mtd(f) and null move by Peter Alloysius, CCC, March 11, 2004 » MTD(f)
double null move help by Daniel Shawul, CCC, July 04, 2004
An MTD(f) question about NULL MOVE searching by Dann Corbit, CCC, July 16, 2004 » MTD(f)
null move question(Fruit) by Jan K., CCC, July 22, 2004
mate threat extension/null move by Rick Bischoff, CCC, September 25, 2004

2005 ...

recusive null move in iterative search by Daniel Shawul, Winboard Forum, March 25, 2005 » Iterative Search
Reductions and null move refutations by Tord Romstad, Winboard Forum, April 18, 2005 » Reductions, Late Move Reductions
depthnull by Pedro Castro, Winboard Programming Forum, July 04, 2005

2006

Verified null-move pruning by Tom King, Winboard Programming Forum, March 09, 2006
Simple NULL move enhancement, checks in qsearch by Mark Lefler, Winboard Programming Forum, April 14, 2006

2007

NMP on ALL nodes by Onno Garms, Winboard Programming Forum, April 15, 2007 » All Nodes
Re: Search or Evaluation? by Mark Uniacke, Hiarcs Forum, October 14, 2007
Null Move by Stuart Cracraft, CCC, November 23, 2007
fractal null move by Pawel Koziol, CCC, November 28, 2007

2008

null move threat extension by Andrew Short, CCC, October 23, 2008

2009

Null move in quiescence search idea from Don Beal, 1986 by Eelco de Groot, CCC, Aug 17, 2009 » Quiescence Search, Don Beal
verified null move by Robert Hyatt, CCC, June 21, 2009
Null-moves and zugzwang by Luca Hemmerich, CCC, September 25, 2009 » Zugzwang

2010 ...

Using Heinz in 2010 is not optimal by Milos Stanisavljevic, CCC, January 01, 2010
Null-move pruning and the hash table by Robert Purves, CCC, March 28, 2010 » Transposition Table
nullmove and repetitive draw detection by Edward Yu, CCC, June 20, 2010 » Repetitions
Stockfish null move pre-condition by Rein Halbersma, CCC, July 22, 2010 » Stockfish
Extended Null-Move Reductions by Alvaro Cardoso, CCC, August 20, 2010

2011

Less null move pruning by trans map by Onno Garms, CCC, March 13, 2011 » Onno
Null Move Pruning by Alex Farley, CCC, April 03, 2011
Null move alternative in endgames by Aleks Peshkov, CCC, November 16, 2011

2012

TT avoid nullmove flag by Matthew R. Brades, CCC, August 02, 2012 » Transposition Table
Nullmove vs classic selective search by Ed Schröder, CCC, August 04, 2012 ^[33]

2013

Null Move Fail by CDaley11, OpenChess Forum, January 10, 2013
Two questions by Jerry Donald, CCC, February 11, 2013
nullmove verification vs avoid null by Martin Sedlak, CCC, September 14, 2013
Null move, razoring and mate threats by Jon Dart, CCC, October 28, 2013 » Razoring
Is SF DD greater efficiency would be null move pruning? by Jonathan Lee, CCC, December 22, 2013 » Stockfish

2014

fixing the null move search "bug" by Uri Blass, CCC, February 01, 2014 » Stockfish
Disabling Null Move Pruning in Stockfish by Louis Zulli, CCC, February 15, 2014 » Stockfish
Null move and LMR by Laurie Tunnicliffe, CCC, March 12, 2014 » Late Move Reductions
Null move pruning on PV nodes by Eric Oldre, CCC, July 22, 2014 » PV-Nodes

2015 ...

Why not two consecutive null moves ? by Henk van den Belt, CCC, May 07, 2015
thoughts on null-move reduction by Youri Matiounine, CCC, June 14, 2015 » Null Move Reductions
Null move: minimum depth by Henk van den Belt, CCC, September 14, 2015
Null Move in Quiescent search by Laurie Tunnicliffe, CCC, December 09, 2015 » Quiescence Search, Search Pathology

2016

When to do null move by J. Wesley Cleveland, CCC, June 05, 2016
Calculating R value for Null Move by Andrew Grant, CCC, June 23, 2016 » Depth Reduction R
Null Move recommendations by kickstone, OpenChess Forum, July 29, 2016
Null Move in LMR by Laurie Tunnicliffe, CCC, August 10, 2016 » Late Move Reductions
Nullmove bugs by Matthew R. Brades, CCC, August 28, 2016

2017

What is wrong with doing Nulls & ttcuts in a pv node ? by Mahmoud Uthman, CCC, January 21, 2017 » PV-Nodes, Transposition Table
NULL Move code question by thevinenator, OpenChess Forum, January 27, 2017 » CPW-Engine_search
null move by Folkert van Heusden, CCC, April 14, 2017
tt move vs null move by Erin Dame, CCC, May 27, 2017 » Hash Move, Null Move
End game and Null move by Laurie Tunnicliffe, CCC, June 12, 2017
Fifty move counter and Null move by Tamás Kuzmics, CCC, August 09, 2017 » Fifty-move Rule, Halfmove Clock
Rethinking r in null move by Michael Sherwin, CCC, August 18, 2017 » Depth Reduction R
Question on Null Move Pruning by Jason Fernandez, CCC, August 29, 2017
Threat detection by Harm Geert Muller, CCC, September 09, 2017 » Threat Detection, Threat Move

External Links

Selective Search Techniques in REBEL (null-move) from Programmer Corner by Ed Schröder ^[34] ^[35] » Rebel
A presentation describing the power and flaws in null move pruning: Null Move pruning (pdf) Slides by Lucas Bradstreet
Null-move heuristic from Wikipedia

References

^ Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
^ George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences, reprinted 1988 in Computer Chess Compendium
^ Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (1975). Some Methods of Controlling the Tree Search in Chess Programs. Artificial Intelligence, Vol. 6, No. 4, pp. 361-371. ISSN 0004-3702. Reprinted (1988) in Computer Chess Compendium
^ Don Beal (1989). Experiments with the Null Move. Advances in Computer Chess 5, A revised version is published (1990) under the title A Generalized Quiescence Search Algorithm. Artificial Intelligence, Vol. 43, No. 1, pp. 85-98. ISSN 0004-3702.
^ Chun Ye (1992). Experiments in Selective Search Extensions. M.Sc. thesis, Department of Computing Science, University of Alberta, pdf, pp. 57
^ Jonathan Schaeffer (1987). Speculative Computing. ICCA Journal, Vol. 10, No. 3
^ Gordon Goetsch, Murray Campbell (1988). Experimenting with the Null Move Heuristic in Chess. AAAI Spring Symposium Proceedings, pp. 14-18
^ Gordon Goetsch, Murray Campbell (1990). Experiments with the Null-Move Heuristic. Computers, Chess, and Cognition, pp. 159-168
^ Chun Ye (1992). Experiments in Selective Search Extensions. M.Sc. thesis, Department of Computing Science, University of Alberta, pdf, pp. 27-29
^ Re: SOMA by Ed Schröder, CCC, August 26, 2009
^ Chrilly Donninger (1993). Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs. ICCA Journal, Vol. 16, No. 3
^ Ernst A. Heinz. (1999). Adaptive null-move pruning. ICCA Journal, Vol. 22, No. 3, ps
^ Position from local chess club by Bernhard Bauer, CCC, November 05, 1999
^ Stefan Plenkner (1995). A Null-Move Technique Impervious to Zugzwang. ICCA Journal, Vol. 18, No. 2
^ Null-move zugzwang avoidance, Jun '95 ICCAJ by Bruce Moreland in rgcc, December 6, 1996
^ Omid David, Nathan S. Netanyahu (2002). Verified null-move pruning. ICGA Journal, Vol. 25 No. 3
^ verified null move by Robert Hyatt, CCC, June 21, 2009
^ Omid David, Nathan S. Netanyahu (2008). Extended Null-Move Reductions. CG 2008, pdf
^ Re: Extended Null-Move Reductions by Robert Hyatt, CCC, August 20, 2010
^ Re: Extended Null-Move Reductions by Marco Costalba, CCC, August 20, 2010
^ Re: Null move? by Vincent Diepeveen, rgcc, October 11, 1997
^ Gordon Goetsch, Murray Campbell (1988). Experimenting with the Null Move Heuristic in Chess. AAAI Spring Symposium Proceedings, pp. 14-18
^ Yngvi Björnsson, Tony Marsland (2000). Selective Depth-First Search Methods. in Jaap van den Herik, Hiroyuki Iida (eds.) (2000). Games in AI Research. Universiteit Maastricht, pdf preprint
^ Deep Search Extension by Stuart Cracraft, CCC, January 18, 1998
^ Null move mate extension by James Robertson, CCC, June 25, 1999
^ mate threat extension/null move by Rick Bischoff, CCC, September 25, 2004
^ Re: mate threat extension/null move by Don Beal, CCC, October 04, 2004 » Mate Threat Extensions and WAC booster
^ null move threat extension by Andrew Short, CCC, October 23, 2008
^ The "same threat extension" as effective way to resolve horizon problem by Sergei Markoff, CCC, October 01, 2003
^ Verified Null-Move Pruning, ICGA 25(3) by Omid David, CCC, November 20, 2002
^ Proving something is better by Bruce Moreland, CCC, December 17, 2002
^ courtesy of Don Beal and Carey Bloodworth, Re: Antique chess programs by Carey, CCC, December 16, 2015
^ Selective Search Techniques in REBEL (introduction) from Programmer Corner by Ed Schröder
^ How Rebel Plays Chess is also available as pdf
^ Nullmove vs classic selective search by Ed Schröder, CCC, August 04, 2012

What links here?

Page	Date Edited
Abyss	Aug 5, 2017
Advances in Computer Chess 5	Dec 2, 2017
AEL-Pruning	Jun 22, 2013
AICE	Nov 29, 2017
Alaric	Mar 4, 2014
Alarm	Jun 7, 2017
Aleks Peshkov	Jan 13, 2016
Alpha-Beta	Jan 28, 2018
Alvaro Cardoso	Jan 12, 2018
Amateur	Feb 25, 2012
Amoeba	Mar 19, 2018
Amy	May 9, 2017
Amyan	Dec 10, 2013
Andrew Grant	Jan 13, 2018
Andscacs	Jan 16, 2018
AnMon	Nov 17, 2017
Arion	Nov 28, 2014
Atlas (ESP)	Jan 28, 2018
Atomystica	Oct 2, 2014
Axon	Jul 14, 2013
Bagatur	Sep 10, 2016
BBchess	Oct 30, 2011
Beaches	Jun 10, 2017
Belzebub	Oct 20, 2015
Beowulf	May 5, 2017
Best Move	May 15, 2017
Betsabe	Jul 23, 2017
Betsy	Jul 28, 2014
BigLion	Sep 28, 2016
BikJump	Aug 11, 2014
Bismark	Apr 22, 2015
Bison	Sep 29, 2016
BlackBishop	Nov 7, 2014
Bobcat	Jun 27, 2017
Bodo	Oct 6, 2016
Booot	Jan 22, 2018
Botvinnik-Markoff Extension	Nov 27, 2015
Brainless	Jun 24, 2017
Branching Factor	Jun 28, 2017
Bruja	Feb 3, 2015
Brutus NL	Aug 22, 2016
Capture (program)	Jan 8, 2016
Carballo	Oct 2, 2016
Celes	May 23, 2014
Cheese	Feb 17, 2018
Cheiron	Jan 7, 2016
Cheng	Jul 30, 2017
Chess Guru	Mar 4, 2017
Chess Wizard	Dec 22, 2014
chess22k	Apr 23, 2018
ChessBrainVB	Jun 24, 2017
Chessterfield	Sep 29, 2016
ChessV	Jan 21, 2018
Chezzz	Jan 20, 2013
Chispa	Feb 13, 2014
Chompster	Jul 27, 2013
Chrilly Donninger	Dec 19, 2016
Cilkchess	Jan 21, 2016
Cinnamon	Sep 23, 2017
Clarabit	Nov 3, 2011
Claudia	Jun 1, 2016
Clubfoot	Sep 8, 2015
Coiled	Mar 12, 2017
Comet	Jan 8, 2016
Counter	Nov 13, 2017
CPW-Engine	Dec 31, 2014
CPW-Engine_search	Feb 4, 2017
Crafty	Jan 28, 2018
Critter	Jan 25, 2014
Crux	Jan 30, 2017
CuckooChess	Jan 17, 2017
Cupcake	May 19, 2016
Cyclone	Nov 24, 2013
Czolgista	Apr 20, 2013
DanaSah	Oct 9, 2017
Daniel Shawul	Jan 28, 2018
DarkThought	Jul 3, 2018
Darmenios	Jan 7, 2016
DayDreamer	Aug 22, 2016
Deep Blue	Aug 1, 2017
Defenchess	Mar 18, 2018
Delfi	Jan 7, 2016
Delphil	Sep 17, 2016
DelphiMax	Apr 3, 2013
Demolito	Mar 1, 2018
Depth	Feb 25, 2018
Depth Reduction R	Oct 4, 2017
Desperado	May 19, 2017
Deuterium	Jun 23, 2014
Diablo	May 17, 2016
Dictionary	Aug 24, 2017
Dimitri	Aug 22, 2017
Diogenes	Jan 8, 2016
DisasterArea	Mar 27, 2017
DiscoCheck	Jun 23, 2017
Djinn	Feb 8, 2016
DOCCC 1993	Dec 12, 2016
Dolphin	Nov 28, 2014
Don Beal	Jul 27, 2017
Don Dailey	Dec 7, 2016
Donna	Aug 17, 2017
Dorky	Oct 10, 2016
Dorpsgek	Apr 2, 2018
Double Null Move	May 8, 2015
Dragon FR	Sep 9, 2016
DrunkenMaster	Nov 1, 2016
Dumb	Mar 10, 2018
E.T.Chess	Jan 28, 2013
Elephant	Sep 19, 2016
Engine Testing	Feb 1, 2018
Enhanced Forward Pruning	Oct 21, 2014
Ernst A. Heinz	Mar 6, 2017
ESC	Aug 14, 2013
Ethereal	Mar 20, 2018
Eugen	Jan 7, 2016
Eugenio Castillo Jiménez	Jul 23, 2017
Eveann	Apr 3, 2017
Exacto	Oct 3, 2015
EXchess	Jan 21, 2018
Extensions	Apr 19, 2018
Fail-High Reductions	Mar 6, 2014
Fail-Soft	Jun 2, 2017
Faile	May 27, 2014
Falcon	Sep 2, 2016
FCP	Jun 15, 2013
Ferret	Jan 7, 2016
Fifty-move Rule	Aug 9, 2017
Fischerle	Aug 21, 2017
Floyd	Sep 11, 2016
Flux	Jan 12, 2016
Fortress (Engine)	Oct 19, 2017
Frank Schneider	Jan 7, 2016
Frenzee	Feb 24, 2013
Freyr	Mar 6, 2014
Fridolin	Jun 27, 2017
Fritz	Feb 26, 2018
Fruit	Sep 27, 2016
Futility Pruning	Aug 30, 2017
Gaia	Nov 3, 2015
Galjoen	Mar 19, 2018
Gandalf	Jan 21, 2018
Garbochess	Sep 23, 2017
Garbochess-JS	Sep 23, 2017
Gaviota	Jan 21, 2018
Gazebo	May 21, 2017
Genesis IL	Feb 15, 2014
Gerbil	Feb 3, 2017
GES	Sep 13, 2015
Ghost	Feb 2, 2018
Gian-Carlo Pascutto	Jan 16, 2018
Gibbon	Dec 23, 2014
Ginkgo	Jul 13, 2016
Gk	Oct 9, 2017
Glass	May 24, 2017
Glaurung	Mar 14, 2017
Godot	Apr 28, 2015
Gogobello	Jul 30, 2017
GopherCheck	Feb 3, 2017
Gordon Goetsch	Jan 7, 2016
Greko	Feb 27, 2018
Gromit	Apr 5, 2017
Guidance for Creating New Pages	Dec 15, 2014
Gullydeckel	Oct 28, 2015
Hagrid	Apr 12, 2016
Hakkapeliitta	Apr 26, 2016
Halfmove Clock	Aug 9, 2017
HaQiKi D	Jul 26, 2017
Harm Geert Muller	Mar 31, 2018
Hash Move	Oct 4, 2017
HeavyChess	Feb 14, 2014
History	Jan 2, 2018
Holmes	Apr 24, 2014
Horizon	Mar 17, 2013
ICGA Journal	Dec 21, 2017
Ifrit	Feb 7, 2016
Ikarus	Jul 5, 2016
InmiChess	Mar 6, 2014
Insomniac	Jan 27, 2016
ISA	Apr 2, 2018
IsiChess	Jan 7, 2016
Iterative Search	Oct 20, 2016
Jabba	Sep 10, 2016
Jan Kaan	Feb 4, 2018
Jazz	Oct 4, 2017
JFresh	Mar 2, 2016
JikChess	Nov 29, 2015
Joker IT	Sep 16, 2017
Jon Dart	Dec 17, 2017
Jumbo	Dec 19, 2017
Kaissa	Apr 9, 2018
Kallisto	Oct 28, 2017
Karlo Bala Jr.	Feb 19, 2017
Kholin	Jan 3, 2018
Killer Move	Feb 16, 2017
King of Kings	Sep 4, 2013
KingSlayer	Oct 17, 2016
Kiwi	Sep 2, 2016
KnightCap	Nov 6, 2016
KnockOut	Sep 20, 2016
Knowledge	Jul 22, 2017
Komodo	Mar 6, 2018
Kurt	Apr 20, 2014
Lachex	Jan 7, 2016
LambChop	Nov 24, 2017
LarsenVB	Jun 24, 2017
Laser	Dec 27, 2017
Lasker-Reichhelm Position	Oct 24, 2017
Late Move Reductions	Sep 25, 2017
Laurie Tunnicliffe	Jun 13, 2017
LChess	Jan 7, 2016
Leen Ammeraal	Nov 3, 2014
Lime	May 17, 2015
Little Wing	Oct 26, 2017
LittleThought	Nov 7, 2016
Lozza	Apr 18, 2018
MadChess	Jul 4, 2017
Madeleine	May 18, 2017
Marco Costalba	Feb 28, 2018
Mark Lefler	Nov 23, 2017
Mark Winands	Sep 19, 2017
Martin Sedlak	Dec 25, 2017
Marvin	Feb 10, 2018
Matador	Oct 30, 2015
Matant	Aug 14, 2013
Mate at a Glance	Sep 24, 2014
Mate Threat Extensions	Apr 14, 2012
Mathematician	Apr 9, 2018
Matthew R. Brades	Jun 9, 2017
Maverick	Jan 7, 2016
MBChess	Sep 29, 2012
Merlin	Jan 20, 2018
Monarch	Nov 19, 2014
Monsoon	Feb 8, 2015
Move Ordering	Feb 27, 2018
Movei	Jan 7, 2016
Moves	Feb 19, 2018
Multi-Cut	Jul 4, 2016
Murka	Nov 11, 2016
Murray Campbell	Jun 2, 2017
Muse	May 17, 2016
Napoleon	Jun 25, 2017
Natwarlal	Aug 26, 2013
Naum	Nov 23, 2017
Nebula	Feb 7, 2015
Nemorino	Dec 21, 2017
Nesik	Jan 24, 2014
NG-play	Feb 26, 2017
Nightmare GER	Dec 12, 2016
Nirvanachess	Sep 30, 2017
Node Types	Oct 22, 2017
NoraGrace	Nov 23, 2014
Null Move	Aug 9, 2017
Null Move Observation	Dec 30, 2015
Null Move Pruning	Dec 2, 2017
Null Move Pruning Test Results	May 16, 2015
Null Move Reductions	Jun 22, 2015
Null Move Test-Positions	Nov 22, 2015
Null Window	Nov 8, 2016
Nullmover	Jul 21, 2013
Obender	Apr 17, 2016
Octochess	Aug 15, 2017
OliThink	May 19, 2017
Omid David	Jan 2, 2017
Onno	Jul 19, 2013
Onno Garms	Jul 19, 2013
Open Source Engines	Jul 14, 2015
Orion	Oct 15, 2017
Othello	Jan 4, 2018
Paladin	Jan 29, 2017
Parity Pruning	Jan 14, 2013
Patzer	Apr 5, 2017
Pawel Koziol	Dec 17, 2017
Pawn Endgame	Oct 11, 2017
Pawny	Jun 17, 2015
Pedro Castro	Apr 19, 2016
Peter Aloysius Harjanto	Jul 21, 2015
Peter Fendrich	May 19, 2017
Phalanx	May 2, 2016
Pharaon	Sep 2, 2017
Phoenix	May 8, 2017
Plisk	Dec 31, 2014
PolarChess	May 15, 2017
Popochin	Feb 5, 2016
PostModernist	Jan 7, 2016
Prédateur	Nov 11, 2016
Principal variation	Dec 4, 2017
ProbCut	Mar 25, 2016
ProChess IT	Sep 30, 2015
Prophet	Sep 30, 2017
Protector	Oct 12, 2017
Protej	Jul 27, 2014
Pruning	Jan 1, 2018
Pulsar	May 4, 2017
Purple Haze	Oct 26, 2017
PV-Move	Jan 16, 2013
Quest	Mar 26, 2017
Quiescence Search	Aug 19, 2017
Rajah	Sep 12, 2012
Ramjet	Sep 27, 2017
RattateChess	Dec 2, 2014
Razoring	Oct 5, 2015
Recursion	Nov 18, 2017
RedQueen	Nov 13, 2017
Reductions	Nov 1, 2017
Refutation Move	May 13, 2013
Rein Halbersma	Dec 22, 2015
Repetitions	Jan 16, 2018
Requiem	Feb 5, 2018
Reverse Futility Pruning	Jun 2, 2017
Rhetoric	Nov 15, 2017
Robocide	May 11, 2016
ROCE	Jun 6, 2017
Rodent	Jan 11, 2018
Rodin	Feb 7, 2016
Roland Pfister	Apr 5, 2017
RomiChess	Jan 2, 2018
Ronald de Man	Nov 20, 2017
Rookie	Jan 7, 2016
Ruffian	Jun 6, 2017
RuyDos	Feb 17, 2018
Scidlet	May 31, 2014
Scott Farrell	Jun 16, 2013
Search Instability	May 5, 2017
Search Pathology	Nov 26, 2017
SEE	Jan 14, 2013
Selectivity	Jan 12, 2018
Senpai	Nov 10, 2017
Severi Salminen	May 7, 2015
SharpChess	Jun 6, 2017
Sharper	Jun 6, 2017
Shield	May 17, 2017
Sierżant	Apr 15, 2014
Simplex	Mar 6, 2016
Singular Extensions	Jan 9, 2018
Sinobyl	Jul 3, 2014
Sjaak (Glebbeek)	Oct 4, 2017
Sjeng	Aug 17, 2017
Sloppy	Sep 17, 2016
Slow Chess	May 17, 2016
Small Potato	Feb 14, 2014
Smash	May 11, 2016
SnailChess	Nov 26, 2014
Snitch	Apr 7, 2016
Socrates	Jul 3, 2018
Soldat	Aug 20, 2017
SOS	Apr 5, 2017
Spector	Nov 11, 2016
Spike	Jan 7, 2016
StarTech	Oct 20, 2016
Stefan Plenkner	Dec 31, 2015
Stockfish	Apr 7, 2018
Stuart Cracraft	May 19, 2017
Sungorus	Apr 11, 2014
Sunsetter	Jun 1, 2017
Tactics	Jan 12, 2018
Tao	Jan 8, 2016
Teki	Mar 29, 2018
Tempo	Jan 17, 2018
Terra	Feb 11, 2015
Texel	Oct 9, 2017
The Baron	Jan 8, 2018
The Turk (TR)	Apr 1, 2017
Thor's Hammer	Nov 23, 2013
Thorsten Greiner	May 9, 2017
Threat Move	Sep 10, 2017
Tigran	Aug 16, 2015
Tom King	Aug 19, 2017
tomitankChess	Dec 8, 2017
Tord Romstad	Dec 9, 2017
Tornado	Dec 14, 2017
TRACE	Feb 14, 2013
Transposition Table	Apr 19, 2018
Triangulation	Apr 4, 2013
TSCP	Feb 5, 2016
Tucano	Dec 16, 2017
Tunguska	Sep 16, 2017
Turning Point	Apr 6, 2012
Tytan	Nov 3, 2015
Uri Blass	Feb 26, 2018
Vadim Demichev	Jul 26, 2013
Vajolet	Jan 25, 2018
Vice	Mar 8, 2016
Virtua Chess	Jul 3, 2018
Virtual Chess	Mar 25, 2017
Voyager	Aug 12, 2012
Walter Faxon	Mar 6, 2015
Wasp	Nov 24, 2017
Waxman	Aug 18, 2014
WChess	Jan 7, 2016
WildCat	Nov 11, 2016
Will Singleton	Mar 6, 2015
Win at Chess	Sep 25, 2017
Wing	Oct 26, 2017
Winglet	Apr 26, 2015
Winglet to include	Apr 25, 2015
Witz	Nov 14, 2017
Woodpusher	Dec 12, 2016
WyldChess	Mar 10, 2018
XiniX	Jan 7, 2016
Xiphos	Apr 22, 2018
Xpdnt	Sep 13, 2015
XXXX	Jan 7, 2016
ZChess	Jan 8, 2016
Zeus	Jan 3, 2018
Zeus RU	Jun 6, 2015
Ziggy IS	Sep 6, 2015
Zochova	Nov 9, 2014
Zugzwang	Dec 8, 2017
Zugzwang (Program)	Dec 19, 2016
Zurichess	Mar 12, 2018
Zzzzzz	May 14, 2016

Up one level

Null Move Reductions

GerdIsenberg — Mon, 22 Jun 2015 12:29:02 GMT

Home * Search * Selectivity * Reductions * Null Move Reductions

Null Move Reductions work similar to Feldmann's Fail-High Reductions, but use a Null Move Search rather than static evaluation and reduces by a amount of four plies rather than one. Omid David and Nathan S. Netanyahu introduced so called Extended Null-Move Reductions ^[1] with an adaptive R based on depth.

If a null move fail-high occurs - opposed to Null Move Pruning - the search is reduced by four plies, rather than pruned. Thus, Null Move Reductions are therefor less vulnerable to Zugzwang and might even applied in (late) endings.

if ( nullMoveAllowed && ...) {
   R = depth > 6 ? 4 : 3;
   makeNullMove()
   score = -zwSearch(1-beta, depth-R-1) // -AlphaBeta (0-beta, 1-beta, depth-R-1)
   unmakeNullMove();
   if (score >= beta ) {
      depth -= 4; // reduce search
      if ( depth <= 0 )
          return Evaluate(); // Quiescence
   }
}
// continue search

For zwSearch, see Zero Window Search inside the Principal Variation Search.

Forum Posts

Extended Null-Move Reductions by Alvaro Cardoso, CCC, August 20, 2010
Null move alterative in endgames by Aleks Peshkov, CCC, November 16, 2011
thoughts on null-move reduction by Youri Matiounine, CCC, June 14, 2015 » Null Move Pruning

References

^ Omid David, Nathan S. Netanyahu (2008). Extended Null-Move Reductions. CG 2008, pdf

What links here?

Page	Date Edited
Aleks Peshkov	Jan 13, 2016
Alvaro Cardoso	Jan 12, 2018
Depth Reduction R	Oct 4, 2017
Double Null Move	May 8, 2015
Fail-High Reductions	Mar 6, 2014
Falcon	Sep 2, 2016
Francesca	Jan 7, 2016
Green Light Chess	Jan 21, 2018
Null Move	Aug 9, 2017
Null Move Observation	Dec 30, 2015
Null Move Pruning	Dec 2, 2017
Null Move Reductions	Jun 22, 2015
Reductions	Nov 1, 2017
Sayuri	Oct 1, 2017
Selectivity	Jan 12, 2018
Soldat	Aug 20, 2017
Winter	Jan 23, 2018
Zugzwang	Dec 8, 2017

Up one level

Passed Pawn Extensions

GerdIsenberg — Mon, 11 May 2015 18:18:16 GMT

Home * Search * Selectivity * Extensions * Passed Pawn Extensions

Passed Pawn Extensions are triggered after a passed pawn is established on the seventh or sometimes sixth rank, that is after a pawn push or captures with a pawn. The idea is to avoid horizon effects regarding a possible promotion, and to determine whether the stop- or promotion square is or may blocked, defended or supported. Clearly, this extension heavily interacts with the evaluation of passed pawns, and may also restricted to certain node types and distance to horizon. Some programs also extend promotions itself and not only if there starts a threat to promote.

Colin Frayn on Pawn Push Extensions ^[1]:

If a pawn is pushed to the 7th rank, or promoted, then extend.
This helps spot winning tactics in the endgame.
Not so useful if your endgame analysis function is good enough at handling passed pawns.

Forum Posts

Passed Pawn Extensions by Roberto Waldteufel, CCC, May 24, 2000
passed pawn extension by James Swafford, CCC, January 28, 2002
PASSED_PAWN_PUSH extension scheme (and SmarThink) by Sergei S. Markoff, CCC, September 18, 2002
Adding an Extension Results in Deeper General Search! by Steve Maughan, CCC, May 10, 2015

External Links

References

^ Computer Chess Programming Theory - Search Extensions by Colin Frayn
^ How Rebel Plays Chess is also available as pdf reprint

What links here?

Page	Date Edited
More Links
Amundsen	Sep 3, 2013
Bobcat	Jun 27, 2017
Brainstorm	Jun 24, 2017
Bringer	Jul 14, 2014
Bruja	Feb 3, 2015
Carballo	Oct 2, 2016
Cheese	Feb 17, 2018
Chezzz	Jan 20, 2013
Coiled	Mar 12, 2017
Counter	Nov 13, 2017
DanaSah	Oct 9, 2017
Diablo	May 17, 2016
Djinn	Feb 8, 2016
DrunkenMaster	Nov 1, 2016
Eveann	Apr 3, 2017
Exacto	Oct 3, 2015
Extensions	Apr 19, 2018
Falcon	Sep 2, 2016
Fischerle	Aug 21, 2017
Flux	Jan 12, 2016
Fortress (Engine)	Oct 19, 2017
GES	Sep 13, 2015
Gibbon	Dec 23, 2014
Greko	Feb 27, 2018
Horizon	Mar 17, 2013
Jabba	Sep 10, 2016
James Swafford	Jan 1, 2018
KnockOut	Sep 20, 2016
Matilde	Jan 1, 2014
NoraGrace	Nov 23, 2014
OliThink	May 19, 2017
Passed Pawn	Oct 11, 2017
Passed Pawn Extensions	May 11, 2015
Passed Pawns (Bitboards)	Aug 23, 2010
Pawn Endgame	Oct 11, 2017
Pepito	Nov 27, 2014
PolarChess	May 15, 2017
Popochin	Feb 5, 2016
Prophet	Sep 30, 2017
Rajah	Sep 12, 2012

Up one Level

Pruning

GerdIsenberg — Mon, 01 Jan 2018 11:21:17 GMT

Home * Search * Selectivity * Pruning

		Pruning, (as opposed to reductions) a name for every heuristic that removes completely certain branches of the search tree, assuming they have no bearing to the search result. Alpha-Beta may be considered as backward pruning, because we found a refutation after searching ^[1]. Forward pruning always involves some risks to overlook something, with influence on the root score. Some pruning techniques rely on a specialized, but reduced search, others rely only on static move properties. Shannon Type B programs only consider some plausible mores, but all other moves are pruned.
Samuel Bak - Under the Trees ^[2]

Backward pruning

sound pruning, not affecting the search result

Mate Distance Pruning

Forward pruning techniques

Forward pruning techniques are either applied at expected Cut-Nodes or All-Nodes and return either beta as lower bound or alpha as upper bound. The none recursive ProbCut is applied at both types of none PV-nodes. Rather than immediately returning alpha at strong expected All-Nodes after a reduced or quiescence search, pruning techniques near the horizon skip moves, which are very unlikely to exceed alpha, or in case of the quiescence search itself, all (most) quiet moves as well as losing captures.

Returning Beta

at expected Cut-Nodes:

Null Move Pruning - if reduced nullmove search fails high, return beta
Multi-Cut - if a reduced, specialized search has C cut-offs from N tried moves, return beta
Enhanced Forward Pruning, also applicable at expected All-Nodes
ProbCut
Reverse Futility Pruning
Standing Pat in Quiescence Search

Returning Alpha

or below at expected All-Nodes or expected Cut-Nodes which turn out to become All-Nodes:

after trying width[ply] moves in Shannon Type-B programs, return alpha
Sibling Prediction Pruning - return alpha, or depending on the implementation, only skip the move
ProbCut
Uncertainty Cut-Offs

Skipping Moves

likely at All-Nodes:

Publications

1960 ...

Richard Greenblatt, Donald Eastlake, Stephen D. Crocker (1967). The Greenblatt Chess Program. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, pp. 801-810. Reprinted (1988) in Computer Chess Compendium, pdf from The Computer History Museum or as pdf or ps from DSpace at MIT

1970 ...

John Birmingham, Peter Kent (1977). Tree-searching and tree-pruning techniques. Advances in Computer Chess 1, reprinted in Computer Chess Compendium

1980 ...

Peter W. Frey (1983). The Alpha-Beta Algorithm: Incremental Updating, Well-Behaved Evaluation Functions, and Non-Speculative Forward Pruning. Computer Game-Playing (ed. Max Bramer), pp. 285-289. Ellis Horwood Limited Publishers, Chichester.
Jonathan Schaeffer (1986). Experiments in Search and Knowledge. Ph.D. thesis, University of Waterloo. Reprinted as Technical Report TR 86-12, Department of Computing Science, University of Alberta
Hermann Kaindl, Marcus Wagner, Helmut Horacek (1988). Comparing Various Pruning Algorithms on Very Strongly Ordered Game Trees: The Details. Tech. Report #50, Department of Statistics and Computer Science, Vienna University of Technology
Hermann Kaindl, Marcus Wagner, Helmut Horacek (1989). Comparing Various Pruning Algorithms on Very Strongly Ordered Game Trees. Workshop on New Directions in Game-Tree Search
Liwu Li (1989). Probabilistic Analysis of Search. Ph.D. thesis, University of Alberta, advisor Tony Marsland
Liwu Li, Tony Marsland (1989). Probability-Based Game Tree Pruning. pdf

1990 ...

Liwu Li, Tony Marsland (1990). Probability-Based Game Tree Pruning. Journal of Algorithms, Vol. 11, No. 1
Chun Ye, Tony Marsland (1992). Experiments in Forward Pruning with Limited Extensions. ICCA Journal, Vol. 15, No. 2
Yi-Fan Ke, Tai-Ming Parng (1993). The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning. ICCA Journal, Vol. 16, No. 2
Chrilly Donninger. (1993). Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs. ICCA Journal, Vol. 16, No. 3
Stephen J.J. Smith, Dana S. Nau (1994). An Analysis of Forward Pruning. Proceedings AAAI 1994, pdf
Michael Buro (1995). ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm. ICCA Journal, Vol. 18, No. 2, pdf
Ernst A. Heinz (1998). Extended Futility Pruning. ICCA Journal, Vol. 21, No. 3
Yngvi Björnsson, Tony Marsland (1998). Multi-Cut Pruning in Alpha-Beta Search. CG 1998, pp. 15-24. See also Yngvi Björnsson, Tony Marsland (2001). Multi-cut Alpha-Beta Pruning in Game Tree Search. Theoretical Computer Science, Vol. 252, pp. 177-196 for an expanded version.

2000 ...

Ernst A. Heinz (2000). AEL Pruning. ICGA Journal, Vol. 23, No. 1, pdf
Yngvi Björnsson, Tony Marsland (2000). Selective Depth-First Search Methods. in Jaap van den Herik, Hiroyuki Iida (eds.) (2000). Games in AI Research. Universiteit Maastricht, pdf preprint
Yngvi Björnsson, Tony Marsland (2001). Multi-cut Alpha-Beta Pruning in Game Tree Search. Theoretical Computer Science, Vol. 252, pp. 177-196. pdf
Mark Winands, Jaap van den Herik, Jos Uiterwijk, Erik van der Werf (2003). Enhanced forward pruning. Accepted for publication. pdf
Qian Liang (2003). The Evolution of Mulan: Some Studies in Game-Tree Pruning and Evaluation Functions in the Game of Amanons. M.Sc. thesis, Electronic Engineering, The University of New Mexico, pdf
Yew Jin Lim, Wee Sun Lee (2006). Properties of Forward Pruning in Game-Tree Search, AAAI 2006, pdf
Yew Jin Lim, Wee Sun Lee (2006). RankCut - A Domain Independent Forward Pruning Method for Games, AAAI 2006, pdf
Jeroen Carolus (2006). Alpha-Beta with Sibling Prediction Pruning in Chess. Masters thesis, pdf
Yew Jin Lim (2007). On Forward Pruning in Game-Tree Search. Ph.D. thesis, National University of Singapore, pdf

2010 ...

Kieran Greer (2012). Tree Pruning for New Search Techniques in Computer Games. Advances in Artificial Intelligence, Vol. 2013
Kieran Greer (2013). Dynamic Move Chains – a Forward Pruning Approach to Tree Search in Computer Chess. arXiv:1403.0778

Forum Posts

1995 ...

Forward pruning by Frank Phillips, CCC, October 16, 1999
Re: Forward pruning by Andrew Williams, CCC, October 16, 1999

2000 ...

Alpha beta fail soft, pruning & hash bounds? by Steve Maughan, CCC, December 14, 2000 » Fail-Soft, Bound
Correct values if all moves are pruned? by Severi Salminen, CCC, January 05, 2001
An interesting forward pruning experiment - with pseudo description by Vincent Diepeveen, rgcc, February 08, 2003
Testing the reliability of forward pruning by Russell Reagan, CCC, May 15, 2003 » Engine Testing
Forward Pruning... by Joshua Haglund, CCC, February 29, 2004
Forward pruning and some related techniques by Sergei Markoff, CCC, March 02, 2004
Bayesian Forward Pruning by Dann Corbit, CCC, April 09, 2004
Forward/HB/Null move pruning ideas by Sergei Markoff, CCC, September 25, 2004

2005 ...

About history pruning... by Svein Bjørnar Myrvang, CCC, October 26, 2005
Fail-low pruning by Tommi Rimpiläinen, CCC, January 17, 2006
History pruning by Frank Phillips from CCC, February 27, 2006
history pruning/ late move pruning by Tom King, Winboard Programming Forum, March 02, 2006
avoidrep-pruning by Gerd Isenberg, CCC, May 15, 2007 » Repetitions
Toga/Glaurung/Strelka Prunings/Reductions by Edsel Apostol, CCC, January 31, 2008 » Toga, Glaurung, Strelka, Reductions
Fruit 2.1 pruning by kongsian, CCC, July 15, 2008 » Fruit

2010 ...

What program first used hard pruning? by Larry Kaufman, CCC, December 10, 2010
Hard pruning history by Mark Watkins, Open Chess Programming Forum, December 10, 2010
Using SEE to prune in main search by Tom King, CCC, January 08, 2011 » Static Exchange Evaluation
Bad Pruning by Onno Garms, CCC, March 13, 2011 » Onno
Reducing/Pruning Bad Captures (SEE < 0) by Edsel Apostol, CCC, August 19, 2011 » SEE
Relationship between move ordering and pruning by Don Dailey, OpenChess Forum, December 17, 2012 » Move Ordering
Adjustable search pruning depending on time control by Jerry Donald, CCC, December 20, 2012 » Time Management
Pruning in QS by Harm Geert Muller, CCC, March 06, 2013 » Quiescence Search
Pruning in today's top engines by Gordon Robertson, CCC, September 13, 2013
stalemate detection and pruning by Jon Dart, CCC, September 22, 2013 » Stalemate
pruning statistics by Jon Dart, CCC, January 27, 2014 » Search Statistics

2015 ...

Verification of pruning techniques by Shawn Chidester, CCC, October 04, 2015
EMR & EMP by Michael Sherwin, CCC, July 19, 2016
Transposition table based pruning idea by Jerry Donald, CCC, December 25, 2017 » Transposition Table

External Links

Pruning Search Trees

Selective Search Techniques in REBEL (introduction) from Programmer Corner by Ed Schröder ^[4] » Rebel

Pruning Trees

References

^ Better Alpha-Beta algorithm than pruning, to don't confuse it with the mentioned forward pruning
^ Under the Trees, Oil on Canvas, 160 x 200 cm, Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
^ Re: What is History Pruning? by Tord Romstad, CCC, July 03, 2005
^ Nullmove vs classic selective search by Ed Schröder, CCC, August 04, 2012

What links here?

Page	Date Edited
Abyss	Aug 5, 2017
ACM 1991	Nov 25, 2017
AEL-Pruning	Jun 22, 2013
Android-Chess	Jun 2, 2016
Andscacs	Jan 16, 2018
Aristarch	May 8, 2014
Asymmetric evaluation	Nov 17, 2016
Awit	Dec 22, 2017
Bagatur	Sep 10, 2016
Bebe	Dec 23, 2017
Beowulf	May 5, 2017
Blockage Detection	Oct 19, 2017
Bobby	Jan 7, 2016
Bobcat	Jun 27, 2017
Bodo	Oct 6, 2016
Bound	Jan 25, 2017
BP	Jan 7, 2016
Brainless	Jun 24, 2017
Branching Factor	Jun 28, 2017
Bringer	Jul 14, 2014
CAPS	Dec 23, 2017
Captures	Oct 1, 2017
Chenard	Sep 5, 2015
Chess System Tal	Jan 13, 2017
Chess Wizard	Dec 22, 2014
ChessV	Jan 21, 2018
Chezzz	Jan 20, 2013
Chiron	Sep 24, 2017
Coiled	Mar 12, 2017
Crafty	Jan 28, 2018
Critter	Jan 25, 2014
Debugging	Jan 20, 2018
Delta Pruning	Dec 2, 2014
Depth	Feb 25, 2018
Dictionary	Aug 24, 2017
Djinn	Feb 8, 2016
Don Dailey	Dec 7, 2016
Double Attack	Oct 22, 2014
Double Null Move	May 8, 2015
DrunkenMaster	Nov 1, 2016
Edsel Apostol	Nov 2, 2016
Engine Testing	Feb 1, 2018
Enhanced Forward Pruning	Oct 21, 2014
Eric Wefald	Jun 23, 2011
Eveann	Apr 3, 2017
Exacto	Oct 3, 2015
Extensions	Apr 19, 2018
Fail-Soft	Jun 2, 2017
Fischerle	Aug 21, 2017
Flux	Jan 12, 2016
Francesca	Jan 7, 2016
Frank Phillips	Sep 26, 2016
Fruit	Sep 27, 2016
Futility Pruning	Aug 30, 2017
Gaia	Nov 3, 2015
Gerbil	Feb 3, 2017
Gibbon	Dec 23, 2014
Glaurung	Mar 14, 2017
GopherCheck	Feb 3, 2017
Green Light Chess	Jan 21, 2018
Gromit	Apr 5, 2017
Guard Heuristic	Nov 18, 2015
Hannibal	Oct 4, 2017
HaQiKi D	Jul 26, 2017
Harm Geert Muller	Mar 31, 2018
History Leaf Pruning	Apr 15, 2013
Horizon	Mar 17, 2013
iCE	Jan 4, 2016
Interception	May 21, 2011
Interior Node Recognizer	Mar 12, 2018
Iteration	May 5, 2017
Junior	Feb 27, 2018
Kches6	Jan 2, 2018
Kieran Greer	Nov 7, 2014
Komodo	Mar 6, 2018
Ktulu	May 16, 2015
Kurt	Apr 20, 2014
Lachex	Jan 7, 2016
LittleThought	Nov 7, 2016
Liwu Li	Nov 27, 2017
Madlenka	Dec 10, 2017
Mark Winands	Sep 19, 2017
Master	Dec 28, 2017
Mate Distance Pruning	Jun 2, 2017
Mate Search	Oct 22, 2016
Mathematician	Apr 9, 2018
Michael Sherwin	Dec 18, 2017
Michel Van den Bergh	Mar 10, 2018
Move Ordering	Feb 27, 2018
Multi-Cut	Jul 4, 2016
Murka	Nov 11, 2016
Muse	May 17, 2016
Neurosis	Dec 23, 2017
Nimzo	Dec 30, 2017
Null Move Pruning	Dec 2, 2017
Null Move Pruning Test Results	May 16, 2015
Omid David	Jan 2, 2017
Onno	Jul 19, 2013
Onno Garms	Jul 19, 2013
Othello	Jan 4, 2018
Parity Pruning	Jan 14, 2013
Parrot	Dec 31, 2014
Patzer	Apr 5, 2017
Peasant	May 21, 2015
Pharaon	Sep 2, 2017
Pioneer	Dec 23, 2017
Point Value by Regression Analysis	Aug 26, 2017
Prédateur	Nov 11, 2016
ProbCut	Mar 25, 2016
Proscha	May 20, 2015
Pruning	Jan 1, 2018
Querg	Dec 11, 2013
Quiescence Search	Aug 19, 2017
Rajah	Sep 12, 2012
Razoring	Oct 5, 2015
Recursion	Nov 18, 2017
Reductions	Nov 1, 2017
Repetitions	Jan 16, 2018
Reverse Futility Pruning	Jun 2, 2017
Rookie	Jan 7, 2016
Ruffian	Jun 6, 2017
Russell Reagan	Aug 31, 2013
Ruy Lopez	Jun 3, 2017
Schach (US)	Jul 21, 2016
Schooner	Feb 2, 2018
Scott Farrell	Jun 16, 2013
Search Instability	May 5, 2017
Search Statistics	Jan 16, 2018
Searcher	Sep 26, 2016
Selectivity	Jan 12, 2018
Senpai	Nov 10, 2017
Sergei Markoff	Mar 12, 2018
Severi Salminen	May 7, 2015
Shawn Chidester	Aug 9, 2016
Singular Extensions	Jan 9, 2018
Sjeng	Aug 17, 2017
Snitch	Apr 7, 2016
Stalemate	Feb 21, 2018
Static Exchange Evaluation	Dec 14, 2017
Stephen J.J. Smith	Apr 7, 2014
Steve Maughan	Jan 31, 2018
Stockfish	Apr 7, 2018
Strelka	May 17, 2016
Tactics	Jan 12, 2018
Tai-Ming Parng	May 23, 2016
Tech	Apr 20, 2018
The Fox	Feb 27, 2017
The Turk	Apr 1, 2017
Time Management	Mar 20, 2018
Toga	Dec 28, 2017
TRACE	Feb 14, 2013
Trajectory	Jan 3, 2015
Transposition Table	Apr 19, 2018
Turbostar	Jan 8, 2016
Uncertainty Cut-Offs	Jul 21, 2015
Warp	Nov 26, 2017
Wasp	Nov 24, 2017
WChess	Jan 7, 2016
Witz	Nov 14, 2017
Woodpusher	Dec 12, 2016
Xiphos	Apr 22, 2018
Yi-Fan Ke	Feb 16, 2015
Zarkov	Feb 26, 2018
ZChess	Jan 8, 2016
Zurichess	Mar 12, 2018

Up one level

Quiescence Search

GerdIsenberg — Sat, 19 Aug 2017 16:54:20 GMT

Home * Search * Quiescence

		Most chess programs, at the end of the main search perform a more limited quiescence search, containing fewer moves. The purpose of this search is to only evaluate "quiet" positions, or positions where there are no winning tactical moves to be made. This search is needed to avoid the horizon effect. Simply stopping your search when you reach the desired depth and then evaluate, is very dangerous. Consider the situation where the last move you consider is QxP. If you stop there and evaluate, you might think that you have won a pawn. But what if you were to search one move deeper and find that the next move is PxQ? You didn't win a pawn, you actually lost a queen. Hence the need to make sure that you are evaluating only quiescent (quiet) positions.
Karen Schuman, Quiescence ^[1]

Limiting Quiescence

Despite the fact that quiescence searches are typically very short, about 50%-90% nodes are spent there, so it is worthwhile to apply some pruning there. Apart from not trying moves with the static exchange evaluation < 0, delta pruning can be used for that purpose.

Standing Pat

In order to allow the quiescence search to stabilize, we need to be able to stop searching without necessarily searching all available captures. In addition, we need a score to return in case there are no captures available to be played. This is done by a using the static evaluation as a "stand-pat" score (the term is taken from the game of poker, where it denotes playing one's hand without drawing more cards). At the beginning of quiescence, the position's evaluation is used to establish a lower bound on the score. This is theoretically sound because we can usually assume that there is at least one move that can either match or beat the lower bound. This is based on the Null Move Observation - it assumes that we are not in Zugzwang. If the lower bound from the stand pat score is already greater than or equal to beta, we can return the stand pat score (fail-soft) or beta (fail-hard) as a lower bound. Otherwise, the search continues, keeping the evaluated "stand-pat" score as an lower bound if it exceeds alpha, to see if any tactical moves can increase alpha.

Checks

Some programs search treat checks and check evasions specially in quiescence. The idea behind this is that if the side to move is in check, the position is not quiet, and there is a threat that needs to be resolved. In this case, all evasions to the check are searched. Stand pat is not allowed if we are in check, for two reasons. First, because we are not sure that there is a move that can match alpha--in many positions a check can mean a serious threat that cannot be resolved. Second, because we are searching every move in the position, rather than only captures.
Standing pat assumes that even if we finish searching all moves, and none of them increase alpha, one of the non-tactical moves can most likely raise alpha. This is not valid if we search every move. The other case of treating checks specially is the checking moves themselves. Some programs, after searching all the captures in a position without finding a move to raise alpha, will generate non-capture moves that give check. This has to be limited somehow, however, because in most given positions there will be very many long and pointless checking sequences that do not amount to anything. Most programs achieve this limit by delta pruning checks, as well as limiting the generation of checks to the first X plies of quiescence.

Pseudo Code

int Quiesce( int alpha, int beta ) {
    int stand_pat = Evaluate();
    if( stand_pat >= beta )
        return beta;
    if( alpha < stand_pat )
        alpha = stand_pat;
 
    until( every_capture_has_been_examined )  {
        MakeCapture();
        score = -Quiesce( -beta, -alpha );
        TakeBackMove();
 
        if( score >= beta )
            return beta;
        if( score > alpha )
           alpha = score;
    }
    return alpha;
}

Publications

1975

Larry Harris (1975) The Heuristic Search And The Game Of Chess - A Study Of Quiescence, Sacrifices, And Plan Oriented Play. IJCAI 1975 Tbilisi, Georgia: 334-339. reprinted (1988) in Computer Chess Compendium

1980 ...

Hermann Kaindl (1982). Dynamic Control of the Quiescence Search in Computer Chess. Cybernetics and Systems Research (ed. R. Trappl), pp. 973-977. North-Holland, Amsterdam.
Hermann Kaindl (1982). Quiescence Search in Computer Chess. SIGART Newsletter, 80, pp. 124-131. Reprinted (1983) in Computer-Game-Playing: Theory and Practice, pp. 39-52. Ellis Horwood Ltd., Chichester.
Don Beal (1984). Mating Sequences in the Quiescence Search. ICCA Journal, Vol. 7, No. 3
Prakash Bettadapur (1986). Experiments in Chess Capture Search, M.Sc. Thesis, Department of Computing Science, University of Alberta.
Prakash Bettadapur (1986). Influence of Ordering on Capture Search. ICCA Journal, Vol. 9, No. 4
Prakash Bettadapur, Tony Marsland (1988). Accuracy and Savings in Depth-Limited Capture Search. In International Journal of Man-Machine Studies, 29 (5) pp. 497-502
Don Beal (1989). Experiments with the Null Move. Advances in Computer Chess 5, a revised version is published (1990) under the title A Generalized Quiescence Search Algorithm. Artificial Intelligence, Vol. 43, No. 1, pp. 85-98. ISSN 0004-3702, edited version in (1999). The Nature of MINIMAX Search. Ph.D. thesis, IKAT, ISBN 90-62-16-6348. Chapter 10, pp. 101-116 » Null Move
Günther Schrüfer (1989). A Strategic Quiescence Search. ICCA Journal, Vol. 12, No. 1 » Bobby's Strategic Quiescence Search

1990 ...

Don Beal (1990). A Generalized Quiescence Search Algorithm. Artificial Intelligence, Vol. 43, No. 1, pp. 85-98. ISSN 0004-3702
Sören Walter Perrey (1991). Mathematische Methoden der Künstlichen Intelligenz: Zur Quiescence-Suche in Spielbäumen. Diplom thesis, Sonderforschungsbereich 343, E91-006, University of Bielefeld (German) ^[2]
Michael Gherrity, Paul Kube (1993). Quiescent Search is Beneficial. Technical Report CS93-289, University of California, San Diego
Don Beal (1999). The Nature of MINIMAX Search. Ph.D. thesis, IKAT, ISBN 90-62-16-6348

2000 ...

Jeff Rollason (2000). SUPER-SOMA - Solving Tactical Exchanges in Shogi without Tree Searching. Lecture Notes In Computer Science, Vol. 2063, CG 2000, Word preprint ^[3]
Jeff Rollason (2006). Looking for Alternatives to Quiescence Search. AI Factory, Autumn 2006
Don Beal (2006). Review of a nullmove-quiescence search mechanism from 1986. (Draft) ^[4]
Maarten Schadd, Mark Winands (2009). Quiescence Search for Stratego. In BNAIC 2009, pdf

Forum Posts

1994 ...

Efficient quiescence by Hans Bogaards, rec.games.chess, January 19, 1994
Computer Chess: swap down evaluators vs capture search by Jon Dart, rgc, October 24, 1994 » Swap-off algorithm - SOMA
Re: Computer Chess: swap down evaluators vs capture search by Deniz Yuret, rgc, October 26, 1994
quiescence search problems by Matt Craighead, rgcc, August 01, 1995
Re: Quiescence search problems by David Blackman, rgcc, August 3, 1995 » Integrated Bounds and Values
quiescent vs non-quiescent node counting by Robert Hyatt, rgcc, July 01, 1996
Deep Quiesence Searching by Steve Dicks, rgcc, February 22, 1997
quiescence search by Andrew Tridgell, rgcc, April 16, 1997 » Check, Crafty
Limiting the QSearch by John Scalo, CCC, December, 30, 1997
Quiescence vs swapoff by Peter Fendrich, CCC, April 15, 1998
SEE for forward pruning in Q. Search by Tom King, CCC, August 04, 1999 » SEE
SEE for forward pruning in the Q. search - I'm confused! by Tom King, CCC, August 11, 1999

2000 ...

What is the q-search? by Leonid, CCC, January 07, 2000
Qsearch problems...(about sorting and SEE) by Severi Salminen, CCC, November 26, 2000 » Static Exchange Evaluation

2001

Bonus points for side to move in qsearch? by Leen Ammeraal, CCC, January 06, 2001 » Tempo
About limiting Qsearch, again... by Severi Salminen, CCC, December 29, 2001
About qsearch... by Severi Salminen, CCC, December 27, 2001
Qsearch survey by Severi Salminen, CCC, December 30, 2001

2002

Checks in the Qsearch by Scott Gasch, CCC, June 28, 2002 » Check
A question about quiescence search by Nagendra Singh Tomar, CCC, October 19, 2002
Quiescence Explosion by David Rasmussen, CCC, November 26, 2002
Quiescent Explosion by macaroni, CCC, June 26, 2003
Regarding Qsearch with Fractional ply extensions by Federico Corigliano, CCC, August 11, 2003 » Depth - Fractional Plies
real job of the qSearch? find quiet vs stop horizon effect by Scott Farrell, CCC, August 28, 2003
quiescence by Noah Roberts, rgcc, September 20, 2003

2004

QSearch() as PVS() ? by Matthias Gemuh, CCC, January 14, 2004
Rebel's long checks concept in QS by milix, CCC, January 23, 2004 » Rebel, Check
quiesce node explosion by Mike Siler, CCC, January 24, 2004
Qsearch Checks by Tor Lattimore, CCC, August 29, 2004 » Check
Checks in QSearch by Dan Honeycutt, Winboard Programming Forum, November 23, 2004

2005 ...

quiescence search / horizon question by Andrew Shapira, CCC, August 26, 2005
How to Best Limit Checks in the Quiescence ? by Stuart Cracraft, CCC, August 20, 2007 » Check, Checks in Quiescence Search
Quiescence Search Explosions by Mike Leany, CCC, April 18, 2008
checks in q-search by Robert Hyatt, CCC, September 02, 2008
Limiting Quiescent Search Depth by John Merlino, CCC, May 20, 2009
Null move in quiescence search idea from Don Beal, 1986 by Eelco de Groot, CCC, Aug 17, 2009 » Null Move Pruning, Don Beal
Threat information from evaluation to inform q-search by Gary, CCC, September 15, 2009
Only recaptures in qsearch? by John Merlino, CCC, November 21, 2009

2010 ...

Avoiding qsearch explosion by Marco Costalba, CCC, January 29, 2010
Problems when implementing checks in qsearch by Luca Hemmerich, CCC, February 03, 2010
Standpat and check by Vlad Stamate, CCC, February 06, 2010 » Standing Pat, Check
This is totally weird ... Don't understand at all by Gregory Strong, CCC, November 13, 2010

2012

checks in quies by Larry Kaufman, CCC, March 22, 2012
stand pat or side to move bonus by Larry Kaufman, CCC, March 22, 2012
Some thoughts on QS by Harm Geert Muller, CCC, July 19, 2012
QSearch, checks and the lack of progress... by Mincho Georgiev, CCC, July 27, 2012
Quiescence - Check Evaluation and Depth Control by Cheney Nattress, CCC, November 10, 2012

2013

Quiescent search, and side to move is in check by Louis Zulli, CCC, February 08, 2013
Transposition table usage in quiescent search? by Jerry Donald, CCC, March 01, 2013 » Transposition Table
Pruning in QS by Harm Geert Muller, CCC, March 06, 2013 » Pruning
QS investigation by Ed Schröder, CCC, March 07, 2013
qsearch question by nak3c, OpenChess Forum, August 19, 2013
about qs by Daniel Anulliero, CCC, September 11, 2013

2014

Positional quiesence by Harm Geert Muller, CCC, April 12, 2014
Transposition table in Q-search by Alex Ferguson, CCC, December 26, 2014 » Transposition Table

2015 ...

Detail evaluation within quiescence search by Reinhard Scharnagl, CCC, February 22, 2015
hanging piece at starting quiescence search - how to handle? by Reinhard Scharnagl, CCC, February 22, 2015 » Hanging Piece
Search algorithm in it's simplest forum by Mahmoud Uthman, CCC, February 25, 2015 » Alpha-Beta
Check-extension in QS by Harm Geert Muller, CCC, April 03, 2015 » Check
quiescence search (best practices) by thevinenator, OpenChess Forum, July 02, 2015
Null Move in Quiescent search by Laurie Tunnicliffe, CCC, December 09, 2015 » Null Move Pruning, Search Pathology

2016

Checks in qsearch - must-have or optional? by Martin Fierz, CCC, March 15, 2016 » Check, Checks in Quiescence Search
Hashing in Qsearch? by Martin Fierz, CCC, April 03, 2016 » Transposition Table
Quiescence node explosion by sandermvdb, OpenChess Forum, June 01, 2016 » Search Explosion
Starting with quiescence search by Luis Babboni, CCC, July 28, 2016
Quiescence Search Performance by David Cimbalista, CCC, July 28, 2016
Removing Q-search by Matthew Lai, CCC, September 02, 2016
Searching using slow eval with tactical verification by Matthew Lai, CCC, September 06, 2016
Collecting PVs of Qsearch ? by Mahmoud Uthman, CCC, October 22, 2016 » Principal Variation, Triangular PV-Table

2017

capturing PV in QSearch by thevinenator, OpenChess Forum, January 20, 2017 » Principal Variation, Triangular PV-Table
Ridiculous QSearch Depth by Jonathan Rosenthal, CCC, March 03, 2017 » Depth
Q search explosion by Colin Jenkins, CCC, March 30, 2017 » Search Explosion
Probe EGT in quiescence? by Nguyen Pham, CCC, May 20, 2017 » Endgame Tablebases, Xiangqi
Is expensive eval required for QS? by Alexandru Mosoi, CCC, July 21, 2017 » Lazy Evaluation

External Links

Quiescence search from Wikipedia
Quiescence from Wikipedia
Quiescence Search from Bruce Moreland's Programming Topics
Quiescent Search in REBEL from Ed Schröder's Programmer Stuff
Pim Jacobs, Ruud Jacobs, Ruud Brink, Wim Overgaauw, Dom Um Romão, Astrud Gilberto - Meditation, It Might as Well Be Spring, Telephone Song, Only Trust Your Heart, Corcovado (Quiet Nights of Quiet Stars), The Girl From Ipanema; from Dzjes Zien à la Bossa Nova, NCRV 1965, YouTube Video

References

^ Quiescence by Karen Schuman from Artist Karen Schuman’s Personal Mythology Reviewed by Anna Poplawska
^ Ingo Althöfer (1991). Mathematische Methoden der Künstlichen Intelligenz: Zur Quiescence-Suche in Spielbäumen. Review, ICCA Journal, Vol. 14, No. 2
^ Jeff Rollason (2006). Looking for Alternatives to Quiescence Search. AI Factory, Autumn 2006
^ courtesy of Don Beal and Carey Bloodworth, Re: Antique chess programs by Carey, CCC, December 16, 2015

Up one level

Recapture Extensions

GerdIsenberg — Sat, 02 Feb 2013 12:56:03 GMT

Home * Search * Selectivity * Extensions * Recapture Extensions

Recapture Extensions are a subset of Capture Extensions, restricted to recaptures to the same target square. A recapture is supposed to be a relatively forced move. However, some programmers consider any two consecutive captures ^[1], or even any capture with respect to an intermediate Zwischenzug ^[2], if it restores the material balance of the root as recapture, while others recently favor to restrict them to PV-nodes only ^[3].

Forum Posts

Search extensions on recaptures by Chua Kong Sian, gnu.chess, March 22, 1994
Capture/recapture extensions by Andrew Williams, CCC, December 14, 1998
Recapture Extensions by Scott Gasch, CCC, June 01, 2001
Search extensions at promising trajectories by Reinhard Scharnagl, CCC, May 28, 2008

External Links

Search Extension from Bruce Moreland's Programming Topics
Programmer Corner - Extension Techniques in REBEL (recaptures) by Ed Schröder ^[4]
The automatic recapture... from ChessBase News, January 02, 2010
Exchange (chess) from Wikipedia
Recapture from Wikipedia 1930 drama by Preston Sturges
reCAPTCHA from Wikipedia

References

^ Re: Recapture Extensions by Ulrich Türke, CCC, June 02, 2001
^ Re: Search extensions at promising trajectories by Robert Hyatt, CCC, May 29, 2008
^ Re: extensions by Edsel Apostol, Winboard Forum, August 27, 2008
^ How Rebel Plays Chess is also available as pdf reprint

What links here?

Page	Date Edited
Abyss	Aug 5, 2017
Andrew Williams	Jan 7, 2016
Bringer	Jul 14, 2014
Bruja	Feb 3, 2015
Capture Extensions	Oct 26, 2012
Captures	Oct 1, 2017
Chepla	May 10, 2013
Chess Guru	Mar 4, 2017
Chess Wizard	Dec 22, 2014
Chester	Feb 15, 2014
Chezzz	Jan 20, 2013
Counter	Nov 13, 2017
Cumulus	Jan 7, 2016
DanaSah	Oct 9, 2017
Djinn	Feb 8, 2016
Duck	Dec 12, 2016
Edsel Apostol	Nov 2, 2016
Exacto	Oct 3, 2015
Extensions	Apr 19, 2018
Falcon	Sep 2, 2016
Ferret	Jan 7, 2016
Fischerle	Aug 21, 2017
Flux	Jan 12, 2016
GES	Sep 13, 2015
Gibbon	Dec 23, 2014
Greko	Feb 27, 2018
Horizon	Mar 17, 2013
Move Ordering	Feb 27, 2018
Murka	Nov 11, 2016
Muse	May 17, 2016
Nemorino	Dec 21, 2017
Pepito	Nov 27, 2014
Prophet	Sep 30, 2017
Rajah	Sep 12, 2012
RattateChess	Dec 2, 2014
Recapture Extensions	Feb 2, 2013
RuyDos	Feb 17, 2018
Scott Gasch	Nov 29, 2016
Searcher	Sep 26, 2016
Selectivity	Jan 12, 2018
SharpChess	Jun 6, 2017
Shield	May 17, 2017
Singular Extensions	Jan 9, 2018
Sloppy	Sep 17, 2016
Slow Chess	May 17, 2016
SOS	Apr 5, 2017
Spector	Nov 11, 2016
Spike	Jan 7, 2016
Tactics	Jan 12, 2018
Tao	Jan 8, 2016
Thor's Hammer	Nov 23, 2013
Touch	Dec 12, 2016
Warrior	Feb 23, 2015
WChess	Jan 7, 2016
Wing	Oct 26, 2017
Witz	Nov 14, 2017
YChess	Feb 25, 2018

Up one Level

Reverse Futility Pruning

GerdIsenberg — Fri, 02 Jun 2017 19:37:04 GMT

Home * Search * Selectivity * Pruning * Reverse Futility Pruning

Reverse Futility Pruning, (Static Null Move Pruning)
postpones a extended futility pruning condition applied at [pre]... pre frontier nodes to skip moves inside its move loop if material balance plus gain of the move and safety margin does not improve alpha, ...

int search( int alpha, int beta, ... ) {
  bool fprune = ...;
  int margin = ...;
  for ( all moves ) {
    if ( fprune && materialBalance + margin + gain(move) <= alpha ) continue;
    make( move );
    score = -search(-beta, -alpha, ...);
    unmake( move );
    ...
  }
  ...
}

... with the "reversed" or negamaxed fail-high condition of a more reliable score minus safety margin greater or equal than beta - after making the move, and calling the child and its static evaluation. Thus, Reverse Futility Pruning relies on the null move observation, and is a generalisation of standing pat at quiescent nodes, or a special case of null move pruning without explicitly making one ^[1]:

int search( int alpha, int beta, ... ) {
  int eval = evaluate(...);
  int margin = ...;
  if (... && eval - margin >= beta) {
    return eval - margin; /* fail soft */
  ...
}

Forum Posts

2008 ...

Toga/Glaurung/Strelka Prunings/Reductions by Edsel Apostol, CCC, January 31, 2008 » Toga, Glaurung, Strelka, Reductions
Null move in quiescence search idea from Don Beal, 1986 by Eelco de Groot, CCC, August 17, 2009 » Quiescence Search, Don Beal

2010 ...

static null move pruning is stockfish by Tom King, CCC, June 13, 2010 » Stockfish
Reverse Futility Pruning by Matthew R. Brades, CCC, December 02, 2011
mate distance pruning problems and static null move pruning by Pierre Bokma, CCC, December 04, 2011 » Mate Distance Pruning

2015 ...

Futile attempts at futility pruning by Martin Fierz, CCC, March 27, 2016
Futility prunning by Daniel Anulliero, CCC, August 11, 2016 » Futility Pruning
Static null move pruning by Fernando Tenorio, CCC, December 18, 2016
Static NULL Move by thevinenator, OpenChess Forum, December 26, 2016 » CPW-Engine_search
Futility pruning ? by Mahmoud Uthman, CCC, March 04, 2017 » Futility Pruning
increasing futility prunning depth by Alexandru Mosoi, CCC, April 28, 2017

References

^ Re: Reverse Futility Pruning by Don Dailey, CCC, December 02, 2011

What links here?

Page	Date Edited
Amoeba	Mar 19, 2018
Carballo	Oct 2, 2016
CPW history	Jan 1, 2015
CPW-Engine_search	Feb 4, 2017
Daniel Anulliero	Oct 3, 2017
Demolito	Mar 1, 2018
Dorpsgek	Apr 2, 2018
Ethereal	Mar 20, 2018
Futility Pruning	Aug 30, 2017
Gogobello	Jul 30, 2017
Hakkapeliitta	Apr 26, 2016
ISA	Apr 2, 2018
Laser	Dec 27, 2017
Martin Fierz	Apr 26, 2018
Marvin	Feb 10, 2018
Mate Distance Pruning	Jun 2, 2017
Matthew R. Brades	Jun 9, 2017
Null Move Observation	Dec 30, 2015
Null Move Pruning	Dec 2, 2017
Pruning	Jan 1, 2018
Reverse Futility Pruning	Jun 2, 2017
Selectivity	Jan 12, 2018
Shield	May 17, 2017
Stockfish	Apr 7, 2018
Texel	Oct 9, 2017
tomitankChess	Dec 8, 2017
Vajolet	Jan 25, 2018
Wasp	Nov 24, 2017
Winter	Jan 23, 2018

Up one Level

Selectivity

GerdIsenberg — Fri, 12 Jan 2018 09:28:18 GMT

Home * Search * Selectivity

Selectivity gives a whiff of Shannon's Type B search to Shannon's Type A or brute-force. The goal is to search "interesting" and forced branches which are or are likely to become part of the principal variation deeper than nominal, but to reduce uninteresting branches.

Extensions

Pruning

Reductions

Publications

1970 ...

Russell M. Church, Kenneth W. Church (1977). Plans, Goals, and Search Strategies for the Selection of a Move in Chess. Chess Skill in Man and Machine

1980 ...

Hermann Kaindl (1983). Searching to Variable Depth in Computer Chess. Proceedings of IJCAI 83, pp. 760-762. Karlsruhe. pdf
Don Beal (1986). Selective Search without Tears. ICCA Journal, Vol. 9, No. 2
Hermann Kaindl, Helmut Horacek, Marcus Wagner (1986). Selective Search versus Brute Force. ICCA Journal, Vol. 9, No. 3
David Levy, David Broughton, Mark Taylor (1989). The SEX Algorithm in Computer Chess. ICCA Journal, Vol. 12, No. 1

1990 ...

Chun Ye (1992). Experiments in Selective Search Extensions. MSc. thesis, Department of Computing Science, University of Alberta, pdf
Chun Ye, Tony Marsland (1992). Selective Extensions in Game-Tree Search. Heuristic Programming in AI 3
Javier Ros Padilla (1994). Estimating Asymmetry and Selectivity in Chess Programs. ICCA Journal, Vol. 17, No. 1 ^[1]
Deniz Yuret (1994). The Principle of Pressure in Chess. TAINN 1994
Lev Finkelstein, Shaul Markovitch (1998). Learning to Play Chess Selectively by Acquiring Move Patterns. ICCA Journal, Vol. 21, No. 2, pdf
Rainer Feldmann, Burkhard Monien (1998). Selective Game Tree Search on a Cray T3E. ps

2000 ...

Paul E. Utgoff, Richard P. Cochran (2000). A Least-Certainty Heuristic for Selective Search. CG 2000, pdf » LCF
Yngvi Björnsson, Tony Marsland (2000). Selective Depth-First Search Methods. in Jaap van den Herik, Hiroyuki Iida (eds.) (2000). Games in AI Research. Universiteit Maastricht, pdf preprint
Ulf Lorenz, Burkhard Monien (2002). The Secret of Selective Game Tree Search, When Using Random-Error Evaluations. Proceedings of 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pdf
Pálmi Skowronski (2009). Gradual Focus: A Method for Automated Feature Discovery in Selective Search. MSc-Thesis, pdf

2010 ...

Omid David, Moshe Koppel, Nathan S. Netanyahu (2010). Optimizing Selective Search in Chess. ICML Workshop on Machine Learning and Games, Haifa, Israel
Maarten Schadd (2011). Selective Search in Games of Different Complexity. Ph.D. Thesis. Department of Knowledge Engineering, Maastricht University

Forum Posts

1998 ...

A new selective heuristic? by Frank Schneider, CCC, June 21, 1998 » Reductions

2000 ...

Selective Searching by Bob Durrett, rgcc, November 19, 2000
pruning vs extensions vs qsearch - are these all effectively the same? by Scott Farrell, CCC, November 27, 2002
Evaluation-based Reductions and/or Extensions by Tom Likens, CCC, December 28, 2003
extensions + reductions + pruning = confusion by Johan de Koning, CCC, March 24, 2004 (was Shredder 8 secret: search depth?)
Extension - Reductions and threats by mjlef, Winboard Forum, May 17, 2006
Extensions/Reductions by Luca Hemmerich, CCC, September 28, 2009

2010 ...

Nullmove vs classic selective search by Ed Schröder, CCC, August 04, 2012 ^[2]
Houdini 3 reducing the depth feature by Maurizio Maglio, CCC, October 17, 2012 » Houdini
selective depth definition by Uri Blass, CCC, February 13, 2014 » Stockfish
Is modern chess software lossless or lossy? by Meni Rosenfeld, CCC, January 10, 2018 » Playing Strength

External Links

Selective Search Techniques in REBEL (introduction) from Programmer Corner by Ed Schröder ^[3] » Rebel
Living Being Quintet - On the heights, Altitude Jazz Festival 2015, YouTube Video
Vincent Peirani, Émile Parisien, Tony Paeleman, Julien Herné, Yoann Serra

References

^ ICCA Journal, Vol. 17, No. 1 by Jos Uiterwijk, rgcc, May 02, 1994
^ Selective Search Techniques in REBEL (introduction) from Programmer Corner by Ed Schröder
^ Nullmove vs classic selective search by Ed Schröder, CCC, August 04, 2012

What links here?

Page	Date Edited
Abyss	Aug 5, 2017
ACM 1991	Nov 25, 2017
AEL-Pruning	Jun 22, 2013
AI Chess	Jan 7, 2016
Alan Turing	Feb 8, 2017
Alpha-Beta	Jan 28, 2018
Anaconda	Jul 4, 2015
Andscacs	Jan 16, 2018
B*	Nov 27, 2017
Bagatur	Sep 10, 2016
BigLion	Sep 28, 2016
Bobcat	Jun 27, 2017
Botvinnik-Markoff Extension	Nov 27, 2015
BP	Jan 7, 2016
Brainless	Jun 24, 2017
Brute-Force	Jul 27, 2017
CAPS	Dec 23, 2017
Capture Extensions	Oct 26, 2012
Carballo	Oct 2, 2016
Chat	Jan 7, 2016
Check Extensions	Apr 19, 2018
Cheese	Feb 17, 2018
Chenard	Sep 5, 2015
Cheng	Jul 30, 2017
Chess	Jan 21, 2018
Chess Player 2150	Jan 1, 2017
Chess Simulator	Dec 7, 2016
Chess Wizard	Dec 22, 2014
chess22k	Apr 23, 2018
ChessBrainVB	Jun 24, 2017
ChessV	Jan 21, 2018
Chump	Jan 31, 2016
Clash	May 19, 2016
Claude Shannon	Apr 30, 2016
Coiled	Mar 12, 2017
Comet	Jan 8, 2016
Cumulus	Jan 7, 2016
Defenchess	Mar 18, 2018
Delicate Brute	Jun 7, 2016
Delta Pruning	Dec 2, 2014
Demolito	Mar 1, 2018
Deniz Yuret	Aug 9, 2016
Depth	Feb 25, 2018
Diablo	May 17, 2016
Diep	Jan 28, 2018
DisasterArea	Mar 27, 2017
Dorpsgek	Apr 2, 2018
Double Null Move	May 8, 2015
Dragon FR	Sep 9, 2016
Enhanced Forward Pruning	Oct 21, 2014
Enigma	Feb 9, 2015
Ethereal	Mar 20, 2018
Extensions	Apr 19, 2018
Eye Movements	Jul 22, 2015
Fail-High Reductions	Mar 6, 2014
Francesca	Jan 7, 2016
Fruit Reloaded	Dec 8, 2017
Futility Pruning	Aug 30, 2017
Gandalf	Jan 21, 2018
Garbochess	Sep 23, 2017
Garbochess-JS	Sep 23, 2017
Genesis NL	Dec 12, 2016
Gerhard Trippen	Jun 8, 2015
Gibbon	Dec 23, 2014
Gk	Oct 9, 2017
Glaurung	Mar 14, 2017
Gogobello	Jul 30, 2017
Golch	Dec 7, 2017
GopherCheck	Feb 3, 2017
Grandmaster Chess	Dec 7, 2016
Hagrid	Apr 12, 2016
HAL	Jun 14, 2016
Hannibal	Oct 4, 2017
History Leaf Pruning	Apr 15, 2013
Houdini	Apr 14, 2018
Ifrit	Feb 7, 2016
ISA	Apr 2, 2018
Javier Ros Padilla	Sep 2, 2015
JikChess	Nov 29, 2015
Kholin	Jan 3, 2018
KnockOut	Sep 20, 2016
Knowledge	Jul 22, 2017
Komodo	Mar 6, 2018
Laser	Dec 27, 2017
Late Move Reduction Test Results	Sep 25, 2017
Late Move Reductions	Sep 25, 2017
LittleThought	Nov 7, 2016
LL Chess	May 23, 2015
Lozza	Apr 18, 2018
Mark Lefler	Nov 23, 2017
Marvin	Feb 10, 2018
Mate Distance Pruning	Jun 2, 2017
Mate Threat Extensions	Apr 14, 2012
Mephisto (H)	Dec 18, 2017
Mephisto Lyon	Sep 1, 2017
Mephisto Mondial	Jun 23, 2017
Mephisto Portorose	Sep 1, 2017
Mephisto Roma	Sep 1, 2017
Mephisto Vancouver	Sep 2, 2017
Merlin	Jan 20, 2018
Multi-Cut	Jul 4, 2016
Murka	Nov 11, 2016
Napoleon	Jun 25, 2017
Nebula	Feb 7, 2015
Nemorino	Dec 21, 2017
Neural Networks	Mar 12, 2018
Node Types	Oct 22, 2017
Nodes per second	Feb 28, 2018
Nona	Jan 7, 2016
Novag Expert	Aug 3, 2013
Novag Forte	Aug 3, 2013
Now	Jan 7, 2016
Null Move Pruning	Dec 2, 2017
Null Move Pruning Test Results	May 16, 2015
Null Move Reductions	Jun 22, 2015
Obender	Apr 17, 2016
Odd-Even Effect	May 19, 2017
Omid David	Jan 2, 2017
One Reply Extensions	Dec 31, 2014
Othello	Jan 4, 2018
Overloading	May 5, 2017
Parity Pruning	Jan 14, 2013
Passed Pawn Extensions	May 11, 2015
Planning	Feb 12, 2018
Playing Strength	Mar 31, 2018
Ply	Jan 27, 2014
Point Value by Regression Analysis	Aug 26, 2017
ProbCut	Mar 25, 2016
Prophet	Sep 30, 2017
Pruning	Jan 1, 2018
Psion	Mar 20, 2017
PV Extensions	May 4, 2013
RattateChess	Dec 2, 2014
Razoring	Oct 5, 2015
Recapture Extensions	Feb 2, 2013
RedQueen	Nov 13, 2017
Reductions	Nov 1, 2017
Reverse Futility Pruning	Jun 2, 2017
Rex	Jan 7, 2016
RexChess	Dec 7, 2016
Richard Lang	Jan 7, 2016
Richard P. Cochran	Mar 28, 2015
Robocide	May 11, 2016
RuyDos	Feb 17, 2018
Sayuri	Oct 1, 2017
Search	Feb 1, 2018
Selective Search	Oct 24, 2016
Selectivity	Jan 12, 2018
SEX Algorithm	Nov 25, 2014
SharpChess	Jun 6, 2017
Shield	May 17, 2017
Shogi	Feb 19, 2018
Singular Extensions	Jan 9, 2018
Sloppy	Sep 17, 2016
Smash	May 11, 2016
Snitch	Apr 7, 2016
Stockfish	Apr 7, 2018
Tactics	Jan 12, 2018
Teki	Mar 29, 2018
The King	Jan 21, 2018
TRACE	Feb 14, 2013
Triangular PV-Table	Jun 12, 2017
Turochamp	Dec 14, 2017
Type B Strategy	Jul 19, 2016
Uncertainty Cut-Offs	Jul 21, 2015
Vajolet	Jan 25, 2018
WCCC 1986	Jul 27, 2017
Wing	Oct 26, 2017
Winter	Jan 23, 2018
WyldChess	Mar 10, 2018
Xpdnt	Sep 13, 2015
Zurichess	Mar 12, 2018

Up one level

Wikispaces : chessprogramming - items matching description

AEL-Pruning

Table of Contents

Pseudo-Code

References

What links here?

Botvinnik-Markoff Extension

Table of Contents

See also

Forum Posts

References

What links here?

Capture Extensions

Table of Contents

See also

Publications

Forum Posts

External Links

References

What links here?

Delta Pruning

Table of Contents

Sample Code

See also

Forum Posts

External Links

What links here?

Enhanced Forward Pruning

Table of Contents

Pruning in the Null-Window Search

Cut-Node

All-Node

Four Additions

Pseudo Code

See also

Publications

Forum Posts

References

What links here?

Extensions

Table of Contents

Classification

Types

Fractional Extensions

Conditions/Restrictions

Non-reductions

See also

Publications

1980 ...

1990 ...

2000 ...

2010 ...

Forum Posts

1996 ...

2000 ...

2005 ...

2010 ...

2015 ...

External Links

Search Extension

Misc

References

Fail-High Reductions

Table of Contents

See also

Publications

Forum Posts

References

What links here?

Futility Pruning

Table of Contents

Conditions

Extended Futility Pruning

Move Count Based Pruning

Deep Futility Pruning

See also

Publications

Forum Posts

1995 ...

2000 ...