Questions tagged [alpha-beta-pruning]

Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. 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 (wiki)}

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.
_{Strategies & Tactics for Intelligent Search (Stanford)}