Jump to content

Alpha–beta pruning: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
killer heuristic, added extlink that describes it
Line 24: Line 24:
if beta <= alpha
if beta <= alpha
return beta
return beta

See also:
* [[Computer chess]]


==External references==
==External references==

Revision as of 08:31, 19 December 2002

Alpha-beta pruning is a technique to reduce the number of nodes evaluated by the minimax algorithm for two-player games. It prunes out parts of the search tree that are so good for one player that the opponent will never allow them to be reached.

Minimax with alpha-beta pruning produces the same result as un-pruned minimax, but with much greater efficiency. It typically reduces the effective branching factor to its square root, or equivalently doubles the number of ply that can be searched in a given time.

The algorithm maintains two values alpha and beta which represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively. Initially alpha is minus infinity and beta is plus infinity. As the recursion progresses the "window" becomes smaller. When beta becomes less than alpha, it means that the current position cannot be the result of best play by both players and hence need not be explored further.

Further improvement can be achieved by using ordering heuristics to search parts of the tree that are likely to force alpha-beta cutoffs early. For example, moves that take pieces may be examined before moves that do not, or moves that have scored highly in earlier passes through the game-tree analysis may be evaluated before others.

Another common, and very cheap, heuristic is the killer heuristic, where the last move that caused a beta-cutoff at the same level in the tree search is always examined first. This idea can be generalised into a set of refutation tables.

C-like pseudocode is given below

evaluate (node, alpha, beta)
    if node is a leaf
        return the heuristic value of node
    if node is a maximizing node
        for each child of node
            beta = min (beta, evaluate (child, alpha, beta))
            if beta <= alpha
                return alpha
    if node is a minimizing node
        for each child of node
            alpha = max (alpha, evaluate (child, alpha, beta))
            if beta <= alpha
                return beta

See also:

External references