[go: up one dir, main page]
Scribd
Upload
115 views5 pages

Alpha-Beta Pruning

Alpha-beta pruning is a technique for improving the minimax algorithm by reducing the number of nodes that must be evaluated. It uses two values, alpha and beta, to prune branches of the game tree that cannot influence the outcome. The algorithm traverses the tree and updates alpha and beta values at each node to prune subtrees where the minimum possible value for the maximizer is greater than the maximum possible value for the minimizer.

Uploaded by

periyasamy.pn
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
115 views5 pages

Alpha-Beta Pruning

Alpha-beta pruning is a technique for improving the minimax algorithm by reducing the number of nodes that must be evaluated. It uses two values, alpha and beta, to prune branches of the game tree that cannot influence the outcome. The algorithm traverses the tree and updates alpha and beta values at each node to prune subtrees where the minimum possible value for the maximizer is greater than the maximum possible value for the minimizer.

Uploaded by

periyasamy.pn
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

Alpha-Beta Pruning in Artificial Intelligence (AI)

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.

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.

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.

You might also like