CODEWITHSUNDEEP
algorithm
Baseus
Baseus

Reputation: 51

Why does min-max and alpha beta pruning return different answers in this scenario?

I'm currently debugging my own alpha beta pruning implementation - I understand why the last two nodes (-10) (-10) are getting pruned, since alpha will be passed as 0 from the root and beta will get set to 0 from infinity after the 0 node is processed on the right, therefore 0 >= 0 and we break before we get to -10. But in doing so, the node on the right gets a different value in the alpha beta pruning algorithm than in the min max algorithm and my implementation picks the rightmost child with a suitable value. Therefore a correct value of 0 is always picked, but different nodes are used based on whether we use simple min max or apply pruning, which is bad for me as I care more about the node and its data than the value.

Am I to understand that it doesn't matter that the value of the node on the right is different with the alpha beta pruning if we were to always pick the left most child with the maximum value on the root if two nodes have the same value?

Min max: Min max

Alpha beta pruning: Alpha beta pruning

Upvotes: 1

Views: 885

Answers (1)

Baseus
Baseus

Reputation: 51

It seems that picking the leftmost child (i.e. the one that was evaluated first) when two nodes have the same value in the alpha-beta pruning algorithm is the correct way. It doesn't matter if the evaluted values in the non-root nodes in min-max differ, since the correct child will still be picked, if we are always using the leftmost child.

For me, changing

bool foundBetterValue = (maximizing ? (childNodeValue >= suitableChildValue) : (childNodeValue <= suitableChildValue));

to

bool foundBetterValue = (maximizing ? (childNodeValue > suitableChildValue) : (childNodeValue < suitableChildValue));

did the trick.

Upvotes: 1

Related Questions