Some important notes: 1) only in a Max node can update the corresponding alpha, so does Min for beta. 2) v can only be returned up to its parent 3) alpha and beta can only be passed down from its parent 4) cut the current node from the tree whenever alpha >= beta
While examining the children of a maximizer, if v of maximizer > beta, prune the rest of the children. While examining the children of a minimizer, if v of minimizer < alpha, prune the rest of the children.
Thanks for the video! Even though this is a relatively simple algorithm, the only way to really understand it is to go step by step on a toy problem, like you did. Excellent job!
+Dinh Hung Nguyen Attention please at minute 2:28 !!! Hello :) Thank you very much for your explaination. It is very helpful. The algorithm checks whether the value 4 is higher or equal !!! to beta. Thank you, BR
A very good explanation. A lot of people are complaining about how this could be more simple, but look at the title, it shows you if how exactly algorithm would do this.
To be honest, I found MIT's lecture is a little bit better. The lecturer at MIT (Patrick Winston) provides more intuition behind the alpha beta pruning, while Prof Pieter Abbeel, although shows clear logic behind each step, does not give us reson for why you should do this, and the example is a bit complicated as well. So I personally recommend watching the MIT's AI lecture 6 at first, then watching this.That would be a perfect complement.
In the branch to the right, alpha is already set to 6. This means that the v should be set to 6 initially in the max-nodes, not -infinity as is shown in the video. If you find this hard, look up the minmax algorithm. Alpha-beta is built upon minmax
Anyone else following the General Game Playing course on Coursera? The Alpha-Beta Search was by far the most confusing one (because of lack of an example) so far in the lectures and this helped a lot.
+moraigna66 Also, there was a lack of a well defined system. No where it mentions how the alpha must only come from "above" for a minimizer but the same minimizer can use a beta from a previously explored "lower" branch and vice-versa for the maximizer.
Very well detailed explanation of alpha beta pruning given Sir! You are really a good teacher, saved me from this confusing algo! I was tearing my hair getting to understand this, until i came over to your video. Thank you so much!
it makes sense, but classifying the variable as internal structure of a node would've simplified your explanation greatly, and explaining that there appears to be two forms of pruning, local pruning and greater pruning, local where the local scope of an object is taken into account, in the first instance of the prune shown in this video; and the second where the tactical decision to circumvent this option was taken because no matter what option the maximizer presented to the minimizer the minimizer would've taken the value 2 or lower; as thats where it seems you confused alot of people. note i'm not stating there are different prunes, they use the same strategy just the reasoning behind the prune is different which i've represented with different names.
Why is the second child of the middle minimizer pruned? below as a child of minimizer is a maximizer. The v value of the maximizer between 0 and 1 is 1. So at the minimizer we have v = 1, because 1 is the better option than 2.
Pretty good explanation. I think the hard to get part, for me, is the best path to the root concept. But if one works through some trees, I think it becomes more clear.
A little bit messy But still 100 times better than my University's AI lecturer My understandeing: When a maximizer is going to look at other children, check if it already has a value that is greater than the best minimizer value along its way to root, you can stop it because the only thing it can do is to make this value more than the current value, however the current value is already greater than the best minimizer value, so the upper minimizer will discard this node anyways. Same thing to a minimizer, if it discovers its value is already smaller than the best maximizer value, you can stop it from expanding, because the only thing it can do is to keep lowering that value and it will be discarded later.
I found this very helpful especially once the values of alpha and beta weren't just infinity and -infinity! I kept pausing the video and working through a couple steps then playing the video to see if I did them right, which really helped me grasp when you change the values of alpha and beta. Great video although it did take me a couple watches to fully get it!
a good student need not be a good teacher. to become a really good teacher, you need to spend 10 times more time thinking what is the best innovative way so that my students can grasp this concept easily.
Which part, or what aspects lost you? This stuff always seems like magic at first, but asking questions, discussion, and going t/ examples really helps. I've been trying a few problems before this video, and it really helped make some of the steps click.
It's well explained it even has to much info, like addition of minimizer at the (main) root. But if you don't understand this I suggest dodging any kind of algorithm based courses in the future
Great tutorial, really helped me. But why are alpha and beta passed to leaf nodes? Is this because they're passed before we know its a leaf when implemented?
13:39. It can't be pruned because what happens if that 2 was a 7. When it gets to the minimizer, a 7 is lower than the 8. Therefore it wins, when it gets to the root, the 7 is greater than the 6 therefore the 7 wins. Thus it can't be pruned.
Thanks a lot! I understand it much better now :) btw, i have a strange question: how do u write on the screen? is it a special digital pen? thanks again :)
How do you know the nodes are sorted like this such that the max/min knows to prune vs the other node being possibly lower on the same depth pair? (Like when 7 prunes 9 and it was swapped order)
Congratulations, very well explained. It was very usefull for me. I agree there is not much tutorials which explain this concept as u do. Again, congratulations and thank you man.
At around 2:22 to 2:29, Pieter says "for that it checks the following conditions: it checks whether this value of 4, the current value here is higher than beta. If that's the case, then it doesn't need to look at any further children here..." He should have said "...higher than OR EQUAL TO beta."
9:05 : How are we so sure that there is a lower value in the next branch, thus pruning this branch? I lack the understanding of how you come to that conclusion. If anyone could clear that up for me, I thank you so much.
+1stMusic Ah, it's not that there's a value less than 2 in the right branch, it's that the minimizer has has the option to choose 2 at that node (and possibly a lower value than 2 if it turns out that the right branch does have a lower value). Since the minimizer has the ability to choose a 2 (or maybe lower) in the main center branch, the maximizer would compare the value of 2 with the value of 6 to see which is higher. If the maximizer chooses the center branch then the minimizer would be able to force a game value of 2 or less; however if the maximizer chooses the left branch then the minimizer only has the ability to force a value as low as 6. thus the maximizer will only want to choose the left branch at that point, no matter what other unexplored values there are in the center branch. Hope that helped if you were still wondering about that.
Wait. Why isn't beta changed in the middle tree with 2 as its maximizer? When 2 is the max for the node, wouldn't it be propagated up to the minimizer node? Alpha isn't changed but shouldn't beta be changed from +inf to 2? And since alpha > beta, the whole right subtree is pruned.
So alpha beta pruning I've found is not explained well by ANYONE individually. I tried geeksforgeeks and hackerearth. I sort of grokked the logic, but then I realized something was missing. So, I came here. The idea that alpha and beta get passed down and up were actually huge, what helps is that alpha goes updated exclusively with maximizers. Beta gets updated exclusively with minimizers. If alpha is greater than beta, you prune the remaining trees if there are still unexplored trees.
Honestly, there are much better ways to explain this. The whole infinity and -infinity adds unnecessary confusion to really just mean "we don't know what it could be yet"
Consider a chess game, and there are only 2 moves available, hence two paths. The cost function or heuristic is (number of white pieces - number of black pieces). The Maximizer is the white player, who wants to maximize that heuristic function, while the black is the minimizer. But, each players' moves depend on the opposite player moves. Here, the top node is white, i.e. it is his move, hence it is the Maximizer. 2nd level is black's move i.e. minimizer, third is again white's move, hence maximizer. e.g.the 2nd level minimizer will minimize the inputs from both maximizers at 3rd level. "So, white is maximizing among all the black's minimized values and vice versa" Pruning is carried out bcoz, since minimizer will not allow that maximum value even though explored.
Ok not knocking the professor, but seriously, this was quite unclear and then more unclear, and then just muddy. For the best explanation check out John Levine's video: ua-cam.com/video/zp3VMe0Jpf8/v-deo.html - he explains the minmax algorithm - he then explains the pruning algorithm. - it is simple - it is not messy - it is concise and not rushed.
Some important notes:
1) only in a Max node can update the corresponding alpha, so does Min for beta.
2) v can only be returned up to its parent
3) alpha and beta can only be passed down from its parent
4) cut the current node from the tree whenever alpha >= beta
Thanks man that helped A LOT .
While examining the children of a maximizer, if v of maximizer > beta, prune the rest of the children.
While examining the children of a minimizer, if v of minimizer < alpha, prune the rest of the children.
💯
Thanks for the video! Even though this is a relatively simple algorithm, the only way to really understand it is to go step by step on a toy problem, like you did. Excellent job!
You saved my ass right before my A.I exam
+Dinh Hung Nguyen yeah
+Dinh Hung Nguyen
Attention please at minute 2:28 !!!
Hello :)
Thank you very much for your explaination.
It is very helpful.
The algorithm checks whether the value 4 is higher or equal !!! to beta.
Thank you, BR
i have an AI exam in a few hours lol
me 2
one advice: Keep it clean and clear !!
A very good explanation. A lot of people are complaining about how this could be more simple, but look at the title, it shows you if how exactly algorithm would do this.
To be honest, I found MIT's lecture is a little bit better. The lecturer at MIT (Patrick Winston) provides more intuition behind the alpha beta pruning, while Prof Pieter Abbeel, although shows clear logic behind each step, does not give us reson for why you should do this, and the example is a bit complicated as well. So I personally recommend watching the MIT's AI lecture 6 at first, then watching this.That would be a perfect complement.
Thank you for sharing. I understand better now.
Yes you are absolutely right, he explains it much better!
Yup, watch the MIT lecture first then this one! Helps so much
exactly......followed your sequence ........helped a lot
Agree, you are correct. The lecture explained better than this guy. Maybe I was a dumb or something. Can't get this video's idea T^T
This video helped me understand pruning better thank you! Those of you complaining abt how messy it is, draw it yourself as he goes along.
In the branch to the right, alpha is already set to 6. This means that the v should be set to 6 initially in the max-nodes, not -infinity as is shown in the video. If you find this hard, look up the minmax algorithm. Alpha-beta is built upon minmax
Always initiate unexplored max node to -infinity
6 hours before the exam and I'm studying now. Why am I like this
Anyone else following the General Game Playing course on Coursera?
The Alpha-Beta Search was by far the most confusing one (because of lack of an example) so far in the lectures and this helped a lot.
+moraigna66 Also, there was a lack of a well defined system. No where it mentions how the alpha must only come from "above" for a minimizer but the same minimizer can use a beta from a previously explored "lower" branch and vice-versa for the maximizer.
If you understand the minima concept, this is an awesome explanation and it really helped me a lot. Thank you
I know it makes sense and all, but it sure does take a few minutes for it to sink in and stick. Glad you went through the entire process.
Very well detailed explanation of alpha beta pruning given Sir! You are really a good teacher, saved me from this confusing algo! I was tearing my hair getting to understand this, until i came over to your video. Thank you so much!
Worst teacher
why? You didnt understand the explanation? :(
Nope. Nada.
:-(
This is a great explanation. I am shocked to see that some people disliked this video....
it makes sense, but classifying the variable as internal structure of a node would've simplified your explanation greatly, and explaining that there appears to be two forms of pruning, local pruning and greater pruning, local where the local scope of an object is taken into account, in the first instance of the prune shown in this video; and the second where the tactical decision to circumvent this option was taken because no matter what option the maximizer presented to the minimizer the minimizer would've taken the value 2 or lower; as thats where it seems you confused alot of people. note i'm not stating there are different prunes, they use the same strategy just the reasoning behind the prune is different which i've represented with different names.
Why is the second child of the middle minimizer pruned? below as a child of minimizer is a maximizer. The v value of the maximizer between 0 and 1 is 1. So at the minimizer we have v = 1, because 1 is the better option than 2.
Pretty good explanation. I think the hard to get part, for me, is the best path to the root concept. But if one works through some trees, I think it becomes more clear.
this makes a lot of sense if you've already seen this like at least a dozen times. if you're new, don't even waste time watching this
A little bit messy
But still 100 times better than my University's AI lecturer
My understandeing:
When a maximizer is going to look at other children, check if it already has a value that is greater than the best minimizer value along its way to root, you can stop it because the only thing it can do is to make this value more than the current value, however the current value is already greater than the best minimizer value, so the upper minimizer will discard this node anyways.
Same thing to a minimizer, if it discovers its value is already smaller than the best maximizer value, you can stop it from expanding, because the only thing it can do is to keep lowering that value and it will be discarded later.
I found this very helpful especially once the values of alpha and beta weren't just infinity and -infinity! I kept pausing the video and working through a couple steps then playing the video to see if I did them right, which really helped me grasp when you change the values of alpha and beta. Great video although it did take me a couple watches to fully get it!
wish i could hit like button 100 millions times
thanks man God bless yuh
peace
a good student need not be a good teacher.
to become a really good teacher, you need to spend 10 times more time thinking what is the best innovative way so that my students can grasp this concept easily.
First you do this.
Then this.
Then magic.
More magic.
Done. Do you understand now?
are you kidding me?? or are you a kid in real??? best explained ? where is deep cutting you dumb??
Which part, or what aspects lost you? This stuff always seems like magic at first, but asking questions, discussion, and going t/ examples really helps. I've been trying a few problems before this video, and it really helped make some of the steps click.
It's well explained it even has to much info, like addition of minimizer at the (main) root. But if you don't understand this I suggest dodging any kind of algorithm based courses in the future
that's because the depth is only 4
😂😂
Listen to the explanation around 09:00 . "A maximizer has a better option than two- six" which comes from the previous branch, incidentally.
you dont know how much u saved me. thanks so much man
Great tutorial, really helped me. But why are alpha and beta passed to leaf nodes? Is this because they're passed before we know its a leaf when implemented?
Excellent walk through!
13:39. It can't be pruned because what happens if that 2 was a 7. When it gets to the minimizer, a 7 is lower than the 8. Therefore it wins, when it gets to the root, the 7 is greater than the 6 therefore the 7 wins.
Thus it can't be pruned.
2:27
should be: current value is higher OR EQUAL than beta
Thanks a lot! I understand it much better now :)
btw, i have a strange question: how do u write on the screen? is it a special digital pen?
thanks again :)
Thanks a lot. Well explained!
I am not sure why others did not get it. Maybe if you first check the theory, then watch this, you should get it.
that video kind of saved my ass. thank you. maybe you can explain when the cut is called a-cut and when it is calles b-cut
How do you know the nodes are sorted like this such that the max/min knows to prune vs the other node being possibly lower on the same depth pair? (Like when 7 prunes 9 and it was swapped order)
Congratulations, very well explained. It was very usefull for me.
I agree there is not much tutorials which explain this concept as u do.
Again, congratulations and thank you man.
Thanks :) Currently working on this in my AI class and this helped a lot.
At around 2:22 to 2:29, Pieter says "for that it checks the following conditions: it checks whether this value of 4, the current value here is higher than beta. If that's the case, then it doesn't need to look at any further children here..."
He should have said "...higher than OR EQUAL TO beta."
Thank you. This helped me a lot !!
9:05 : How are we so sure that there is a lower value in the next branch, thus pruning this branch? I lack the understanding of how you come to that conclusion.
If anyone could clear that up for me, I thank you so much.
+1stMusic Ah, it's not that there's a value less than 2 in the right branch, it's that the minimizer has has the option to choose 2 at that node (and possibly a lower value than 2 if it turns out that the right branch does have a lower value). Since the minimizer has the ability to choose a 2 (or maybe lower) in the main center branch, the maximizer would compare the value of 2 with the value of 6 to see which is higher. If the maximizer chooses the center branch then the minimizer would be able to force a game value of 2 or less; however if the maximizer chooses the left branch then the minimizer only has the ability to force a value as low as 6. thus the maximizer will only want to choose the left branch at that point, no matter what other unexplored values there are in the center branch.
Hope that helped if you were still wondering about that.
Tori Knorth Thanks, I got it!
I think that the 6th leaf, the number 2 is wrong, isnt it suposed to be the 6 a better option?
much appreciated, very thorough explanation yet clear and simple.
This is the best video explanation on youtube for alpha beta pruning
No, it's not.
nope
ua-cam.com/video/zp3VMe0Jpf8/v-deo.html&ab_channel=JohnLevine
way better
Only this is clear and accurate tutorial i have found on the internet..today is my AI exam..thanks a lot to you.
Hey thanks for video if we apply alpha beta pruning right to left instead of left to right is it effect the result thank you
This was really helpful for me. Thank you!
This is a really well explained video. Thanks Pieter
This video helped me very much with my Artificial Intelligence course. Thank you for taking the time to make this video.
Such a messy explanation, I got more confused than I was before watching this video
Hi, what if the first node is negative value? For example, if it is -5?
Pretty much how Dragon Ball tournament was organized
lmao. dbsuper sucked ballz
dragon ballz that is ;)
underrated comment ...
Wait. Why isn't beta changed in the middle tree with 2 as its maximizer? When 2 is the max for the node, wouldn't it be propagated up to the minimizer node? Alpha isn't changed but shouldn't beta be changed from +inf to 2? And since alpha > beta, the whole right subtree is pruned.
Clear as mud
Minute 8:26 why is he sending up 2? instead of 6 which is the highest alfa, beta is still infinity. Dont understand this, is he doing wrong?
Thank u sir.I have an A.I exam tomorrow.
best ever the best the most best fantastic explanation thank you prof.
nice video,I can understand the notion now.
Minimisehuhhas an option 4:30
Got me cracking midst an exam revision session.
Nice speech, could finally understand the concept with of this vid
Thank you so much for this video!!!!
Why I can't have a lecturer just like you!!!!!!
Great video, really helped! (I'm a junior majoring in AI and Robotics)
Sir,it would be better if you explain it in different slides ....it is very difficult to understand.
This is brilliant, much appreciated sir.
Might be hard if you're learning alpha beta pruning for the first time but excellent for review.
I thought this would explain prune, the game...
What language are you speaking?
Great video! I finally understood how alpha-beta pruning works! Thanx!
5 rewatches later
Its making sense
Wonderfully explained. Thanks a lot!
So alpha beta pruning I've found is not explained well by ANYONE individually.
I tried geeksforgeeks and hackerearth.
I sort of grokked the logic, but then I realized something was missing.
So, I came here. The idea that alpha and beta get passed down and up were actually huge, what helps is that alpha goes updated exclusively with maximizers.
Beta gets updated exclusively with minimizers.
If alpha is greater than beta, you prune the remaining trees if there are still unexplored trees.
You sir, are a GOD
Great video. Thank you.
Thanks, great explanation!
would appreaciate it if the pen explanation was more clear
Thank you Thank you Thank you :)))
Very very helpful for Computer Engineer
Honestly, there are much better ways to explain this. The whole infinity and -infinity adds unnecessary confusion to really just mean "we don't know what it could be yet"
This really helped me understand alpha-beta minimax! Thank you so much!
Great video , very clear .
Thank so much for saving my final *big thumbs up*
Very nice explanation. Thank you :)
Nice and simple! Thanks.
Geniusss!!!! You´v saved my work
Awesome Explaination!
Not all heroes wear capes. ( ; _ ;) Thank you so much for saving a stranger.
Thank you so much, for providing this lecture I was having quite a difficult time understanding how alpha beta pruning works...
This SAVED me on my AI midterm, thank you!
OMG tks sir! you save my life !
Thanks. Helps lots
9:07 going to be even worse for the minimizer. Because minimizer will keep the value
What exactly are minimizer or maximizer?
you are the maximizer. Your opponent is the minimizer.
Consider a chess game, and there are only 2 moves available, hence two paths. The cost function or heuristic is (number of white pieces - number of black pieces).
The Maximizer is the white player, who wants to maximize that heuristic function, while the black is the minimizer.
But, each players' moves depend on the opposite player moves. Here, the top node is white, i.e. it is his move, hence it is the Maximizer. 2nd level is black's move i.e. minimizer, third is again white's move, hence maximizer.
e.g.the 2nd level minimizer will minimize the inputs from both maximizers at 3rd level.
"So, white is maximizing among all the black's minimized values and vice versa"
Pruning is carried out bcoz, since minimizer will not allow that maximum value even though explored.
way too messy
Yes but it does the job
great video
can't thank you enough!
thanks that helped to give me the last hint to understand alpha beta pruning =)
How if alpha and beta's value are the same? we stop?
u prune
thanks a lot prof.
3:22 how is 6 better than positive infinity?
Well it's less than pos inf so which means it isn't higher than the minimizer's current min value so it's valid.
thanks a ton! one of the best explanations :)
amazing explanation!
Thanks very much!
great work
Ok not knocking the professor, but seriously, this was quite unclear and then more unclear, and then just muddy.
For the best explanation check out John Levine's video: ua-cam.com/video/zp3VMe0Jpf8/v-deo.html
- he explains the minmax algorithm
- he then explains the pruning algorithm.
- it is simple
- it is not messy
- it is concise and not rushed.