Difference between revisions of "Enhanced Forward Pruning"

From Chessprogramming wiki
Jump to: navigation, search
 
Line 1: Line 1:
 
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Pruning]] * Enhanced Forward Pruning'''
 
'''[[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> ]]  
+
[[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|[[:Category:Hannah Höch|Hannah Höch]], Cut with the Dada ... <ref>[[:Category:Hannah Höch|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/>
 
'''Enhanced Forward Pruning''',<br/>
Line 90: Line 90:
  
 
'''[[Pruning|Up one Level]]'''
 
'''[[Pruning|Up one Level]]'''
 +
[[Category:Hannah Höch]]

Latest revision as of 22:30, 2 November 2019

Home * Search * Selectivity * Pruning * Enhanced Forward Pruning

Hannah Höch, Cut with the Dada ... [1] [2]

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

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

  1. 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).
  2. 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.
  3. 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.
  4. 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
   ...
}

See also

Publications

Forum Posts

References

Up one Level