This question is from geeks for geeks platform

Question

I saw this question of alpha beta prunning and they mentionoing answer that node K and G will be prunned according to me only G will be prunned i verified via gemini also but i have doubt can anyone verify this @Sachin Mittal 1 @GO Classes Support 

Comments

Answer via gemini 

Tree Structure & Node Roles

• Level 1 (A): MAX node ($\triangle$)

• Level 2 (B, C): MIN nodes ($\nabla$)

• Level 3 (D, E, F, G): MAX nodes ($\triangle$)

• Level 4 (H, I, J, K, L, M, N): MIN nodes ($\nabla$)

• Level 5: Leaf values

Step-by-Step Traversal to Node K

1. Node J (MIN node at Level 4):

    

   • Its child leaf value is 15.

   • Since J has no other children, J = 15.

2. Node E (MAX node at Level 3):

    

   • Since E is a MAX node, it receives 15 from its left child J.

   • Node E updates its local value / lower bound: $\alpha_E = 15$.

   • Node E now evaluates its right child K.

3. Node K (MIN node at Level 4):

    

   • Node K receives the parent's lower bound ($\alpha = 15$).

   • Node K evaluates its left child (25) first:

      

     • Since K is a MIN node, seeing 25 sets its upper bound: $\beta_K = 25$.

     • Since $\alpha (15) < \beta (25)$, no pruning occurs yet.

   • Node K evaluates its right child (0) second:

      

     • Node K updates its upper bound to the smaller value: $\beta_K = 0$.

     • Thus, K = 0.

4. Back at Node E (MAX node):

    

   • Node E compares its children: $\max(J, K) = \max(15, 0) = 15$.

   • Thus, E = 15.

Is Node K Pruned?

No, Node K is fully evaluated, and neither of its children is pruned.

 

Both children of K (25 and 0) are visited to determine that $K = 0$.

 

The node that actually gets pruned in this game tree is Node G:

 

• When evaluating C (MIN node at Level 2), its left child F returns 3 (since $\min(L, M) = \min(2, 3) = 3$, after L evaluates 0 and 2).

• Node C now has $\beta_C = 3$.

• Since ancestor node A (MAX node) already has $\alpha_A = 15$ (from branch B), node C's bound $\beta_C = 3 \le \alpha_A = 15$ causes an $\alpha$-cutoff.

• Therefore, the entire right subtree under G is pruned.

---

K will also get pruned