Graph Theory37 sections · 1633 units
Open in Course

Alpha-Beta Pruning

(Skipping irrelevant branches)

Alpha-beta pruning improves minimax by skipping branches that cannot affect the final decision. If you are the max player and found a move with value 1010, you do not need to fully explore other moves that can give at most 55. Prune those branches. On graphs, alpha-beta pruning reduces the number of states you need to evaluate.

The savings depend on move ordering and graph structure. This saves time by skipping branches that cannot possibly improve the outcome. When you find a move that guarantees a win, you stop checking alternatives in that subtree.