Beta-Cutoff

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Alpha-Beta * Beta-Cutoff

Cut-off [1]

A beta-cutoff occurs in the alpha-beta algorithm, if the score backed up by the search is greater than or equal to beta and fails high. No further moves need to be searched, since one refutation is already sufficient to avoid the move that led to this node or position. Nodes, where a beta-cutoff occurs are then cut-nodes where 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 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 implementation makes both players maximizers, negamax alpha-beta has beta-cutoffs exclusively for both players.

Shallow or Deep

A shallow cutoff occurs if the window was narrowed at the parent node, that is, reduced current beta. A deep cutoff occurs if the window was narrowed closer to the 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 through the recursive call [2].

Shallowcutoff.jpg
Deepcutoff.jpg
Shallow Cutoff if α >= β Deep Cutoff if α >= β [3]

See also

Forum Posts

External Links

References

  1. A Biker's vintage cut-off adorned with club badges, Image by Bullenwächter, December 12, 2004, Cut-off from Wikipedia, Wikimedia Commons
  2. Re: What the computer chess community needs to decide by Harm Geert Muller, CCC, February 11, 2011
  3. Modified images from Matthew L. Ginsberg, Alan Jaffray (2002). Alpha-Beta Pruning Under Partial Orders. in Richard J. Nowakowski (ed.) More Games of No Chance. Cambridge University Press, pdf

Up one Level