UGC NET November 2020 Paper1
October 4, 2023NTAUGCNET 2021 Dec & 2022 June Paper2
Question 16

(A) Root (0) level
(B) 6 level
(C) 8 level
(D) Depends on utility value in a breadth first order
(B) and (C) only


(A) and (B) only


(A),(B) and (C) only


(A) and (D) only

Alphabeta Algorithm:
– Uses Depth first search
– only considers nodes along a single path from root at any time
α = highestvalue choice found at any choice point of path for MAX (initially, α = −infinity)
β = lowestvalue 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 AlphaBeta Search:
– Alpha/beta best case is O(b^{(d/2)}) rather than O(b^{d})
– 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)}
Alphabeta Algorithm:
– Uses Depth first search
– only considers nodes along a single path from root at any time
α = highestvalue choice found at any choice point of path for MAX (initially, α = −infinity)
β = lowestvalue 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 AlphaBeta Search:
– Alpha/beta best case is O(b^{(d/2)}) rather than O(b^{d})
– 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)}