Logical-Reasoning
October 4, 2023NTA-UGC-NET 2021 Dec & 2022 June Paper-2
| 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 |
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)
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)