Algorithms Explained - minimax and alpha-beta pruning
Vložit
- čas přidán 25. 06. 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
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
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
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)
im happy for your achievement
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 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
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 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
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
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
me after spending 30min on wikipédia : this is black magic
me 2min into Seb's video : I understand everything !
Literally the best resource for minimax out there well done. This is amazing content instant sub
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!
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!
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!!
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.
I was really confused by almost all other videos about this topic, but you made it clear and showed really nice examples. Great video!
I really enjoy the way you combine the code with the visualisation, it is so impressive!
Extremely helpful because you included the code and an in-depth explanation. Thank you!
Absolutely fantastic video, amazing production quality. Just fantastic all around!
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 CZcams is so precious.
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.
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
An incredible tutorial. Simple, quick and legible.
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
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 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.
this video saved sons life, he was terminally ill until i watched this video. its a miracle thank you so much
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.
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!
Finally, a great explanation of alpha-beta pruning! Thank you.
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.
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.
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!
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
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.
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
The best film on yt about minimax and alpha-beta. Thank you!
You scratch the insides of my brain. Thank you.
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 video is a fantastic explanation, clear and well illustrated! Thanks for making it!
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.
Probably the best explanation of a complex topic that I've ever seen
This guy is a legend. Haven't seen a clearer explanation of this algorithm anywhere else.
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.
This video is the best video on CZcams explaining this algorithm.
Man keep updating these cool videos they are helping a lot thanks for your hard work
Really good. I was looking for a better explanation of alpha and beta code wise. This did the job perfectly
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!
Very nice explanation with great visualization. Also very helpful that you showed this pseudcode and went trough it step by step.
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...
Excellent description of the MinMax (w/pruning) approach to searching the tree of possible games.
amazinggg!!! You explained better than my teacher at school
very true
Thank you very much for the explanation, especially about alpha-beta pruning. It was the clearest explanation I saw so far.
Best explanation I've seen so far. Thank you!
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.
You have a very clear voice and it is very easy to follow. Thank you!
You explained in 11 minutes, what the teacher tried and failed in 2 hours and 120 slides! Great Video!
This made so much more sense. Way less cluttered than the other popular video on this topic
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.
Oh well nice timing. We had a class about minimax today. Noice!
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.
This is the best explanation that I was looking for. So clear
Wow! So concise examples and pseudocode: Bravo!
Better then other videos available!!! Nice and thanks!
Well explained man! I knew how it works but I think I still ended up learning something after watching your video.
Aesthetic and condensed. Good video. Good job.
My university took a screenshot of your pseudo code to teach this topic. But without this video is something else. Nice explanation, great work!
This is the best explanation I ever watched, I'm sure !!
Best explanation so far on the entire Internet!!! Thanks a lot
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 CZcams is so precious.
This is the most efficient and effective way I've seen this concept being taught 💯
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 is my first comment ever on CZcams, but I simply had to comment on this one to show my appreciation for how incredible this explanation was! Thank you!
Best explanation of minimax I found. Helped me get through my tic-tac-toe app. Thank You!!
This is the Best algorithm video. It left me min understanding and max confusion.
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.
love it. Keep stuff coming out of the blue :) always interesting
a very intuitive demo of the algorithm
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.
You have forced me to leave a comment, which I rarely do on a CZcams 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.
Wow. That was a wonderful explanation. Love the presentation graphics
Accidentally found this while i was searching your channel for vids to watch, Its perfect cuz i need this for my tic tac toe game
Man, I am trying to program a checker-engine and this video definitely shows how I am going to start. Excellent.
I come from your chess video and this has been amazing. Very well explained!
The best explanation of this algorithm's code!
Thanks for this video mate, you explained this way better and faster than our Professor
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.
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!
Best pseudocode I have seen so far
Minimax? More like "Man, these are some great facts." Thanks for sharing; this was a really illuminating description and demonstration of the algorithms!
Finally! Remarkable explanation! Thank you!!
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!