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: