Algorithms Explained - minimax and alpha-beta pruning

  Переглядів 1,050,170

Sebastian Lague

Sebastian Lague

День тому

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

КОМЕНТАРІ: 716
@yanlinzhu2682
@yanlinzhu2682 5 років тому
The only 13 people that disliked this videos are the branches being pruned.
@jeongtaebang3679
@jeongtaebang3679 5 років тому
comment of the day
@aymarfeed
@aymarfeed 5 років тому
XD
@minorus3549
@minorus3549 5 років тому
branch lives matter
@muhammadroshan7315
@muhammadroshan7315 5 років тому
21 now
@THERedstoneBR
@THERedstoneBR 5 років тому
@@muhammadroshan7315 22 :c
@MrSupa5
@MrSupa5 5 років тому
This is the most aesthetic algorithm video I've seen
@user-li6ev1ro9c
@user-li6ev1ro9c 4 роки тому
It means that you havent seen much of algorithm videos
@bernhardriemann6797
@bernhardriemann6797 4 роки тому
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.
@randomrandom450
@randomrandom450 4 роки тому
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.
@ap-pv7ug
@ap-pv7ug 3 роки тому
@@randomrandom450 As a Computerphile fan, I take personal offense at that.
@puppergump4117
@puppergump4117 2 роки тому
You must not have seen 3blue1brown much
@SebastianLague
@SebastianLague 6 років тому
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.
@AkhilNairjedi18
@AkhilNairjedi18 6 років тому
Sebastian Lague That sounds like a very good idea, thanks a lot!
@daniausimon8674
@daniausimon8674 6 років тому
Hi! Great series idea, i'd love to see your take on some kind of machine learning/neural network stuff, or maybe PID control
@ignaciovillanueva1221
@ignaciovillanueva1221 6 років тому
That's a very good idea. I'm for sure going to follow this series.
@danielrousseau6541
@danielrousseau6541 6 років тому
This is amazing.
@PiyPowKachou
@PiyPowKachou 6 років тому
Cool! Maybe, some procedural generation algorithms?
@kenhaley4
@kenhaley4 3 роки тому
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!
@Walking_W
@Walking_W Рік тому
What if the opponent doesn't play optimally?
@kenhaley4
@kenhaley4 Рік тому
@@Walking_W In that case, the slgorithm will find a solution in fewer moves.
@diogoandre756
@diogoandre756 9 місяців тому
@@Walking_W Then by definition of the word "optimal" he is going to perish faster
@vuhoang5903
@vuhoang5903 4 місяці тому
@@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)
@undercoverdudes
@undercoverdudes 4 роки тому
Incredibly helpful video
@tastyrobot9369
@tastyrobot9369 3 роки тому
Didn't think I'd find you here!
@CH3THIN
@CH3THIN 3 роки тому
mans bout to write a minimax algorithm to play krunker
@SkidFace
@SkidFace 2 роки тому
I'm two years late too- but I do find it funny UCD is here
@qwest500
@qwest500 2 роки тому
Wut
@coldwind8327
@coldwind8327 5 років тому
This is the best explanation I have ever watched about minimax and alpha-beta pruning. Thank you for this.
@duzypokoj1151
@duzypokoj1151 Рік тому
because it's the only one you've seen rotfl lololol get rekd nerd
@Luoze
@Luoze Місяць тому
@@duzypokoj1151 wow so cool! 🤩🤩
@nathanalgren288
@nathanalgren288 3 роки тому
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.
@halbkuppe4895
@halbkuppe4895 3 роки тому
i remember trying to "kill" the pieces my opponent used for capturing important pieces of me..
@MattB90
@MattB90 3 роки тому
lol that's so funny
@nathanalgren288
@nathanalgren288 3 роки тому
@@halbkuppe4895 Ooh, sweet revenge!
@nathanalgren288
@nathanalgren288 3 роки тому
@@MattB90 And better than many human players ;)
@paulminh3525
@paulminh3525 9 місяців тому
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!
@pvtejeswarpanda6324
@pvtejeswarpanda6324 5 років тому
I learnt 2 lecture worth concept in 11 mins with code as a plus. Amazing!!!
@RealJulWhite
@RealJulWhite 2 місяці тому
Wow, 5 years old and still one of the simplest, straightforward videos about these two algorithms/methods!
@THEPAGMAN
@THEPAGMAN 16 днів тому
actually its one algorithm 🤓
@dimensionaldot
@dimensionaldot 6 років тому
I really love this new more CS focused topic, you should do more like this in the future!
@vasile-simionsularea1978
@vasile-simionsularea1978 3 роки тому
Dude, this is freaking amazing. Your skill of explaining complicated concepts in an easy way is fantastic
@GalHorowitz
@GalHorowitz 6 років тому
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
@badimoore
@badimoore 2 роки тому
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!
@rayryeng
@rayryeng 2 роки тому
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!
@machineworld9495
@machineworld9495 4 роки тому
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
@WaseemYusuf
@WaseemYusuf 5 років тому
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!!
@minimanzero2262
@minimanzero2262 5 років тому
Literally the best resource for minimax out there well done. This is amazing content instant sub
@waltersmith8134
@waltersmith8134 3 роки тому
I was really confused by almost all other videos about this topic, but you made it clear and showed really nice examples. Great video!
@eu1860
@eu1860 Рік тому
I really enjoy the way you combine the code with the visualisation, it is so impressive!
@edmund-osborne
@edmund-osborne 4 роки тому
Extremely helpful because you included the code and an in-depth explanation. Thank you!
@gabeharding2643
@gabeharding2643 3 роки тому
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
@martinnolte
@martinnolte 2 роки тому
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
@ElGnomoCuliao
@ElGnomoCuliao Рік тому
fr man
@toilettenbrain7246
@toilettenbrain7246 Рік тому
@@ElGnomoCuliao TUB?
@shitshow_1
@shitshow_1 Рік тому
True, He does lot of mathematical explanations and Game Dev tutorials. Wish I had money so that I can donate or contribute to him : )
@InXLsisDeo
@InXLsisDeo Рік тому
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 UKposts is so precious.
@yourchingoo
@yourchingoo 5 років тому
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.
@ar_1966
@ar_1966 Місяць тому
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.
@Chris-zj2qz
@Chris-zj2qz 24 дні тому
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.
@michaelpersiyanov6131
@michaelpersiyanov6131 4 роки тому
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.
@fledge8422
@fledge8422 2 місяці тому
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
@DennisPing
@DennisPing 2 роки тому
It's nuts that you could fit so much information into 11 minutes. Great video and diagrams.
@AnawneeMawse
@AnawneeMawse 5 років тому
This 10 minute video was more useful than the 2 hours I spent sitting in class to learn this.
@hbcoding5553
@hbcoding5553 Рік тому
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.
@TheRealVicyX
@TheRealVicyX 2 роки тому
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
@LoukasSC
@LoukasSC Рік тому
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!
@Ch1n4Sailor
@Ch1n4Sailor 5 років тому
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...
@Dominik-K
@Dominik-K 2 роки тому
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
@frontire_ace
@frontire_ace 2 роки тому
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.
@DatSwif
@DatSwif Рік тому
For me, this video has pruned hours of searching for how this algorithm works. Thank you so much for this nice and clear explanation!
@randomrandom450
@randomrandom450 4 роки тому
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.
@anmolchandrasingh2179
@anmolchandrasingh2179 2 роки тому
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.
@sokmalinowy6038
@sokmalinowy6038 2 роки тому
An incredible tutorial. Simple, quick and legible.
@shadowzero3673
@shadowzero3673 8 місяців тому
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!
@dwang2805
@dwang2805 4 роки тому
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.
@thosan3090
@thosan3090 6 місяців тому
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.
@MattYang
@MattYang 4 роки тому
Absolutely fantastic video, amazing production quality. Just fantastic all around!
@Maarc15.
@Maarc15. 3 роки тому
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!
@youtubecommenter5122
@youtubecommenter5122 3 роки тому
Probably the best explanation of a complex topic that I've ever seen
@ShubhamGupta-nm1tz
@ShubhamGupta-nm1tz 4 роки тому
This guy is a legend. Haven't seen a clearer explanation of this algorithm anywhere else.
@chaoticprogramming
@chaoticprogramming 2 роки тому
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.
@gabrielmarcondes9814
@gabrielmarcondes9814 2 роки тому
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.
@puppergump4117
@puppergump4117 2 роки тому
If google starts deleting youtube we're all screwed anyways.
@keithdavis00
@keithdavis00 3 роки тому
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!
@lvl5popcap
@lvl5popcap 4 роки тому
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.
@jej3125
@jej3125 3 роки тому
Excellent description of the MinMax (w/pruning) approach to searching the tree of possible games.
@barsengin2186
@barsengin2186 2 роки тому
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...
@zzador
@zzador 3 роки тому
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.
@stttrm
@stttrm 3 роки тому
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
@henriquesousa6089
@henriquesousa6089 2 роки тому
Really good. I was looking for a better explanation of alpha and beta code wise. This did the job perfectly
@Ohrenbanane
@Ohrenbanane 2 роки тому
Very nice explanation with great visualization. Also very helpful that you showed this pseudcode and went trough it step by step.
@matthewhelke4332
@matthewhelke4332 4 роки тому
Finally, a great explanation of alpha-beta pruning! Thank you.
@janardhanpolle7255
@janardhanpolle7255 2 місяці тому
This is the most efficient and effective way I've seen this concept being taught 💯
@Coder-zx4nb
@Coder-zx4nb 4 роки тому
This made so much more sense. Way less cluttered than the other popular video on this topic
@haribhatt34
@haribhatt34 2 роки тому
You have forced me to leave a comment, which I rarely do on a UKposts 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.
@efecantepe3990
@efecantepe3990 2 роки тому
Man, I am trying to program a checker-engine and this video definitely shows how I am going to start. Excellent.
@diegotrazzi
@diegotrazzi 4 роки тому
This video is a fantastic explanation, clear and well illustrated! Thanks for making it!
@eeriksp
@eeriksp 4 роки тому
You have a very clear voice and it is very easy to follow. Thank you!
@omritahar-yakimgames4212
@omritahar-yakimgames4212 Рік тому
You scratch the insides of my brain. Thank you.
@dhimanashish
@dhimanashish 3 роки тому
Well explained man! I knew how it works but I think I still ended up learning something after watching your video.
@committedcoder3352
@committedcoder3352 3 роки тому
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.
@jatinsaini7790
@jatinsaini7790 3 роки тому
This video is the best video on UKposts explaining this algorithm.
@poneis88
@poneis88 3 роки тому
Thank you very much for the explanation, especially about alpha-beta pruning. It was the clearest explanation I saw so far.
@saokz7
@saokz7 2 роки тому
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.
@InXLsisDeo
@InXLsisDeo Рік тому
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 UKposts is so precious.
@cristibranisteanu5338
@cristibranisteanu5338 4 роки тому
You explained in 11 minutes, what the teacher tried and failed in 2 hours and 120 slides! Great Video!
@danielhalachev4714
@danielhalachev4714 5 місяців тому
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.
@slepyy3
@slepyy3 6 років тому
The best film on yt about minimax and alpha-beta. Thank you!
@taelocalxo4264
@taelocalxo4264 9 місяців тому
wow this is an amazing explanation and really made be feel excited when I finally understood
@TheDannyjoblack
@TheDannyjoblack 2 місяці тому
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.
@SeppahBaws
@SeppahBaws 6 років тому
Oh well nice timing. We had a class about minimax today. Noice!
@rafsangoni6979
@rafsangoni6979 3 роки тому
My university took a screenshot of your pseudo code to teach this topic. But without this video is something else. Nice explanation, great work!
@simonroed6921
@simonroed6921 3 роки тому
This is my first comment ever on UKposts, but I simply had to comment on this one to show my appreciation for how incredible this explanation was! Thank you!
@TeyimPila
@TeyimPila 2 роки тому
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
@rodrigoborjas7727
@rodrigoborjas7727 4 роки тому
This is the Best algorithm video. It left me min understanding and max confusion.
@code1997
@code1997 5 років тому
Thanks for this video mate, you explained this way better and faster than our Professor
@JO-vj9kn
@JO-vj9kn 4 роки тому
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.
@scienceofart9121
@scienceofart9121 3 роки тому
This is the best explanation that I was looking for. So clear
@adnansamivlogs7789
@adnansamivlogs7789 2 місяці тому
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!
@ollieellis6189
@ollieellis6189 3 роки тому
having the edges colour schemed was super useful thank you
@vanessaifrah
@vanessaifrah 5 років тому
Well explained and complete! This is the best video I've watched on this topic. Thanks for this.
@marcosalmistraro7869
@marcosalmistraro7869 2 роки тому
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
@Seannyoo900
@Seannyoo900 4 роки тому
Best explanation I've seen so far. Thank you!
@nocturn9x
@nocturn9x 7 місяців тому
I come from your chess video and this has been amazing. Very well explained!
@Dark_Peace
@Dark_Peace 3 роки тому
me after spending 30min on wikipédia : this is black magic me 2min into Seb's video : I understand everything !
@evetsize
@evetsize 4 роки тому
Best explanation so far on the entire Internet!!! Thanks a lot
@geoffreymartin8019
@geoffreymartin8019 7 місяців тому
Best explanation of minimax I found. Helped me get through my tic-tac-toe app. Thank You!!
@JoseTorres-tr6od
@JoseTorres-tr6od 5 років тому
Look at the pruning that happens from 8:01 to 8:03. When he claims that node is "
@angusmclellan918
@angusmclellan918 5 років тому
Thanks for the explanation
@reema7277
@reema7277 5 років тому
Thanks a lot! thought he made a mistake
@bigsmerdo
@bigsmerdo 3 роки тому
yo thanks i was bare confused
@levanlomia9046
@levanlomia9046 3 роки тому
Thanks for explanation
@WalksWithBooks
@WalksWithBooks 2 роки тому
My alternate formulation of the same concept. Looking at 1:06 (ukposts.info/have/v-deo/pF2ZnGtopZmYpX0.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 "
@dmuiruri
@dmuiruri 2 роки тому
a very intuitive demo of the algorithm
@Dlegend7
@Dlegend7 4 роки тому
I can say that after hours of university and hours of studying I finally understood how these algorithms works and how pruning in general works! Thank you so much
@meowjustme6865
@meowjustme6865 4 роки тому
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
@leducphuclong
@leducphuclong 5 місяців тому
This is the best explanation I ever watched, I'm sure !!
@yuxiaofei3442
@yuxiaofei3442 Рік тому
so clear,this is what call good education video,deep explain,yet damn easy grasp
@_mrundercoverhd_
@_mrundercoverhd_ 3 роки тому
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!
@AliAli-wi2ys
@AliAli-wi2ys 2 роки тому
4 years after and still useful
@parthgeek
@parthgeek 4 роки тому
One of the best video i have seen so far on AI. GOOD JOB BROTHER
@spinipsFI
@spinipsFI 3 роки тому
Wow! So concise examples and pseudocode: Bravo!
Procedural Landmass Generation (E01: Introduction)
3:28
Sebastian Lague
Переглядів 1 млн
Minimax with Alpha Beta Pruning
13:44
John Levine
Переглядів 318 тис.
Surprise Gifts #couplegoals
00:21
Jay & Sharon
Переглядів 28 млн
когда одна дома // EVA mash
00:51
EVA mash
Переглядів 10 млн
Minimax: How Computers Play Games
14:37
Spanning Tree
Переглядів 187 тис.
Best OS for programming? Mac vs Windows vs Linux debate settled
8:41
Fast Inverse Square Root - A Quake III Algorithm
20:08
Nemean
Переглядів 4,8 млн
Coding Adventure: Chess
29:22
Sebastian Lague
Переглядів 3,7 млн
Mastering Dynamic Programming - How to solve any interview problem (Part 1)
19:41
How Do Computers Remember?
19:32
Sebastian Lague
Переглядів 6 млн
The ARM chip race is getting wild… Apple M4 unveiled
4:07
Fireship
Переглядів 700 тис.
Binary Search Algorithm - Computerphile
18:34
Computerphile
Переглядів 153 тис.
Surprise Gifts #couplegoals
00:21
Jay & Sharon
Переглядів 28 млн