We can use the idea of pruning to eliminate large parts of the tree from consideration. The particular technique we examine is called alpha–beta pruning.

When applied to a standard ALPHA–BETA PRUNING minimax tree, it returns the same move as minimax would, but prunes (cuts off) away branches that cannot possibly influence the final decision.

Consider the two-ply game tree from following figure. Let’s go through the calculation of the optimal decision once, this time paying careful attention to what we know at each point in the process. The steps are explained in figure.

The outcome is that we can identify the minimax decision without ever evaluating two of the leaf nodes. Another way to look at this is as a simplification of the formula for MINIMAX.

Let the two unevaluated successors of node C in Figure have values x and y. Then the value of the root node is given by MINIMAX(root) = max(min(3, 12, 8), min(2, x, y), min(14, 5, 2)) = max(3, min(2, x, y), 2) = max(3, z, 2) where z = min(2, x, y) ≤ 2 = 3.

In other words, the value of the root and hence the minimax decision are independent of the values of the pruned leaves x and y. Alpha–beta pruning can be applied to trees of any depth, and it is often possible to prune entire subtrees rather than just leaves. The general principle is this: consider a node n somewhere in the tree (see Figure), such that Player has a choice of moving to that node.

If Player has a better choice m either at the parent node of n or at any choice point further up, then n will never be reached in actual play. So once we have found out enough about n (by examining some of its descendants) to reach this conclusion, we can prune it. Remember that minimax search is depth-first, so at any one time we just have to consider the nodes along a single path in the tree

Consider the following game tree:

So in this example we have pruned 2 beta and 0 alpha branches.