Today we are going to solve a sum on alpha beta pruning. So in alpha beta pruning we basically have two values alpha and beta and prune basically means we are going to ignore the next branches. We will understand this when we will solve the example.
So alpha contains the maximum value and beta contains the minimum value. So let's start the sum. This is our given sum.
This is our starting node. So the first thing what we are going to do is we are going to alternately write max max for this one max min max min okay and now what we're going to do is we're going to start uh so the sum by initializing alpha is equal to minus infinity since alpha always contains the maximum value we are going to initialize it with a with a negative value a least value basically and beta is equal to plus infinity now as we know as we traverse in a tree what we do is we go left by left left hand side will be traced first so let's let's do that so these values will go down Beta is equal to infinity. This will become alpha is equal to minus infinity. Beta is equal to infinity. Left hand.
Now again here alpha is equal to minus infinity. Beta is equal to infinity. Now.
now here what is this min min means beta so only beta value will be changed in this this node so now now we are going to again check from left to right now left is for for beta is infinity small or 10 small obviously 10 so this will change to 10 but now again right hand side is 5 small or 10 small 5 so 5 will be put over here now again on top it will go now over here here what is the value max so only alpha will be changed now is minus infinity big or is minus infinity big or 5 is big which Which one is a bigger number 5? So infinity will be changed to 5. I mean alpha will become 5. Now this same value will go downwards. And this will become alpha is equal to 5, beta is equal to infinity.
Now again beta min. What is the value of the node of here? Min.
So only beta will be changed. So what it will become is infinity. And at every node we have to check whether alpha is equal to infinity. is greater than equal to beta if that happens that particular node will be pruned i mean the next branch will be pruned um i'll show it when when it comes now beta is equal to infinity is infinity small or seven small seven so seven will come over here is seven now here is seven small eleven small seven only so seven will remain away now it will go on top now over here what is the value max only alpha will be changed so is five big and max means maximum value so is 5 big or 5 is big or 7 is big the values over here will be checked so is 5 big or 7 big 7 so 7 will over will come over here okay now it will go on top it will go on top now here what is the value of the min i mean what is the value of the node min min means beta will be changed beta will be changed now is in beta means minimum value so is b beta minimum or 7 minimum or sorry is infinity minimum 7 minimum or infinity is minimum 7 is the least value here so it will become 7 correct now now this will go over here right it will go on the left side here then it will go on top and then right that's how it is now over here again the same values will be repeated downwards alpha is equal to minus infinity beta is equal to 7 now Now over here what is the value?
Min. Beta will be changed. So is 7 small or 12 small?
Now what is the value over here? Max. So alpha will be changed. So is minus infinity big or minus infinity big or is 7 big? 7 is big.
So 7 will come over here. But as you can see alpha is equal to. beta y and the condition is alpha should be greater than or equal to beta so it is equal to beta so this will prune itself prune means now we don't have to traverse this this is not going to be the solution so we prune it So, we save the time of traversing it.
So, this is the basic of alpha beta. Now, as we reach over here, we will go on top. Now, again here, what is the value of the node? Min. Min means beta.
Now, what is the beta? Now, 7, 7 or 7, which is the minimum? 7 only.
So, 7 will come here. Now, it will go on top. Here, maximum. Now, since max is over here, alpha will be changed.
So, minus infinity, minus infinity or 7, which is the maximum? 7. So, this will cut to 7. Now again it will go downwards. Now same values will be repeated. Same values will be repeated here. again down alpha is equal to 7 beta is equal to infinity now here what is the value of the node min min means beta now which is small 5 5 or infinity 5 now but now if you see alpha is 7 beta is 5 means alpha is greater than beta the same condition so pruning condition so this will be prune now we don't have to traverse this node so this is the condition now we'll go on top now here what is the value max now 7 7 of i which is the maximum 7 same thing will be there now again over here alpha is equal to 7 beta is equal to infinity now now we have to what is the value over here min min means beta beta should be changed so infinity or 11 which is least 11 now similarly now over here 11 or 12 which is minimum 11 only so 11 will appear now over here now if you see maximum means alpha so 7 7 or 11 which is maximum 11 so this will become 11 correct correct now it will go on top now minimum so infinity 11 or infinity which is minimum 11 so this will become 11 Right?
Alpha is equal to 7, beta is equal to 11. Now again, same values will be repeated here. And we cannot prune it because alpha is less than beta over here. So nothing is going to happen. Go down.
Alpha is equal to 7, beta is equal to 11. equal to 11 now here min beta will be changed so 11 or 9 which is minimum 9 so 9 will come over here then over here 9 or 10 which is minimum 8 so 8 will come over here right 8 and 9 nothing will be proved now again now we'll go on top now maximum value max max here so alpha will be changed so 7 7 or 8 what is maximum 8 so 8 will come over here now alpha is equal to 8 beta is equal to 11 Alpha is equal to 8, beta is equal to 11. Now, what is the value over here? Min. Min means beta will be changed. So, 11 or 7. What is a smaller number?
Because we have to change beta. 7 is a smaller number. 7. Now, if we see alpha is greater than beta. So, this will be pruned. So, this is our solution.
Thank you.