Multi-Cut
Home * Search * Selectivity * Pruning * Multi-Cut
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.
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:
// 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
Publications
- Yngvi Björnsson, Tony Marsland (1998). Multi-cut Pruning in Alpha-Beta Search. CG 1998, see also MC2001 for an expanded version.
- Yngvi Björnsson, Tony Marsland (2000). Risk Management in Game-tree Pruning. Information Sciences, Vol. 122, No. 1, pdf
- Yngvi Björnsson, Tony Marsland (2001). Multi-cut Alpha-Beta Pruning in Game Tree Search. Theoretical Computer Science, Vol. 252, pdf
- Yngvi Björnsson (2002). Selective Depth-First Game-Tree Search. Ph.D. thesis, University of Alberta
- Mark Winands, Jaap van den Herik, Jos Uiterwijk, Erik van der Werf (2003). Enhanced forward pruning. pdf
- Hrafn Eiríksson (2011). Investigation of Multi-Cut Pruning in Game-Tree Search. B.Sc. Thesis, Reykjavík University, pdf
Forum Posts
- Mult-cut, SE and ETC by Ricardo Gibert, CCC, August 05, 2010 » Singular Extensions, Enhanced Transposition Cutoff
- Re: Some thoughts on QS by Vincent Diepeveen, CCC, July 30, 2012
- Multi-cut and fail-soft by Matthew R. Brades, CCC, June 30, 2016 » Fail-Soft
External Links
- Björk - Big Time Sensuality, YouTube Video
References
- ↑ 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
- ↑ Yngvi Björnsson, Tony Marsland (1998). Multi-cut Pruning in Alpha-Beta Search. CG 1998
- ↑ Yngvi Björnsson, Tony Marsland (2001). Multi-cut Alpha-Beta Pruning in Game Tree Search. Theoretical Computer Science, Vol. 252, pdf
- ↑ Mark Winands, Jaap van den Herik, Jos Uiterwijk, Erik van der Werf (2003). Enhanced forward pruning. pdf
- ↑ Hrafn Eiríksson (2011). Investigation of Multi-Cut Pruning in Game-Tree Search. B.Sc. Thesis, Reykjavík University, pdf
- ↑ CHESS AND MATHEMATICS - Workshop Dresden, 21st - 23rd November 2008
- ↑ Workshop Chess and Mathematics (pdf) agenda and abstracts