Alpha-Beta

_α-β pruning

• It is a decision rule algorithm which is represented as game tree.

• It is used to find best way from number of possibility by pruning the nodes.

• Min-Max with alpha-beta pruning yields the same result as a complete search, but with much greater efficiency (i.e  reduced its effective branching).

• Here we store the best value for Max play found so far in ALPHA and the best value for Min play found so for in BETA.

• If, at any given point BETA becomes smaller than ALPHA (α≥β)we can prune the game tree at this point.

• It is required to evaluate atleast on set of leaf nodes branching of one of the deepest Min nodes and then use the acquired α value to prune the rest of the search.

 

Example:

Consider the following example, here 

 

The alpha-beta pruning process is based on depth first search algorithm, it excutes the successor nodes till it reaches depth, then it assign a value to the nodes and these values are backtracked to the previous nodes.

_{Step1:  we are starting our problem by generating first successor node.}

_{Step2:  As still we didn’t reach the depth we need to expanding next successor node.}

 

_{Step3:  Again expanding the successor nodes}

We pass this node back to the min node above. Since this is a min node, we now know that the minimax value of this node must be less than or equal to 3. In other words, we change beta to 3.

 

Note that the alpha and beta values at higher levels in the tree didn't change. When processing actually returns to those nodes, their values will be updated.

Next we generate the next child at depth 4, run our evaluation function, and return a value of 17 to the min node above:

 

Since this is a min node and 17 is greater than 3, this child is ignored. Now we've seen all of the children of this min node, so we return the beta value to the max node above. Since it is a max node, we now know that it's value will be greater than or equal to 3, so we change alpha to 3:

 

Notice that beta didn't change. This is because max nodes can only make restrictions on the lower bound. Further note that while values passed down the tree are just passed along, they aren't passed along on the way up. Instead, the final value of beta in a min node is passed on to possibly change the alpha value of its parent. Likewise the final value of alpha in a max node is passed on to possibly change the beta value of its parent.

We generate the next child and pass the bounds along:

 

Since this node is not at the target depth, we generate its first child

 

 

Since this is a min node, we now know that the value of this node will be less than or equal to 2, so we change beta to 2:

 

As here the condition satisfy (α≥β) we prune the tree, and traverse to the next node.

 

Back at the parent max node, our alpha value is already 3, which is more restrictive than 2, so we don't change it. At this point we've seen all the children of this max node, so we can set its value to the final alpha value:

 

Now we move on to the parent min node. With the 3 for the first child value, we know that the value of the min node must be less than or equal to 3, thus we set beta to 3:

 

Since we still have a valid range, we go on to explore the next child. We generate the max node...

 

 

 finally the max node at the target depth. All along this path, we merely pass the alpha and beta bounds along.

 

At this point, we've seen all of the children of the min node, and we haven't changed the beta bound. Since we haven't exceeded the bound, we should return the actual min value for the node.

 

 Now we return the value to the parent max node. Based on this value, we know that this max node will have a value of 15 or greater, so we set alpha to 15: