1
$\begingroup$

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:

Animation of deep pruning by the Alpha-Beta Algorithm.

$\endgroup$
0

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.