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 betabound. 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.

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-forceminimax 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.

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

Home * Search * Selectivity * Pruning * Multi-CutMulti-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. thesisInvestigation 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.^{[5]}## Table of Contents

## 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:## See also

Multi–ProbCut

## Publications

1998).Multi-cut Pruning in Alpha-Beta Search. CG 1998, see also MC2001 for an expanded version.2000).Risk Management in Game-tree Pruning. Information Sciences, Vol. 122, No. 1, pdf2001).Multi-cut Alpha-Beta Pruning in Game Tree Search.Theoretical Computer Science, Vol. 252, pdf2002).Selective Depth-First Game-Tree Search. Ph.D. thesis, University of Alberta2003).Enhanced forward pruning.pdf2011).Investigation of Multi-Cut Pruning in Game-Tree Search. B.Sc. Thesis, Reykjavík University, pdf## Forum Posts

## External Links

## References

1998).Multi-cut Pruning in Alpha-Beta Search. CG 19982001).Multi-cut Alpha-Beta Pruning in Game Tree Search.Theoretical Computer Science, Vol. 252, pdf2003).Enhanced forward pruning.pdf2011).Investigation of Multi-Cut Pruning in Game-Tree Search. B.Sc. Thesis, Reykjavík University, pdf## What links here?

Up one Level