October 4, 2023
October 4, 2023
###### UGC NET November 2020 Paper-1
October 4, 2023
October 4, 2023
 Question 16
In a game playing search tree, up to which depth α-β pruning can be applied?
(A) Root (0) level
(B) 6 level
(C) 8 level
(D) Depends on utility value in a breadth first order
 A (B) and (C) only B (A) and (B) only C (A),(B) and (C) only D (A) and (D) only
Question 16 Explanation:
Alpha-beta pruning is a modified version of the minimax algorithm. It is an optimization technique for the minimax algorithm.

Alpha-beta Algorithm:
– Uses Depth first search
– only considers nodes along a single path from root at any time
α = highest-value choice found at any choice point of path for MAX (initially, α = −infinity)
β = lowest-value choice found at any choice point of path for MIN (initially, β = +infinity)
– Pass current values of α and β down to child nodes during search.
– Update values of α and β during search:
– MAX updates α at MAX nodes
– MIN updates β at MIN nodes

When to Prune:
– Prune whenever α ≥ β.
– Prune below a Max node whose alpha value becomes greater than or equal to the beta value of its ancestors.
– Max nodes update alpha based on children’s returned values.
– Prune below a Min node whose beta value becomes less than or equal to the alpha value of its ancestors.
– Min nodes update beta based on children’s returned values.

Effectiveness of Alpha-Beta Search:
– Alpha/beta best case is O(b(d/2)) rather than O(bd)
– This is the same as having a branching factor of sqrt(b),
– (sqrt(b))d/ = b(d/2) (i.e., we have effectively gone from b to square root of b)
– In chess go from b ~ 35 to b ~ 6
– permitting much deeper search in the same amount of time
– In practice it is often b(2d/3)

Question 16 Explanation:
Alpha-beta pruning is a modified version of the minimax algorithm. It is an optimization technique for the minimax algorithm.

Alpha-beta Algorithm:
– Uses Depth first search
– only considers nodes along a single path from root at any time
α = highest-value choice found at any choice point of path for MAX (initially, α = −infinity)
β = lowest-value choice found at any choice point of path for MIN (initially, β = +infinity)
– Pass current values of α and β down to child nodes during search.
– Update values of α and β during search:
– MAX updates α at MAX nodes
– MIN updates β at MIN nodes

When to Prune:
– Prune whenever α ≥ β.
– Prune below a Max node whose alpha value becomes greater than or equal to the beta value of its ancestors.
– Max nodes update alpha based on children’s returned values.
– Prune below a Min node whose beta value becomes less than or equal to the alpha value of its ancestors.
– Min nodes update beta based on children’s returned values.

Effectiveness of Alpha-Beta Search:
– Alpha/beta best case is O(b(d/2)) rather than O(bd)
– This is the same as having a branching factor of sqrt(b),
– (sqrt(b))d/ = b(d/2) (i.e., we have effectively gone from b to square root of b)
– In chess go from b ~ 35 to b ~ 6
– permitting much deeper search in the same amount of time
– In practice it is often b(2d/3)