What Is Alpha-Beta Pruning in Game Trees?

TL;DR

Alpha-beta pruning is an advanced version of the minimax algorithm that cuts off search by exploring fewer nodes. Alpha values are kept at Max nodes and increase, beta values are kept at Min nodes and decrease. When a branch cannot influence the final decision, it is pruned entirely, improving performance over minimax, whose time complexity is order of B raised to power D.

Transcript

Hello! friends Welcome to Gate Smashers! In today's video we're going to discuss about Alpha-Beta Pruning In we will discuss all important points about alpha-beta pruning which are beneficial for your competitive exams as well as for your college or university exams So we will start from the first point that we also call alpha-beta pruning method a... Read More

Key Insights

• Alpha-beta pruning is called an advanced version of the minimax algorithm. Its purpose is to cut off the search by exploring a smaller number of nodes, so that performance increases and the algorithm takes less time than plain minimax.
• The time complexity of minimax is order of B raised to power D, where B is the branching factor, meaning every node has B children, and D is the depth of the game tree. This cost arises because minimax explores all the nodes.
• Alpha and beta are two values used during the search. Alpha is generally considered for the Max nodes and beta is generally considered for the Min nodes, and both are updated as terminal utilities are read during traversal.
• The traversal in alpha-beta pruning follows depth-first search. The search descends to the leftmost terminal node first, reads its utility value, and propagates values upward as each Min or Max node becomes fixed.
• Beta values move in a decreasing direction and alpha values move in an increasing direction. A Min node's value will be equal to or less than its beta, and a Max node's value will be equal to or greater than its alpha.
• Pruning happens when a Min node's beta is already lower than an ancestor Max node's alpha. In the example, a Max node with alpha 3 ignores a Min branch offering only 2 or less, so that branch is pruned without being searched.
• A branch is pruned when it cannot influence the final decision. In the example, a Max node reaching alpha 7 sits under a Min node fixed at beta 3, so even a value of 1000 down that path would never be selected.
• The pruned subtrees would give the same final answer under minimax anyway. Minimax would reject a path yielding a minimum of 2 when another path guarantees the Max player a profit of at least 3, so skipping it costs nothing.

Questions & Answers

Q: What is alpha-beta pruning in artificial intelligence?

Alpha-beta pruning is an advanced version of the minimax algorithm. Its main idea is to cut off the search by exploring a smaller number of nodes instead of exploring all nodes as minimax does. If a best path has already been found, the remaining paths are pruned, meaning they are cut off and never explored, because they create no problem in and no influence on the final decision. Alpha and beta are two values used in the process: alpha is generally considered for Max nodes and beta for Min nodes.

Q: What is the time complexity of the minimax algorithm?

The time complexity and performance of the minimax algorithm is calculated as order of B raised to power D. Here B is the branching factor, which means every node in the game tree has B number of children, and D is the depth of that game tree. The complexity is this high because minimax explores all the nodes in the tree. The main aim is to find the best path for the Max player, who is considered at the root level, and reaching that decision requires exploring every node.

Q: Why does alpha-beta pruning improve performance over minimax?

Alpha-beta pruning improves performance because it explores a smaller number of nodes than minimax. When fewer nodes are explored, performance obviously increases and the method takes less time. The saving comes from pruning: if a path has already been found, the remaining paths are cut off and not searched. Those pruned paths are skipped safely because they do not create any problem in the final decision, and the answer produced is the same one minimax would have produced after exploring everything.

Q: Where are alpha and beta values assigned in a game tree?

Alpha is generally considered at the Max nodes and beta is generally considered at the Min nodes. In the example game tree, the root node is Max, the next level is Min, then Max again, then Min, and the last level holds the terminals, also called leaf nodes, which already carry utility values. As the search reads a terminal value, it fixes beta at the Min node above it, and once a node's value is fixed, that value is carried up and fixed as alpha at the Max node above.

Q: How does a beta value get updated at a Min node?

Beta is generally taken with an upper bound of plus infinity and then decreased, choosing the minimum. In the worked example, the leftmost terminal has value 3, so beta is fixed at 3, and the Min node's value is then known to be either 3 or less than 3. Moving to the sibling terminal with value 4, beta remains 3 because 4 is larger, so the Min node's value is confirmed as 3. Had the sibling been 2 instead of 4, the Min node's value and beta would both have become 2.

Q: When should a branch be pruned during alpha-beta pruning?

A branch should be pruned when it cannot change the final decision. In the example, a Max node has alpha fixed at 3, so its value is 3 or greater than 3. The next branch reaches a terminal with value 2, so beta there is 2 and that Min node's value will be 2 or less than 2. Since the Max player is already guaranteed at least 3 and that branch offers at most 2, the branch is not worth exploring and is pruned without being searched.

Q: Why is a subtree with a very large value still pruned?

Because the parent has already committed to a smaller bound. In the example, a Max node reaches alpha 7, and the Min node above it already has beta fixed at 3, meaning it will accept only 3 or less than 3. Even if that path led to alpha of 1000, the Min node would never select it. The transcript also shows that exploring further, where the minimum between 9 and 10 is 9, would raise alpha to 9, yet the Min node fixed at beta 3 still would not consider it, so the whole part is pruned.

Q: How does depth-first search relate to alpha-beta pruning?

The movement through the game tree follows depth-first search. The search first descends along the leftmost path down to a terminal node, reads its utility value, and then works upward, fixing beta at Min nodes and alpha at Max nodes as values become confirmed. Only after a node's value is fixed is it carried to the level above. This ordering is what makes pruning possible, because bounds established on already-explored branches can be compared against newly encountered branches to decide whether those branches are worth exploring.

Summary & Key Takeaways

• Minimax explores every node of a game tree to find the best path for the Max player at the root, giving a time complexity of order of B raised to power D, where B is the branching factor (the number of children per node) and D is the depth of the game tree.

• Alpha-beta pruning cuts off the search by exploring a smaller number of nodes. Once a best path has already been found, the remaining paths are pruned, meaning they are not explored at all, because they create no problem in and no influence on the final decision.

• Alpha is considered for Max nodes and beta for Min nodes. Beta is generally taken with an upper bound of plus infinity and decreased toward the minimum, while alpha is taken in an increasing way from minus infinity, though the values can also be assigned directly from the terminal utilities.