###### Logical-Reasoning

October 4, 2023# NTA-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(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)}

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(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)}