25,161
edits
Changes
Created page with "'''Home * Search * Alpha-Beta * Beta-Cutoff''' FILE:Kutte Motorrad vorn.jpg|border|right|thumb|200px|Cut-off <ref>A Biker's vintage cut-off adorned wi..."
'''[[Main Page|Home]] * [[Search]] * [[Alpha-Beta]] * Beta-Cutoff'''
[[FILE:Kutte Motorrad vorn.jpg|border|right|thumb|200px|Cut-off <ref>A Biker's vintage cut-off adorned with club badges, Image by [https://commons.wikimedia.org/wiki/User:Bullenw%C3%A4chter Bullenwächter], December 12, 2004, [https://en.wikipedia.org/wiki/Cut-off Cut-off from Wikipedia], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
A '''beta-cutoff''' occurs in the [[Alpha-Beta|alpha-beta algorithm]], if the [[Score|score]] backed up by the search is greater than or equal to [[Beta|beta]] and [[Fail-High|fails high]]. No further [[Moves|moves]] need to be searched, since one [[Refutation Move|refutation]] is already sufficient to avoid the move that led to this [[Node|node]] or [[Chess Position|position]]. Nodes, where a beta-cutoff occurs are then [[Node Types#CUT|cut-nodes]] where [[Move Ordering|move ordering]] was crucial to try the refutation move as early as possible - typically as first move in 90 to 95 per cent of all cases. In [[Alpha-Beta#MaxversusMin|max versus min alpha-beta]] a beta-cutoff can only occur for the max-player, while the min-player cuts if below or equal alpha, called '''alpha-cutoff'''. Since the common [[Negamax|negamax]] implementation makes both players maximizers, [[Alpha-Beta#Negamax|negamax alpha-beta]] has beta-cutoffs exclusively for both players.
=Shallow or Deep=
<span id="shallow"></span> A '''shallow''' cutoff occurs if the [[Window|window]] was narrowed at the parent node, that is, reduced current beta. <span id="deep"></span>A '''deep''' cutoff occurs if the [[Window|window]] was narrowed closer to the [[Root|root]] with an odd ply-distance of at least three to the current node. Deep cutoffs were sometimes omitted in early chess programs if not passing [[Alpha|alpha]] through the [[Recursion|recursive]] call <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=394125&t=38007 Re: What the computer chess community needs to decide] by [[Harm Geert Muller]], [[Computer Chess Forums|CCC]], February 11, 2011</ref>.
{|
|-
| [[FILE:shallowcutoff.jpg|none|border|text-bottom]]
!
| [[FILE:deepcutoff.jpg|none|border|text-bottom]]
|-
| Shallow Cutoff if α >= β
!
| Deep Cutoff if α >= β <ref>Modified images from [[Matthew L. Ginsberg]], [[Alan Jaffray]] ('''2002'''). ''Alpha-Beta Pruning Under Partial Orders''. in [[Richard J. Nowakowski]] (ed.) ''[http://library.msri.org/books/Book42/ More Games of No Chance]''. [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press], [http://library.msri.org/books/Book42/files/ginsberg.pdf pdf]</ref>
|}
=See also=
* [[Sierżant#Cutratio|Cutoff ratio in Sierżant]]
* [[Fail-High]]
* [[Fail-Low]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=65477 cut nodes] by [[Folkert van Heusden]], [[CCC]], October 18, 2017 » [[Node Types#CUT|Cut-Nodes]]
=External Links=
* [https://en.wiktionary.org/wiki/cutoff cutoff - Wiktionary]
* [https://en.wiktionary.org/wiki/cut_off cut off - Wiktionary]
* [https://en.wikipedia.org/wiki/Cutoff Cutoff from Wikipedia]
* [https://en.wikipedia.org/wiki/Cut-off Cut-off from Wikipedia]
=References=
<references />
'''[[Alpha-Beta|Up one Level]]'''
[[FILE:Kutte Motorrad vorn.jpg|border|right|thumb|200px|Cut-off <ref>A Biker's vintage cut-off adorned with club badges, Image by [https://commons.wikimedia.org/wiki/User:Bullenw%C3%A4chter Bullenwächter], December 12, 2004, [https://en.wikipedia.org/wiki/Cut-off Cut-off from Wikipedia], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
A '''beta-cutoff''' occurs in the [[Alpha-Beta|alpha-beta algorithm]], if the [[Score|score]] backed up by the search is greater than or equal to [[Beta|beta]] and [[Fail-High|fails high]]. No further [[Moves|moves]] need to be searched, since one [[Refutation Move|refutation]] is already sufficient to avoid the move that led to this [[Node|node]] or [[Chess Position|position]]. Nodes, where a beta-cutoff occurs are then [[Node Types#CUT|cut-nodes]] where [[Move Ordering|move ordering]] was crucial to try the refutation move as early as possible - typically as first move in 90 to 95 per cent of all cases. In [[Alpha-Beta#MaxversusMin|max versus min alpha-beta]] a beta-cutoff can only occur for the max-player, while the min-player cuts if below or equal alpha, called '''alpha-cutoff'''. Since the common [[Negamax|negamax]] implementation makes both players maximizers, [[Alpha-Beta#Negamax|negamax alpha-beta]] has beta-cutoffs exclusively for both players.
=Shallow or Deep=
<span id="shallow"></span> A '''shallow''' cutoff occurs if the [[Window|window]] was narrowed at the parent node, that is, reduced current beta. <span id="deep"></span>A '''deep''' cutoff occurs if the [[Window|window]] was narrowed closer to the [[Root|root]] with an odd ply-distance of at least three to the current node. Deep cutoffs were sometimes omitted in early chess programs if not passing [[Alpha|alpha]] through the [[Recursion|recursive]] call <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=394125&t=38007 Re: What the computer chess community needs to decide] by [[Harm Geert Muller]], [[Computer Chess Forums|CCC]], February 11, 2011</ref>.
{|
|-
| [[FILE:shallowcutoff.jpg|none|border|text-bottom]]
!
| [[FILE:deepcutoff.jpg|none|border|text-bottom]]
|-
| Shallow Cutoff if α >= β
!
| Deep Cutoff if α >= β <ref>Modified images from [[Matthew L. Ginsberg]], [[Alan Jaffray]] ('''2002'''). ''Alpha-Beta Pruning Under Partial Orders''. in [[Richard J. Nowakowski]] (ed.) ''[http://library.msri.org/books/Book42/ More Games of No Chance]''. [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press], [http://library.msri.org/books/Book42/files/ginsberg.pdf pdf]</ref>
|}
=See also=
* [[Sierżant#Cutratio|Cutoff ratio in Sierżant]]
* [[Fail-High]]
* [[Fail-Low]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=65477 cut nodes] by [[Folkert van Heusden]], [[CCC]], October 18, 2017 » [[Node Types#CUT|Cut-Nodes]]
=External Links=
* [https://en.wiktionary.org/wiki/cutoff cutoff - Wiktionary]
* [https://en.wiktionary.org/wiki/cut_off cut off - Wiktionary]
* [https://en.wikipedia.org/wiki/Cutoff Cutoff from Wikipedia]
* [https://en.wikipedia.org/wiki/Cut-off Cut-off from Wikipedia]
=References=
<references />
'''[[Alpha-Beta|Up one Level]]'''
