Trouble applying the Alpha Beta Pruning algorithm to this tree

Question

I am trying to apply the alpha beta pruning algorithm to this given tree.

I am stuck when I hit node C because after expanding all the children of B, I give A >= -4, I then expand C to get I =-3, which IS greater than -4 (-3 >= -4). Do I therefore, update A to -3? If so do I then afterwards, prune J and K because -3 >= -3 ? When I worked through the example, I pruned, J, K, M and N. I am really uncertain about this =(

EDIT:

Another question: After exploring B and passing the value of B to A, do we pass this value to C and thus to I? I saw an example that this was the case. Here it is: http://web.cecs.pdx.edu/~mm/AIFall2011/alphabeta-example.pdf

However, in this example, http://web.cecs.pdx.edu/~mm/AIFall2011/alphabeta-example.pdf, it doesn't seem to pass down values, instead it seems to only propagate values upwards. I am not sure which one is correct or if it makes a difference at all.

Answer 1

After expanding all the children of B, then A has α=-4, β=∞.

When you get to I, then α=-4, β=-3. α < β so J and K are not pruned. They would need to be evaluated to make sure that they're not less than -3, lowering the evaluation of C. The value of A is updated to α=-3, β=∞ after C is expanded. You can't use the updated alpha value of A when evaluating J because it wouldn't have been updated yet.

J and K would be pruned if I was -5 instead. In that case it wouldn't matter what J and K are because we already know the evaluation of C is worse than B because -5 < -4, and J and K can only make that worse.

Each node passes the alpha and beta values to its children. The children will then update their own copies of the alpha or beta value depending on whose turn it is and return the final evaluation of that node. That is then used to update the alpha or beta value of the parent.

See Alpha-Beta pruning for example:

function alphabeta(node, depth, α, β, Player)         
    if depth = 0 or node is a terminal node
        return the heuristic value of node
    if Player = MaxPlayer
        for each child of node
            α := max(α, alphabeta(child, depth-1, α, β, not(Player)))     
            if β ≤ α
                break // Beta cut-off
        return α
    else
        for each child of node
            β := min(β, alphabeta(child, depth-1, α, β, not(Player)))     
            if β ≤ α
                break // Alpha cut-off
        return β

// Initial call
alphabeta(origin, depth, -infinity, +infinity, MaxPlayer)

Answer 2

Whenever I need to refresh my understanding of the algorithm I use this: http://homepage.ufp.pt/jtorres/ensino/ia/alfabeta.html

You can enter your tree there and step through the algorithm. The values you would want are:

3 3 3 3

-2 -4 3 etc.

I find that deducing the algorithm from an example provides a deeper understanding.