Multi-Cut

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Selectivity * Pruning * Multi-Cut

Katsushika Hokusai - Master Pine Pruner [1]

Multi-Cut,
a speculative pruning mechanism for chessplaying programs created by Yngvi Björnsson [2] [3]. 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 [4] . In his 2011 B.Sc. thesis Investigation of Multi-Cut Pruning in Game-Tree Search [5], Hrafn Eiríksson proposed to apply Multi-cut if a transposition table probe indicates a beta-cutoff without sufficient draft stored.

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;
}

See also

Multi–ProbCut

Publications

Forum Posts

External Links

References

  1. 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
  2. Yngvi Björnsson, Tony Marsland (1998). Multi-cut Pruning in Alpha-Beta Search. CG 1998
  3. Yngvi Björnsson, Tony Marsland (2001). Multi-cut Alpha-Beta Pruning in Game Tree Search. Theoretical Computer Science, Vol. 252, pdf
  4. Mark Winands, Jaap van den Herik, Jos Uiterwijk, Erik van der Werf (2003). Enhanced forward pruning. pdf
  5. Hrafn Eiríksson (2011). Investigation of Multi-Cut Pruning in Game-Tree Search. B.Sc. Thesis, Reykjavík University, pdf
  6. CHESS AND MATHEMATICS - Workshop Dresden, 21st - 23rd November 2008
  7. Workshop Chess and Mathematics (pdf) agenda and abstracts

Up one Level