ALPHA-BETA PRUNING
In the course of a depth-first search of the game-tree, we may
sometimes recognize that certain sub-trees do not need to be
explored. For instance, once we begin to explore the sub-tree
rooted at C, and find that position G has value 1, we know that
the minimax value of position C will be 1 or smaller. Since the
minimax value of position B has already been computed to be 4,
which is larger than 1, we do not need to evaluate positions H
and I; we can conclude, on the basis of the information we
already have, that the minimax value of A is 4, and that the
correct minimax move is from A to B.
A
/ \
/ \ Computer's move
/ \
4 C
/ | \ / | \
/ | \ / | \ Human's move
/ | \ / | \
4 5 6 1 ? ?
Ignoring sub-trees in this fashion (a process called alpha-beta
pruning) is easily implemented on a computer, and can lead to
dramatic speed-up of depth-first searches.