Difference between revisions of "Delta Pruning"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
(One intermediate revision by the same user not shown) | |||
Line 8: | Line 8: | ||
=Sample Code= | =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- | + | 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): |
<pre> | <pre> | ||
// get a "stand pat" score | // get a "stand pat" score | ||
Line 44: | Line 44: | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=38997 Inverse delta pruning] by [[Marcel van Kervinck]], [[CCC]], May 06, 2011 | * [http://www.talkchess.com/forum/viewtopic.php?t=38997 Inverse delta pruning] by [[Marcel van Kervinck]], [[CCC]], May 06, 2011 | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=46568 Qsearch Delta Pruning Rate?] by [[Srdja Matovic]], [[CCC]], December 24, 2012 | * [http://www.talkchess.com/forum/viewtopic.php?t=46568 Qsearch Delta Pruning Rate?] by [[Srdja Matovic]], [[CCC]], December 24, 2012 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=64803 Delta pruning Mate error] by [[Tamás Kuzmics]], [[CCC]], August 04, 2017 | ||
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73180 Delta pruning test] by Tom Reinitz, [[CCC]], February 25, 2020 | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73180 Delta pruning test] by Tom Reinitz, [[CCC]], February 25, 2020 | ||
Latest revision as of 10:37, 25 September 2020
Home * Search * Selectivity * Pruning * Delta Pruning
Delta Pruning,
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 material swing. int BIG_DELTA = 975; // queen value if ( isPromotingPawn() ) BIG_DELTA += 775; if ( val < alpha - BIG_DELTA ) { return alpha; } if( alpha < val ) alpha = val;
See also
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
- Delta pruning Mate error by Tamás Kuzmics, CCC, August 04, 2017
- Delta pruning test by Tom Reinitz, CCC, February 25, 2020