So, I hope you have read the two previous articles, part 1 and part 2 of this. I promised to explain about Alpha-Beta pruning, and here we go.

Alpha-Beta Pruning

In normal mini-max algorithm, we have to traverse through all the nodes and evaluate them. But sometime we don’t have to, if we already got a better option than the one we’re going to examine.

Let’s and example game tree.

When we finish the 1st sub-tree, we will get the max value, we call it alpha (α), as 3.

In here alpha is the maximum value for a node, and beta is minimum value for a node.

Then we continue to traverse through the 2nd sub-tree. And at some point, the values will be like following.

When we come to this point, that we know the maximum value we will get to the root of the 2nd sub-tree is 0. The reason is, if there are values above 0 in the branch B, it will be ignored because C takes the minimum value. If there are lower values than 0 in the branch B, C will take them, meaning the maximum value that C will take is 0. But we already know that the parent of C is a max node and it has alpha = 3. So there is no possibility that it will select a lower value than 3. Hence, at this point, we can stop traversing the sub-tree of C by simply returning 0 to the root.

The same scenario is applied when there is a max node at C, but the other way-round.

To reduce the complexity, I will use two functions for Min and Max nodes. However the Alpha-Beta search will be look like:

function ALPHABETA(search tree node s)
  return MAX_VALUE(s,−∞,+∞)
end function

We call the max function at the root, since we need the max value at the root node. But if we’re taking this as 3 sub-trees (as I explained here), we have to apply MIN_VALUE for each of the children of the root, and get the child with the max value.

Here are the pseudo code for the MIN_VALUE and MAX_VALUE functions.

function MIN_VALUE(node s, α, β))
  if s is a leaf then
    return utility(s)
  end if
  value = +∞ // initialize β as the highest possible value
  for each child t of s :
    value = min(value, MAX_VALUE(t, α, β)) // go to next level of the tree
    if value ≤ α then
      return value
    end if
    β = min(β, value)
  end for
  return value
end function

function MAX_VALUE(node s, α, β))
  if s is a leaf then
    return utility(s)
  end if
  value = −∞ // initialize α as the lowest possible value at the beginning
  for each child t of s :
    value = max(value, MIN_VALUE(t, α, β)) // go to next level of the tree
    if value ≥ β then
      return value
    end if
    α = max(α, value)
  end for
  return value
end function

No matter how much this performs, if we still create the whole tree before we traverse, it will cost us a LOT. So it’s better to create the children on the way of traversal.

Quick Comparison

• Mini-Max visits all tree nodes. With branching factor b and depth d, this amounts to b^d.
• Number of nodes that Alpha-Beta visits, depends on the order in which moves are examined.
• If the best move is always examined first, Alpha-Beta visits b^d/2 nodes.
• Hence, we can use domain-specific knowledge to order the possible moves to achieve more efficiency.

For the details about the utility function, please see the edit of my first article.