ALGORITHMS - ALPHA-BETA PRUNING

Alpha-beta pruning is an improvement over the minimax algorithm. The problem with minimax is that the number of game states it has to examine is exponential in the number of moves. While it is impossible to eliminate the exponent completely, we are able to cut it in half. It is possible to compute the correct minimax decision without looking at every node in the tree. Borrowing the idea of pruning, or eliminating possibilities from consideration without having to examine them, the algorthm allows us to discard large parts of the tree from consideration. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.

Alpha-beta pruning can be applied to trees of any depth and it often allows to prune away entire subtrees rather than just leaves. Here is the general algorithm:

1. Consider a node n somewhere in the tree, such that one can move to that node.
2. If there is a better choice m either at the parent of the node n or at any choice point further up, n will never be reached.
3. Once we have enough information about n to reach this conclusion, we can prune it.

Alpha-Beta pruning gets its name from the following parameters:

a = the value of the best choice we have found so far at any choice point along the path for MAX.
ß = the value of the best choice we have found so far at any choice point along the path for MIN

Fig. 1

As shown in Fig. 1, Alpha-Beta search updates the values of a and ß as it goes along and prunes the remaining branches at a node as soon as the value of the current node is known to be worse than the current values of a and ß. The success of the algorithm depends on the order in which the successors are examined.

Transportation tables have been used as a way to keep track of the information about individual nodes. Using such a table can have a framatic effect, sometimes even doubling the reachable search depth. However, if a million nodes are evaluated every second, keeping all the information is a table is not practical.