Alpha-Beta Pruning in Artificial Intelligence (AI)

In this page we will learn about Alpha-Beta Pruning in Artificial Intelligence (AI), Alpha-Beta Pruning, Condition for Alpha-beta pruning, Key points about alpha-beta pruning, Pseudo-code for Alpha-beta Pruning, Working of Alpha-Beta Pruning, Move Ordering in Alpha-Beta pruning, and Rules to find good ordering.

---

Alpha-Beta Pruning

• A modified variant of the minimax method is alpha-beta pruning. It's a way for improving the minimax algorithm.
• The number of game states that the minimax search algorithm must investigate grows exponentially with the depth of the tree, as we saw with the minimax search method. We can't get rid of the exponent, but we can reduce it by half. As a result, there is a technique known as Pruning that allows us to compute the correct minimax choice without having to inspect each node of the game tree. It's named alpha-beta pruning because it involves two threshold parameters, Alpha and beta, for future expansion. Alpha-Beta Algorithm is another name for it.
• Alpha-beta pruning can be done at any depth in a tree, and it can sometimes prune the entire sub-tree as well as the tree leaves.
• The two-parameter can be written as follows:
  a) Alpha: At any point along the Maximizer path, Alpha is the best (highest-value) option we've uncovered so far. The value of alpha starts at -.
  b) Beta: At every point along the route of Minimizer. Beta is the best (lowest-value) option we've found so far. Minimizer. The initial value of beta is +∞
• The Alpha-beta pruning to a standard minimax algorithm produces the same result as the regular approach, but it removes those nodes that aren't really effecting the final decision but are slowing down the procedure. As a result, reducing these nodes speeds up the process.

Note: If you want to learn more about this issue, go into the minimax algorithm.

Condition for Alpha-beta pruning:

The main condition which required for alpha-beta pruning is:

    α >= β 

---

Key points about alpha-beta pruning:

• Only the value of alpha will be updated by the Max player.
• Only the beta value will be updated by the Min player.
• Instead of alpha and beta values, node values will be sent to upper nodes while retracing the tree.
• Only the alpha and beta values will be passed to the child nodes.

Pseudo-code for Alpha-beta Pruning:

 
    function minimax(node, depth, alpha, beta, maximizingPlayer) is  
    if depth == 0 or node is a terminal node then  
    return static evaluation of node  
      
    if MaximizingPlayer then      // for Maximizer Player  
       maxEva =- infinity            
       for each child of node do  
       eva = minimax(child, depth-1, alpha, beta, False)  
      maxEva = max(maxEva, eva)   
      alpha = max(alpha, maxEva)      
       if beta <= alpha  
     break  
     return maxEva  
        
    else                         // for Minimizer player  
       minEva =+infinity   
       for each child of node do  
       eva= minimax(child, depth-1, alpha, beta, true)  
       minEva = min(minEva, eva)   
       beta = min(beta, eva)  
        if beta <= alpha  
      break          
     return minEva     

---

Working of Alpha-Beta Pruning:

To better understand how Alpha-beta pruning works, consider a two-player search tree.
Step 1: The Max player will begin by moving from node A, where = - and = +, and passing these values of alpha and beta to node B, where again = - and = +, and Node B passing the same value to its offspring D.

Step 2: The value of will be determined as Max's turn at Node D. The value of is compared to 2, then 3, and the value of at node D will be max (2, 3) = 3, and the node value will also be 3.

Step 3: The algorithm now returns to node B, where the value of will change as this is a turn of Min, now = +, and will compare with the value of the available subsequent nodes, i.e. min (, 3) = 3, so at node B now = -, and= 3.

In the next step, algorithm traverse the next successor of Node B which is node E, and the values of α= -∞, and β= 3 will also be passed.

Step 4: Max will take its turn at node E, changing the value of alpha. The current value of alpha will be compared to 5, resulting in max (-, 5) = 5, and at node E= 5 and= 3, where >=, the right successor of E will be pruned, and the algorithm will not traverse it, and the value at node E will be 5.

Step 5: The method now goes backwards in the tree, from node B to node A. The value of alpha will be modified at node A, and the highest available value will be 3 as max (-, 3)= 3, and = +. These two values will now transfer to A's right successor, Node C.

=3 and = + will be passed on to node F at node C, and the same values will be passed on to node F.

Step 6: TAt node F, the value of will be compared with the left child, which is 0, and max(3,0)= 3, and then with the right child, which is 1, and max(3,1)= 3 will remain the same, but the node value of F will change to 1.

Step 7: Node F returns the node value 1 to node C, at C = 3 and = +, the value of beta is modified, and it is compared to 1, resulting in min (, 1) = 1. Now, at C, =3 and = 1, and again, it meets the condition >=, the algorithm will prune the next child of C, which is G, and will not compute the complete sub-tree G.

Step 8: C now returns 1 to A, with max (3, 1) = 3 being the greatest result for A. The completed game tree, which shows calculated and uncomputed nodes, is shown below. As a result, in this case, the best maximizer value is 3.

---

Move Ordering in Alpha-Beta pruning:

The order in which each node is reviewed has a significant impact on the success of alpha-beta pruning. The order in which moves are made is crucial in alpha-beta pruning.
There are two types of it:

• Worst ordering: In some instances, the alpha-beta pruning technique does not trim any of the tree's leaves and functions identically to the minimax algorithm. Because of the alpha-beta factors, it also takes more time in this scenario; this type of pruning is known as worst ordering. The optimal move is on the right side of the tree in this situation. For such an order, the temporal complexity is O. (bm).
• Ideal ordering: When a lot of plastic is in the tree and the best movements are made on the left side of the tree, the optimal placement for alpha-beta plastering takes place. We use DFS such that it is initially left searching and goes deep in same amount of time twice as a minimum method. Complexity is O(bm/2) in ideal ordering.

---

Rules to find good ordering:

The following are some guidelines for finding effective alpha-beta pruning ordering:

• The optimal move should be made from the shallowest node.
• In the tree, sort the nodes so that the best ones are checked first.
• When deciding on the right step, make use of your subject knowledge. For example, in Chess, attempt the following order: captures first, threats second, forward moves third, backward moves fourth.
• We can keep track of the states because there's a chance they'll happen again.