CODEWITHSUNDEEP
algorithmtreeminimaxalpha-beta-pruning
user8488823
user8488823

Reputation: 75

Alpha-Beta Pruning special case?

I'm trying to understand the alpha-beta-pruning algorithm, but there's one specific case that I don't understand.

Given this tree, this is supposed to be the solution. What I don't get is why the nodes marked in red are supposed to have the value 19. Apparently this is a "special case" and the value in the lower red node is 19 because 3 < 9 < 10 < 19 (which is the current value for alpha). Which then results in the node above also having the value 19.

This makes no sense to me, because this would suggest there was a leaf with the value 19 in the rightmost subtree. Is this simply wrong and both nodes should have the value 10?

Upvotes: 1

Views: 501

Answers (1)

trincot
trincot

Reputation: 350147

Whether this node gets value 19 (the value of alpha) or 10 (the greatest value among the children) is a matter of variants that exist in different alpha-beta algorithms. When the maximised value is less than alpha, some algorithms will assign the value of alpha, while others will assign that lesser value (which thus lies outside the alpha-beta window). A similar thing happens with beta.

Whichever method is used, it does not influence the choice of the best move. The alpha-beta window is there to indicate that any value that bubbles up from below that lies outside that alpha-beta window cannot be of importance. There is already a better variant known.

In this case the best variant runs via the middle child node of the root. The maximising player can be sure that at least 19 can be achieved. By assigning either 10 or 19 to the third option comes down to the same conclusion: it is not a better move than we already have.

Upvotes: 4

Related Questions