25,161
edits
Changes
Created page with "'''Home * Search * Selectivity * Pruning * Enhanced Forward Pruning''' FILE:270px-Hoch-Cut_With_the_Kitchen_Knife.jpg|border|right|thumb|link=http..."
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Pruning]] * Enhanced Forward Pruning'''
[[FILE:270px-Hoch-Cut_With_the_Kitchen_Knife.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/File:Hoch-Cut_With_the_Kitchen_Knife.jpg|[[Arts#Hoech|Hannah Höch]], Cut with the Dada ... <ref>[[Arts#Hoech|Hannah Höch]] - [https://en.wikipedia.org/wiki/File:Hoch-Cut_With_the_Kitchen_Knife.jpg Cut with the Dada Kitchen Knife through the Last Weimar Beer-Belly Cultural Epoch in Germany], [https://en.wikipedia.org/wiki/Collage Collage] of pasted papers, 90×144 cm, 1919, [https://en.wikipedia.org/wiki/National_Gallery_%28Berlin%29 National Gallery], [https://en.wikipedia.org/wiki/Berlin_State_Museums Berlin State Museums], [https://en.wikipedia.org/wiki/Hannah_H%C3%B6ch Hannah Höch from Wikipedia], [https://en.wikipedia.org/wiki/Dada Dada from Wikipedia], [https://en.wikipedia.org/wiki/Weimar_culture Weimar culture from Wikipedia]</ref> <ref>[http://lemondedekitchi.blogspot.de/2014/10/great-women-1-hannah-hoch.html le monde de kitchi: Great Women #1: Hannah Höch] (German)</ref> ]]
'''Enhanced Forward Pruning''',<br/>
a pruning technique introduced by [[Mark Winands]] et al. in 2003 <ref>[[Mark Winands]], [[Jaap van den Herik]], [[Jos Uiterwijk]], [[Erik van der Werf]] ('''2003'''). ''Enhanced forward pruning.'' [http://www.personeel.unimaas.nl/m-winands/documents/Enhanced%20forward%20pruning.pdf pdf]</ref> , which applies forward pruning like [[Null Move Pruning|null move pruning]] and [[Multi-Cut|multi-cut]] <ref>[[Yngvi Björnsson]] and [[Tony Marsland]] ('''2001'''). ''Multi-cut Alpha-Beta Pruning in Game Tree Search.'' Theoretical Computer Science, Vol. 252, pp. 177-196. [http://www.ru.is/faculty/yngvi/pdf/BjornssonM01a.pdf pdf]</ref> not only at expected [[Node Types#CUT|Cut-nodes]], but also at expected [[Node Types#ALL|All-nodes]] based on considerations and modifications on the [[Principal Variation Search|PVS]] framework.
=Pruning in the Null-Window Search=
It has become practice to use forward-pruning methods only in the [[Principal Variation Search#ZWS|NWS]] part of the PVS framework. The idea is that it is too risky to prune forward at an expected [[Node Types#PV|PV-node]], because a possible mistake causes an immediate change of the [[Principal variation|principal variation]].
==Cut-Node==
If one erroneously prunes forward at some [[Node Types#CUT|Cut-node]] and the resulting score is backed up all the way to a PV-node, it obtains a [[Fail-Low|fail-low]], due to the odd ply distance to its [[Node Types#PV|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 [[Node Types#ALL|All-node]] and the resulting score is backed up all the way to a PV-node, it obtain a [[Fail-High|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 [[Principal variation|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 [[Beta-Cutoff|cutoff]] at the PV-node lying above, the forward-pruning mechanism should return a value equal to [[Beta|β]] 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 [[Principal Variation Search#ZWS|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|lower bound]].
# Cut-nodes where a [[Fail-Low|fail-low]] has occurred with a value equal to α are not stored in the [[Transposition Table|transposition table]] because their values are uncertain.
=Pseudo Code=
<pre>
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
...
}
</pre>
=See also=
* [[Multi-Cut]]
* [[Node Types]]
* [[Null Move Pruning]]
* [[Principal Variation Search]]
* [[ProbCut]]
=Publications=
* [[Mark Winands]], [[Jaap van den Herik]], [[Jos Uiterwijk]], [[Erik van der Werf]] ('''2003, 2005'''). ''[http://www.sciencedirect.com/science/article/pii/S0020025504002750 Enhanced forward pruning].'' [http://www.sciencedirect.com/science/journal/00200255/175/4 Information Sciences, Vol. 175, No. 4], [http://www.personeel.unimaas.nl/m-winands/documents/Enhanced%20forward%20pruning.pdf pdf preprint]
=Forum Posts=
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6392 NMP on ALL nodes] by [[Onno Garms]], [[Computer Chess Forums|Winboard Forum]], April 15, 2007 » [[Null Move Pruning]], [[Node Types#ALL|All Nodes]]
=References=
<references />
'''[[Pruning|Up one Level]]'''
[[FILE:270px-Hoch-Cut_With_the_Kitchen_Knife.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/File:Hoch-Cut_With_the_Kitchen_Knife.jpg|[[Arts#Hoech|Hannah Höch]], Cut with the Dada ... <ref>[[Arts#Hoech|Hannah Höch]] - [https://en.wikipedia.org/wiki/File:Hoch-Cut_With_the_Kitchen_Knife.jpg Cut with the Dada Kitchen Knife through the Last Weimar Beer-Belly Cultural Epoch in Germany], [https://en.wikipedia.org/wiki/Collage Collage] of pasted papers, 90×144 cm, 1919, [https://en.wikipedia.org/wiki/National_Gallery_%28Berlin%29 National Gallery], [https://en.wikipedia.org/wiki/Berlin_State_Museums Berlin State Museums], [https://en.wikipedia.org/wiki/Hannah_H%C3%B6ch Hannah Höch from Wikipedia], [https://en.wikipedia.org/wiki/Dada Dada from Wikipedia], [https://en.wikipedia.org/wiki/Weimar_culture Weimar culture from Wikipedia]</ref> <ref>[http://lemondedekitchi.blogspot.de/2014/10/great-women-1-hannah-hoch.html le monde de kitchi: Great Women #1: Hannah Höch] (German)</ref> ]]
'''Enhanced Forward Pruning''',<br/>
a pruning technique introduced by [[Mark Winands]] et al. in 2003 <ref>[[Mark Winands]], [[Jaap van den Herik]], [[Jos Uiterwijk]], [[Erik van der Werf]] ('''2003'''). ''Enhanced forward pruning.'' [http://www.personeel.unimaas.nl/m-winands/documents/Enhanced%20forward%20pruning.pdf pdf]</ref> , which applies forward pruning like [[Null Move Pruning|null move pruning]] and [[Multi-Cut|multi-cut]] <ref>[[Yngvi Björnsson]] and [[Tony Marsland]] ('''2001'''). ''Multi-cut Alpha-Beta Pruning in Game Tree Search.'' Theoretical Computer Science, Vol. 252, pp. 177-196. [http://www.ru.is/faculty/yngvi/pdf/BjornssonM01a.pdf pdf]</ref> not only at expected [[Node Types#CUT|Cut-nodes]], but also at expected [[Node Types#ALL|All-nodes]] based on considerations and modifications on the [[Principal Variation Search|PVS]] framework.
=Pruning in the Null-Window Search=
It has become practice to use forward-pruning methods only in the [[Principal Variation Search#ZWS|NWS]] part of the PVS framework. The idea is that it is too risky to prune forward at an expected [[Node Types#PV|PV-node]], because a possible mistake causes an immediate change of the [[Principal variation|principal variation]].
==Cut-Node==
If one erroneously prunes forward at some [[Node Types#CUT|Cut-node]] and the resulting score is backed up all the way to a PV-node, it obtains a [[Fail-Low|fail-low]], due to the odd ply distance to its [[Node Types#PV|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 [[Node Types#ALL|All-node]] and the resulting score is backed up all the way to a PV-node, it obtain a [[Fail-High|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 [[Principal variation|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 [[Beta-Cutoff|cutoff]] at the PV-node lying above, the forward-pruning mechanism should return a value equal to [[Beta|β]] 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 [[Principal Variation Search#ZWS|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|lower bound]].
# Cut-nodes where a [[Fail-Low|fail-low]] has occurred with a value equal to α are not stored in the [[Transposition Table|transposition table]] because their values are uncertain.
=Pseudo Code=
<pre>
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
...
}
</pre>
=See also=
* [[Multi-Cut]]
* [[Node Types]]
* [[Null Move Pruning]]
* [[Principal Variation Search]]
* [[ProbCut]]
=Publications=
* [[Mark Winands]], [[Jaap van den Herik]], [[Jos Uiterwijk]], [[Erik van der Werf]] ('''2003, 2005'''). ''[http://www.sciencedirect.com/science/article/pii/S0020025504002750 Enhanced forward pruning].'' [http://www.sciencedirect.com/science/journal/00200255/175/4 Information Sciences, Vol. 175, No. 4], [http://www.personeel.unimaas.nl/m-winands/documents/Enhanced%20forward%20pruning.pdf pdf preprint]
=Forum Posts=
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6392 NMP on ALL nodes] by [[Onno Garms]], [[Computer Chess Forums|Winboard Forum]], April 15, 2007 » [[Null Move Pruning]], [[Node Types#ALL|All Nodes]]
=References=
<references />
'''[[Pruning|Up one Level]]'''
