Algorithms Explained - minimax and alpha-beta pruning
ฝัง
- เผยแพร่เมื่อ 28 เม.ย. 2024
- This video covers the minimax search algorithm, as well as how it can be sped up using alpha-beta pruning.
Pseudocode:
pastebin.com/VSehqDM3 - plain minimax
pastebin.com/rZg1Mz9G - alpha beta
Support the creation of more tutorials:
/ sebastianlague
![How to Get a Developer Job - Even in This Economy [Full Course]](http://i.ytimg.com/vi/6nz8GXjxiHg/mqdefault.jpg)
![[TH] VCT Pacific - Regular Season - สัปดาห์ที่ 4 วันที่ 1 // BLD vs PRX | GE vs DFM](http://i.ytimg.com/vi/MdnZuQ1-pas/mqdefault.jpg)
The only 13 people that disliked this videos are the branches being pruned.
comment of the day
XD
branch lives matter
21 now
@@muhammadroshan7315 22 :c
This is the most aesthetic algorithm video I've seen
It means that you havent seen much of algorithm videos
There's a lot of pleasing algorithms, Diffie-Hellman key exchange is pretty cool. Merkle Trees are quite nice as well. Though I'd say a lot of recursive tree-functions are pleasing.
Yeah, way to many "some dude drawing on a piece of paper with a camera pointed at it". There are literally two of them in my recommended videos on the right.
@@randomrandom450 As a Computerphile fan, I take personal offense at that.
You must not have seen 3blue1brown much
Hello! I know this topic's a bit out of the blue, but I thought it might be interesting to do a series of videos on different algorithms. Let me know if you like the idea, and if you do, if there are any particular algorithms you'd like to see covered.
Sebastian Lague That sounds like a very good idea, thanks a lot!
Hi! Great series idea, i'd love to see your take on some kind of machine learning/neural network stuff, or maybe PID control
That's a very good idea. I'm for sure going to follow this series.
This is amazing.
Cool!
Maybe, some procedural generation algorithms?
I just implemented minimax as described here to play tic-tac-toe in Python. When player goes first, minimax gets called a total of 60,692 times. With alpha-beta pruning, the number of calls is reduced to 8,542, which I found amazing. Thanks for this simple explanation and pseudocode!
What if the opponent doesn't play optimally?
@@Walking_W In that case, the slgorithm will find a solution in fewer moves.
@@Walking_W Then by definition of the word "optimal" he is going to perish faster
@@Walking_W Well, if the player makes a move that is not considered optimal (according to the evaluation function) then the bot would gain even more benefit than it expected since the algorithm assumption is both players will make the optimal move. Also, this is just the algorithm, whether the bot is considered smart or not depends mostly on the evaluation function of the bot (this is where all the strategies of the bot go)
This is the best explanation I have ever watched about minimax and alpha-beta pruning. Thank you for this.
because it's the only one you've seen rotfl lololol get rekd nerd
@@duzypokoj1151 wow so cool! 🤩🤩
I like the respect the chess engine has for me when it's playing its moves... It assumes I'll play the most rational move.
i remember trying to "kill" the pieces my opponent used for capturing important pieces of me..
lol that's so funny
@@halbkuppe4895 Ooh, sweet revenge!
@@MattB90 And better than many human players ;)
When I play my chess game in chessboard app, it always plan to take out my powerful pawn in the games as a way to maximize its victory. Thus, sometimes I decide I play bolder that the chess AI in my iPad could no longer respond to my move. I play on medium level in it thus it fit to my current capabilities as novice chess player for fun in free time. When I try a harder level, it beat me restlessly that I could not respond at all. I feel like an idiot and thus couldn’t adapt to new strategies. I couldn’t play save with an AI at all. I always tried to be initiative as much as possible!
Incredibly helpful video
Didn't think I'd find you here!
mans bout to write a minimax algorithm to play krunker
I'm two years late too- but I do find it funny UCD is here
Wut
I learnt 2 lecture worth concept in 11 mins with code as a plus. Amazing!!!
Wow, 5 years old and still one of the simplest, straightforward videos about these two algorithms/methods!
actually its one algorithm 🤓
I really love this new more CS focused topic, you should do more like this in the future!
This 10 minute video was more useful than the 2 hours I spent sitting in class to learn this.
Dude, this is freaking amazing. Your skill of explaining complicated concepts in an easy way is fantastic
OMG!! This is the first of your videos I am seeing and I simply can't express how good it is. The way you showed the code and stepped through it to explain was just so ELEGANT! Liked, commented and subscribed!!
This video was great! The style was super good for such videos. I think a good algorithm to continue on with is the Monte Carlo tree-search algorithm
Shout out to my man Sebastian for not only being one of my favorite game dev youtubers but also explaining things so much better than my college professor
true, i found him when I got into Unity and stuff and now im pleased every time i look up an algorithm from my AI course and the first video suggested is by him
fr man
@@ElGnomoCuliao TUB?
True, He does lot of mathematical explanations and Game Dev tutorials. Wish I had money so that I can donate or contribute to him : )
To be fair it's more time consuming but also easier to explain in a video rather than live because you have all the time you need to go into as much detail as you need and correct your mistakes before releasing, while when you are on the blackboard, you have to think about what you are saying live, so it's easy to make mistakes or overlook something, or be less cleaar than you want to be. A video is more akin to writing a book chapter or a blog post. But that's why TH-cam is so precious.
I really enjoy the way you combine the code with the visualisation, it is so impressive!
I was really confused by almost all other videos about this topic, but you made it clear and showed really nice examples. Great video!
Understanding the basic idea of a-b pruning wasn't too difficult, but it took this video for me to really get how to implement it in code. Thanks!
This video is not only better in quality but having the code side-by-side as well as stepping through an example really set it over the top. I'm currently taking the AI Udacity Nanodegree course and I could not make sense of what they were talking about when they tried to explain minimax and alpha beta pruning. This video did such a better job and I'm now able to understand what's going on. Thanks so much!
Not only did you provide super good tutorials for a procedural generation project, this also helped me with my introductory AI course! I owe 50% of this semesters credit to you my man
me after spending 30min on wikipédia : this is black magic
me 2min into Seb's video : I understand everything !
Extremely helpful because you included the code and an in-depth explanation. Thank you!
Literally the best resource for minimax out there well done. This is amazing content instant sub
This channel is by far the most interesting and useful channel I've ever come across, and im so glad I've been able to watch and learn from these videos over the past few years. thank you, truly
This is such a well made video. Really helped me understand and you even went out of the way to show us an example of the code too. Thank you for this.
I love this video.
I've been searching for an easy explanation for the *idea* behind alpha-beta pruning for days. The video just took a few seconds for me to get it.
Subscribed.
It's nuts that you could fit so much information into 11 minutes. Great video and diagrams.
I recently found your channel and those AI or algorithm videos are very interesting. Love your approach, voice over and video style. Learned a ton by watching and trying to implement those algorithms
Your robotic and static pace of the voice makes it even more amazing, although I am struggling but that's my problem. The step-by-step procedure of your explanation pathway seemed pretty good! Thanks fam.
Dude this video is awesome, it explained the algorithm, how it works, and even gives pseudocode for it with worked examples. I'm not kidding when I say that this video is more effective than the university lectures. Thanks man, you're a lifesaver.
Thank you so much for this. Many people explain minimax codes and alpha beta pruning, but none that I have seen actually gave some sort of coding example. Thank you for this. its amazing.
An incredible tutorial. Simple, quick and legible.
Great video man!! The simple walk through for the last example really helped me get a solid understanding of the algorithm. Keep up the good work.
What a god. Was looking through all my lecture slides and didn't understand the concept at all... Watched this video and understood the whole concept in minutes... thank you.
For me, this video has pruned hours of searching for how this algorithm works. Thank you so much for this nice and clear explanation!
This is one of the best explanations I've come across. I'm currently programming a Ruby chess game and this is invaluable. Thank you so much!
Thank you!!! The best, simplistic and straight-forward example in I've seen... Thank you for making this understandable... Every other video on this (other than yours...!) leaves you more confused than the last...
Thank you, after a couple of videos explaining minimax + alpha-beta pruning, I got the idea of the theory but couldn't figure out the code that is... in the end pretty simple when you explain it. Simple recursion, a dept first search passing down a min and max as parameters. Thank you for the simple step by step explanation.
Probably the best explanation of a complex topic that I've ever seen
Absolutely fantastic video, amazing production quality. Just fantastic all around!
This is literally the only video that I found helpful to fully understand the Minimax and the codes to implement it.
Have subscribed the channel.
Absolutely the best explanation of Minimax and AB Pruning, I just got an A+ in my AI final exam this semester, thank you so much sir.
the way you did that loop was really smart. thoughout the video i was thinking of doing 'if then's but when i realized that you can just use the same function over and over to a certain depth that blew my mind. Very helpful for making efficient code
My professor tried to explain this yesterday and kept messing up so I got nothing out of it.
I'm glad this video exists because the homework is due regardless.
Omg, alpha-beta pruning works so good. I'm making my tic tac toe using minimax and at first i decided to simplfy it by not using pruning. My bot needed about 5 seconds(!) to calculate all the possible turns. Then i added alpha-beta and now it completes its turn instantly! So cool
You have forced me to leave a comment, which I rarely do on a TH-cam video. This is the only video/explanation I have watched for Minimax and Alpha beta pruning. I can confidently says, the only one anyone might need. The code for minimax could have been intimidating, but you explained it beautifully. I subscribed your channel even though I don't do graphic stuff, just a random DS Algo guy. I am happy that I stumbled upon this video. Would love if you keep uploading some more DS Algo Videos.
Finally, a great explanation of alpha-beta pruning! Thank you.
You explained in 11 minutes, what the teacher tried and failed in 2 hours and 120 slides! Great Video!
I am doing an online master's and this was taught in 54 video lectures. I have watched all 54 videos but I only understood what they were trying to teach after watching this single video
This guy is a legend. Haven't seen a clearer explanation of this algorithm anywhere else.
Studying computer engineering at college, taking a class on AI right now. They have explained this to me about 5 times, and not a single one i've understood how it works. I watch once your video because YT decided to show it to me, and suddenly i understand it all... Man you are the best! Thanks!
This explanation is miles better than that of my professor. I am a great student and went on here for guidance in rather simplistic terms, and you beautifully delivered.
This is the most efficient and effective way I've seen this concept being taught 💯
Excellent description of the MinMax (w/pruning) approach to searching the tree of possible games.
I really like your videos. Your voice is so soothing it's almost as Bob Ross would have given a programming course. All your code is well explained and easily understandable. Besides that your videos are incredibly inspiring.
You scratch the insides of my brain. Thank you.
Nice. I've been teaching this on and off to summer interns for a couple of decades from published papers and a whiteboard, but this video will be a first-stop teaching tool--thanks!
Thanks! I was trying to make a chess AI since your video but I might have overstepped my current skill bounds so I am making a checkers AI, and this sped it up a lot! I am still looking for more improvements, but this was great to start out.
Thanks so much. I have watched so many videos about alpha-beta pruning and I haven't been able to understand. I have just watched this video and I have understood at the moment. Thanks for your pure explanation. Actually simplicity is so important to explain for foreign people who are not good at English. Again Thank you so much...
You have a very clear voice and it is very easy to follow. Thank you!
Very nice explanation with great visualization. Also very helpful that you showed this pseudcode and went trough it step by step.
Really good. I was looking for a better explanation of alpha and beta code wise. This did the job perfectly
The best film on yt about minimax and alpha-beta. Thank you!
This video is the best video on TH-cam explaining this algorithm.
This video is a fantastic explanation, clear and well illustrated! Thanks for making it!
this video is so good that I will download and backup it everywhere possible so civilization never loses this encapsulated knowledge.
super job mate.
your channel is just awesome.
If google starts deleting youtube we're all screwed anyways.
Thank you very much for the explanation, especially about alpha-beta pruning. It was the clearest explanation I saw so far.
My university took a screenshot of your pseudo code to teach this topic. But without this video is something else. Nice explanation, great work!
Oh well nice timing. We had a class about minimax today. Noice!
Fantastic work! I'm basing my AI agent solely on this video so hope it's correct ;) It's so much more intuitive to see it animated than reading some greek pseudocode.
Man, I am trying to program a checker-engine and this video definitely shows how I am going to start. Excellent.
Thanks for this video mate, you explained this way better and faster than our Professor
amazinggg!!! You explained better than my teacher at school
very true
Well explained man! I knew how it works but I think I still ended up learning something after watching your video.
This is my first comment ever on TH-cam, but I simply had to comment on this one to show my appreciation for how incredible this explanation was! Thank you!
Minimax? More like "Man, these are some great facts." Thanks for sharing; this was a really illuminating description and demonstration of the algorithms!
This is the best explanation that I was looking for. So clear
having the edges colour schemed was super useful thank you
Best explanation I've seen so far. Thank you!
I feel like I need to send this video to my professors so that they can learn how to teach.
In particular I loved how you ended the video. Really brought home the power of AI and it's relevance. Felt like a "so what?" Never really thought about how important that was because none of my CS professors has ever done it right.
To be fair it's more time consuming but also easier to explain in a video rather than live because you have all the time you need to go into as much detail as you need and correct your mistakes before releasing, while when you are on the blackboard, you have to think about what you are saying live, so it's easy to make mistakes or overlook something, or be less cleaar than you want to be. A video is more akin to writing a book chapter or a blog post. But that's why TH-cam is so precious.
This is the Best algorithm video. It left me min understanding and max confusion.
Best explanation so far on the entire Internet!!! Thanks a lot
When I first watched this video so long ago, I was so confused, but now I’ve done my first year of CS at college and it makes perfect sense! Wow. Weird that education actually did something for me.
I paid thousands of dollars to go for university. Ended up listening and understanding more from an 11 minute video from youtube. Thanks alot man
Look at the pruning that happens from 8:01 to 8:03. When he claims that node is "
Thanks for the explanation
Thanks a lot! thought he made a mistake
yo thanks i was bare confused
Thanks for explanation
My alternate formulation of the same concept. Looking at 1:06 (th-cam.com/video/l-hh51ncgDI/w-d-xo.html ) sorry about formatting; rush job.
//quote Jose Torres 3 years ago (edited)
Look at the pruning that happens from 8:01 to 8:03. When he claims that node is "
Thank you for this video. I finally understood the algorithm, even though you didn't even use the triangle notation to represent maximizers and minimizers.
I study computer science at the TU in Berlin Germany and had really big problems with this algorithm!
So ty a lot! You probably safed a few points for me!
This made so much more sense. Way less cluttered than the other popular video on this topic
Best explanation of minimax I found. Helped me get through my tic-tac-toe app. Thank You!!
Wow! So concise examples and pseudocode: Bravo!
Your explanation is way better than my teacher did... Thanks!
a very intuitive demo of the algorithm
Incredible...I listened to an hour long lecture without understanding it and all I needed was a 11min video.
This is the best explanation I ever watched, I'm sure !!
thank you so so much man. You managed to explain this in a much much better way than the professor at my uni, who took 1.5 h to basically say nothing.
May the gods be in your favor
I am working on a bot for a turn-based game and for calculating a depth of 6 there were 10 million possibilities. This number went down to 20k because of pruning. Thanks!
I come from your chess video and this has been amazing. Very well explained!
best vedio on minax i came accross . It is way way better than the MIT lectures .
My God, thank you so much for uploading this. My professor can't explain any of this, so You Tube is my lifeline at the moment. God bless you in your endeavours InshaAllah!
Wow. That was a wonderful explanation. Love the presentation graphics