I am studying the Alpha Beta pruning algorithm here.
function alphabeta(node, depth, α, β, maximizingPlayer) is if depth = 0 or node is a terminal node then return the heuristic value of node if maximizingPlayer then value := −∞ for each child of node do value := max(value, alphabeta(child, depth − 1, α, β, FALSE)) α := max(α, value) if α ≥ β then break (* β cutoff *) return value else value := +∞ for each child of node do value := min(value, alphabeta(child, depth − 1, α, β, TRUE)) β := min(β, value) if β ≤ α then break (* α cutoff *) return value
In this slide (pg. 13) I read:
Deep alpha cut-off: . Def: For a node u in a tree and a positive integer g, Ancestor(g, u) is the direct ancestor of u by tracing the parent’s link g times. . When the lower bound Vl is produced at and propagated from u’s great grand parent, i.e., Ancestor(3,u), or any Ancestor(2i + 1,u), i ≥ 1. . When an upper bound Vu is returned from the a branch of u and Vl ≥ Vu, then there is no need to evaluate all later branches of u.
Also here the difference bteween shallow and deep cutoff.
I understand shallow alpha cutoff but I don't understand why deep alpha cutoff works.
UPDATE: I understood the deep cut watching this video: