Using the alpha-beta algorithm, which is the correct pruning?

Question

BlackTom AI · Accepted Answer

Alpha-beta pruning tracks two bounds: alpha (best value found so far for MAX) and beta (best value found so far for MIN). We traverse left-to-right, updating alpha/beta and pruning when alpha >= beta.

Step-by-step (left subtree B is MIN; its children D,E,F are MAX nodes; leaves: J=3, K=6, L=8, M=5, N=7, O=5; right subtree C is MIN with MAX children H(R=8,S=6) and I(T=15,U=9)):

1) Root A (MAX): alpha = -∞, beta = +∞. Explore left child B (MIN).
2) At B: alpha inherited = -∞, beta = +∞. Explore D (MAX):
   - D sees J = 3 → D.alpha = 3
   - D sees K = 6 → D.alpha = max(3,6) = 6
   - D returns value 6 to B. B.beta = min(+∞,6) = 6.
   So after D, B has current best = 6 and A.alpha updates to max(-∞,6) = 6.
3) Explore E (MAX) under B:
   - E sees L = 8 → E.alpha = 8.
   - Compare E.alpha (8) with B.beta (6): since E.alpha ≥ B.beta (8 ≥ 6), E cannot produce a value < 6 (MIN at B already has 6), so E’s remaining child M is pruned. (Pruned node: M)
   - E would yield ≥8, so B remains 6.
4) Explore F (MAX) under B:
   - F sees N = 7 → F.alpha = 7.
   - Compare F.alpha (7) with B.beta (6): 7 ≥ 6 so F’s remaining child O is pruned. (Pruned node: O)
   - F would yield ≥7, so B remains 6. B returns 6 to A; A.alpha remains 6.
5) Now explore right child C (MIN) of A with alpha = 6:
   - Explore H (MAX): R = 8 → H.alpha = 8; S = 6 → H.alpha = max(8,6)=8. H returns 8 to C. C.beta = min(+∞,8)=8.
   - Since C.beta (8) > A.alpha (6) no pruning yet.
6) Explore I (MAX) under C with C.beta = 8:
   - I sees T = 15 → I.alpha = 15.
   - Now I.alpha (15) ≥ C.beta (8), so remaining child U is pruned. (Pruned node: U)
   - I would return ≥15; C remains min(8,≥15)=8; A will choose max(6,8)=8.

Pruned leaves: M, O, and U — exactly the pruning pattern labeled P3. Other patterns (P1, P2) prune different nodes incorrectly (they either prune children before the alpha/beta condition holds or fail to prune the two left-subtree children while pruning others incorrectly). Therefore the correct pruning diagram is P3, matching the provided answer.

Using the alpha-beta algorithm, which is the correct pruning? 单项选择题

类似问题

You own a bond that pays $64 in interest annually. The face value is $1,000 and the current market price is $1,021.61. The bond matures in 11 years. What is the yield to maturity?

Which of the following statements is CORRECT?

It will cost $9,600 to acquire an ice cream cart that is expected to produce cash inflows of $3,600 a year for three years. After the three years, the cart is expected to be worthless. What is the payback period?

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单