Make your own AI Game Engine – 3

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.

game-tree
Sample Game Tree

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

Game Tree : 1st Sub-Tree Traversed
Game Tree : 1st Sub-Tree Traversed

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.

Game Tree : Traversing 2nd Sub-Tree
Game Tree : Traversing 2nd Sub-Tree

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 bd.
  • 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 bd/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.

Leave a Reply