25,161
edits
Changes
Created page with "'''Home * Search * Selectivity * Pruning * Multi-Cut''' FILE:Master Pine Pruner LACMA M.2006.136.205a-b.jpg|border|right|thumb|[[Arts#Hokusai|Kats..."
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Pruning]] * Multi-Cut'''
[[FILE:Master Pine Pruner LACMA M.2006.136.205a-b.jpg|border|right|thumb|[[Arts#Hokusai|Katsushika Hokusai]] - Master Pine Pruner <ref>[[Arts#Hokusai|Katsushika Hokusai]] - [http://commons.wikimedia.org/wiki/File:Master_Pine_Pruner_LACMA_M.2006.136.205a-b.jpg Master Pine Pruner] cropped, ca. 1802, Series: Famous Views of the Eastern Capital, woodcuts, Current location: [https://en.wikipedia.org/wiki/Los_Angeles_County_Museum_of_Art Los Angeles County Museum of Art], [https://commons.wikimedia.org/wiki/Category:Katsushika_Hokusai Category:Katsushika Hokusai], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''Multi-Cut''',<br/>
a speculative pruning mechanism for chessplaying programs created by [[Yngvi Björnsson]] <ref>[[Yngvi Björnsson]], [[Tony Marsland]] ('''1998'''). ''[http://link.springer.com/chapter/10.1007/3-540-48957-6_2 Multi-cut Pruning in Alpha-Beta Search]''. [[CG 1998]]</ref> <ref>[[Yngvi Björnsson]], [[Tony Marsland]] ('''2001'''). ''Multi-cut Alpha-Beta Pruning in Game Tree Search.'' Theoretical Computer Science, Vol. 252, [http://www.ru.is/faculty/yngvi/pdf/BjornssonM01a.pdf pdf]</ref>. 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 [[Node Types#CUT|Cut-node]] is not singular, that is multiple (C) moves [[Fail-High|fail high]], and to prune the whole subtree in that case by returning the hard [[Beta|beta]] [[Bound|bound]]. [[Mark Winands|Mark Winands']] [[Enhanced Forward Pruning|enhanced forward pruning]] applies Multi-Cut even at expected [[Node Types#ALL|All-nodes]], with slight modifications on a [[Principal Variation Search|PVS]] framework <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> . In his 2011 B.Sc. thesis ''Investigation of Multi-Cut Pruning in Game-Tree Search'' <ref>[[Hrafn Eiríksson]] ('''2011'''). ''Investigation of Multi-Cut Pruning in Game-Tree Search''. B.Sc. Thesis, [https://en.wikipedia.org/wiki/Reykjav%C3%ADk_University Reykjavík University], [http://skemman.is/en/stream/get/1946/9180/22971/1/research-report.pdf pdf]</ref>, [[Hrafn Eiríksson]] proposed to apply Multi-cut if a [[Transposition Table|transposition table]] probe indicates a [[Beta-Cutoff|beta-cutoff]] without sufficient [[Depth|draft]] stored.
=Abstract=
from the [[Workshop Chess and Mathematics]], 2008 <ref>[http://www.math.tu-dresden.de/num/chess2008/index-en.html CHESS AND MATHEMATICS - Workshop Dresden, 21st - 23rd November 2008]</ref> <ref>[http://www.math.tu-dresden.de/num/chess2008/abstracts.pdf Workshop Chess and Mathematics] (pdf) agenda and abstracts</ref> :
The [[Alpha-Beta|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|brute-force]] [[Minimax|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|root]] of the [[Search Tree|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|null window]]- or [[Principal Variation Search#ZWS|zero window search]] of a [[Fail-Hard|fail-hard]] [[Principal Variation Search|PVS]] framework, applied at expected [[Node Types#CUT|Cut-nodes]]:
<pre>
// 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;
}
</pre>
=See also=
* [[Enhanced Forward Pruning]]
* [[Null Move Pruning]]
* [[ProbCut]]
: [[ProbCut#MPC|Multi–ProbCut]]
* [[Singular Extensions]]
* [[Uncertainty Cut-Offs]]
=Publications=
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''1998'''). ''[http://link.springer.com/chapter/10.1007/3-540-48957-6_2 Multi-cut Pruning in Alpha-Beta Search]''. [[CG 1998]], see also [[Yngvi Björnsso#MC2001|MC2001]] for an expanded version.
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''2000'''). ''Risk Management in Game-tree Pruning''. Information Sciences, Vol. 122, No. 1, [http://www.ru.is/faculty/yngvi/pdf/BjornssonM00.pdf pdf]
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''2001'''). ''Multi-cut Alpha-Beta Pruning in Game Tree Search.'' Theoretical Computer Science, Vol. 252, [http://www.ru.is/faculty/yngvi/pdf/BjornssonM01a.pdf pdf]
* [[Yngvi Björnsson]] ('''2002'''). ''[http://dl.acm.org/citation.cfm?id=935848 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.'' [http://www.personeel.unimaas.nl/m-winands/documents/Enhanced%20forward%20pruning.pdf pdf]
* [[Hrafn Eiríksson]] ('''2011'''). ''Investigation of Multi-Cut Pruning in Game-Tree Search''. B.Sc. Thesis, [https://en.wikipedia.org/wiki/Reykjav%C3%ADk_University Reykjavík University], [http://skemman.is/en/stream/get/1946/9180/22971/1/research-report.pdf pdf]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=35697 Mult-cut, SE and ETC] by Ricardo Gibert, [[CCC]], August 05, 2010 » [[Singular Extensions]], [[Enhanced Transposition Cutoff]]
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=476407&t=44507 Re: Some thoughts on QS] by [[Vincent Diepeveen]], [[CCC]], July 30, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=60650 Multi-cut and fail-soft] by [[Matthew R. Brades]], [[CCC]], June 30, 2016 » [[Fail-Soft]]
=External Links=
* [https://en.wikipedia.org/wiki/Bj%C3%B6rk Björk] - [https://en.wikipedia.org/wiki/Big_Time_Sensuality Big Time Sensuality], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=-wYmq2Vz5yM|alignment=left|valignment=top}}
=References=
<references />
'''[[Pruning|Up one Level]]'''
[[FILE:Master Pine Pruner LACMA M.2006.136.205a-b.jpg|border|right|thumb|[[Arts#Hokusai|Katsushika Hokusai]] - Master Pine Pruner <ref>[[Arts#Hokusai|Katsushika Hokusai]] - [http://commons.wikimedia.org/wiki/File:Master_Pine_Pruner_LACMA_M.2006.136.205a-b.jpg Master Pine Pruner] cropped, ca. 1802, Series: Famous Views of the Eastern Capital, woodcuts, Current location: [https://en.wikipedia.org/wiki/Los_Angeles_County_Museum_of_Art Los Angeles County Museum of Art], [https://commons.wikimedia.org/wiki/Category:Katsushika_Hokusai Category:Katsushika Hokusai], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''Multi-Cut''',<br/>
a speculative pruning mechanism for chessplaying programs created by [[Yngvi Björnsson]] <ref>[[Yngvi Björnsson]], [[Tony Marsland]] ('''1998'''). ''[http://link.springer.com/chapter/10.1007/3-540-48957-6_2 Multi-cut Pruning in Alpha-Beta Search]''. [[CG 1998]]</ref> <ref>[[Yngvi Björnsson]], [[Tony Marsland]] ('''2001'''). ''Multi-cut Alpha-Beta Pruning in Game Tree Search.'' Theoretical Computer Science, Vol. 252, [http://www.ru.is/faculty/yngvi/pdf/BjornssonM01a.pdf pdf]</ref>. 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 [[Node Types#CUT|Cut-node]] is not singular, that is multiple (C) moves [[Fail-High|fail high]], and to prune the whole subtree in that case by returning the hard [[Beta|beta]] [[Bound|bound]]. [[Mark Winands|Mark Winands']] [[Enhanced Forward Pruning|enhanced forward pruning]] applies Multi-Cut even at expected [[Node Types#ALL|All-nodes]], with slight modifications on a [[Principal Variation Search|PVS]] framework <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> . In his 2011 B.Sc. thesis ''Investigation of Multi-Cut Pruning in Game-Tree Search'' <ref>[[Hrafn Eiríksson]] ('''2011'''). ''Investigation of Multi-Cut Pruning in Game-Tree Search''. B.Sc. Thesis, [https://en.wikipedia.org/wiki/Reykjav%C3%ADk_University Reykjavík University], [http://skemman.is/en/stream/get/1946/9180/22971/1/research-report.pdf pdf]</ref>, [[Hrafn Eiríksson]] proposed to apply Multi-cut if a [[Transposition Table|transposition table]] probe indicates a [[Beta-Cutoff|beta-cutoff]] without sufficient [[Depth|draft]] stored.
=Abstract=
from the [[Workshop Chess and Mathematics]], 2008 <ref>[http://www.math.tu-dresden.de/num/chess2008/index-en.html CHESS AND MATHEMATICS - Workshop Dresden, 21st - 23rd November 2008]</ref> <ref>[http://www.math.tu-dresden.de/num/chess2008/abstracts.pdf Workshop Chess and Mathematics] (pdf) agenda and abstracts</ref> :
The [[Alpha-Beta|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|brute-force]] [[Minimax|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|root]] of the [[Search Tree|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|null window]]- or [[Principal Variation Search#ZWS|zero window search]] of a [[Fail-Hard|fail-hard]] [[Principal Variation Search|PVS]] framework, applied at expected [[Node Types#CUT|Cut-nodes]]:
<pre>
// 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;
}
</pre>
=See also=
* [[Enhanced Forward Pruning]]
* [[Null Move Pruning]]
* [[ProbCut]]
: [[ProbCut#MPC|Multi–ProbCut]]
* [[Singular Extensions]]
* [[Uncertainty Cut-Offs]]
=Publications=
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''1998'''). ''[http://link.springer.com/chapter/10.1007/3-540-48957-6_2 Multi-cut Pruning in Alpha-Beta Search]''. [[CG 1998]], see also [[Yngvi Björnsso#MC2001|MC2001]] for an expanded version.
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''2000'''). ''Risk Management in Game-tree Pruning''. Information Sciences, Vol. 122, No. 1, [http://www.ru.is/faculty/yngvi/pdf/BjornssonM00.pdf pdf]
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''2001'''). ''Multi-cut Alpha-Beta Pruning in Game Tree Search.'' Theoretical Computer Science, Vol. 252, [http://www.ru.is/faculty/yngvi/pdf/BjornssonM01a.pdf pdf]
* [[Yngvi Björnsson]] ('''2002'''). ''[http://dl.acm.org/citation.cfm?id=935848 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.'' [http://www.personeel.unimaas.nl/m-winands/documents/Enhanced%20forward%20pruning.pdf pdf]
* [[Hrafn Eiríksson]] ('''2011'''). ''Investigation of Multi-Cut Pruning in Game-Tree Search''. B.Sc. Thesis, [https://en.wikipedia.org/wiki/Reykjav%C3%ADk_University Reykjavík University], [http://skemman.is/en/stream/get/1946/9180/22971/1/research-report.pdf pdf]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=35697 Mult-cut, SE and ETC] by Ricardo Gibert, [[CCC]], August 05, 2010 » [[Singular Extensions]], [[Enhanced Transposition Cutoff]]
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=476407&t=44507 Re: Some thoughts on QS] by [[Vincent Diepeveen]], [[CCC]], July 30, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=60650 Multi-cut and fail-soft] by [[Matthew R. Brades]], [[CCC]], June 30, 2016 » [[Fail-Soft]]
=External Links=
* [https://en.wikipedia.org/wiki/Bj%C3%B6rk Björk] - [https://en.wikipedia.org/wiki/Big_Time_Sensuality Big Time Sensuality], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=-wYmq2Vz5yM|alignment=left|valignment=top}}
=References=
<references />
'''[[Pruning|Up one Level]]'''
