Algorithms Explained - minimax and alpha-beta pruning

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

[@yanlinzhu2682]

The only 13 people that disliked this videos are the branches being pruned.

[@jeongtaebang3679]

comment of the day

[@aymarfeed]

XD

[@minorus3549]

branch lives matter

[@muhammadroshan7315]

21 now

[@THERedstoneBR]

@@muhammadroshan7315 22 :c

[@MrSupa5]

This is the most aesthetic algorithm video I've seen

[@user-li6ev1ro9c]

It means that you havent seen much of algorithm videos

[@bernhardriemann6797]

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]

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]

@@randomrandom450 As a Computerphile fan, I take personal offense at that.

[@puppergump4117]

You must not have seen 3blue1brown much

[@kenhaley4]

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]

What if the opponent doesn't play optimally?

[@kenhaley4]

@@Walking_W In that case, the slgorithm will find a solution in fewer moves.

[@diogoandre756]

@@Walking_W Then by definition of the word "optimal" he is going to perish faster

[@vuhoang5903]

@@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)

[@nathanalgren288]

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]

i remember trying to "kill" the pieces my opponent used for capturing important pieces of me..

[@MattB90]

lol that's so funny

[@nathanalgren288]

@@halbkuppe4895 Ooh, sweet revenge!

[@nathanalgren288]

@@MattB90 And better than many human players ;)

[@paulminh3525]

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!

[@SebastianLague]

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]

Sebastian Lague That sounds like a very good idea, thanks a lot!

[@daniausimon8674]

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]

That's a very good idea. I'm for sure going to follow this series.

[@danielrousseau6541]

This is amazing.

[@PiyPowKachou]

Cool! Maybe, some procedural generation algorithms?

[@coldwind8327]

This is the best explanation I have ever watched about minimax and alpha-beta pruning. Thank you for this.

[@duzypokoj1151]

because it's the only one you've seen rotfl lololol get rekd nerd

[@Luoze]

@@duzypokoj1151 wow so cool! 🤩🤩

[@undercoverdudes]

Incredibly helpful video

[@tastyrobot9369]

Didn't think I'd find you here!

[@CH3THIN]

mans bout to write a minimax algorithm to play krunker

[@SkidFace]

I'm two years late too- but I do find it funny UCD is here

[@qwest500]

Wut

[@pvtejeswarpanda6324]

I learnt 2 lecture worth concept in 11 mins with code as a plus. Amazing!!!

[@RealJulWhite]

Wow, 5 years old and still one of the simplest, straightforward videos about these two algorithms/methods!

[@THEPAGMAN]

actually its one algorithm 🤓

[@dimensionaldot]

I really love this new more CS focused topic, you should do more like this in the future!

[@vasile-simionsularea1978]

Dude, this is freaking amazing. Your skill of explaining complicated concepts in an easy way is fantastic

[@gabeharding2643]

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]

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]

fr man

[@toilettenbrain7246]

@@ElGnomoCuliao TUB?

[@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]

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 KZbin is so precious.

[@machineworld9495]

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

[@GalHorowitz]

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

[@rayryeng]

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!

[@waltersmith8134]

I was really confused by almost all other videos about this topic, but you made it clear and showed really nice examples. Great video!

[@WaseemYusuf]

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!!

[@badimoore]

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!

[@eu1860]

I really enjoy the way you combine the code with the visualisation, it is so impressive!

[@AnawneeMawse]

This 10 minute video was more useful than the 2 hours I spent sitting in class to learn this.

[@edmund-osborne]

Extremely helpful because you included the code and an in-depth explanation. Thank you!

[@minimanzero2262]

Literally the best resource for minimax out there well done. This is amazing content instant sub

[@fledge8422]

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

[@yourchingoo]

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.

[@TheRealVicyX]

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

[@frontire_ace]

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.

[@michaelpersiyanov6131]

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.

[@DennisPing]

It's nuts that you could fit so much information into 11 minutes. Great video and diagrams.

[@Dominik-K]

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

[@Maarc15.]

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!

[@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.

[@Dark_Peace]

me after spending 30min on wikipédia : this is black magic me 2min into Seb's video : I understand everything !

[@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!

[@anmolchandrasingh2179]

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.

[@randomrandom450]

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.

[@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!

[@lvl5popcap]

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.

[@thosan3090]

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]

Absolutely fantastic video, amazing production quality. Just fantastic all around!

[@dwang2805]

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.

[@Ch1n4Sailor]

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...

[@jej3125]

Excellent description of the MinMax (w/pruning) approach to searching the tree of possible games.

[@cristibranisteanu5338]

You explained in 11 minutes, what the teacher tried and failed in 2 hours and 120 slides! Great Video!

[@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]

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.

[@ShubhamGupta-nm1tz]

This guy is a legend. Haven't seen a clearer explanation of this algorithm anywhere else.

[@youtubecommenter5122]

Probably the best explanation of a complex topic that I've ever seen

[@stttrm]

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

[@sokmalinowy6038]

An incredible tutorial. Simple, quick and legible.

[@TeyimPila]

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

[@janardhanpolle7255]

This is the most efficient and effective way I've seen this concept being taught 💯

[@matthewhelke4332]

Finally, a great explanation of alpha-beta pruning! Thank you.

[@barsengin2186]

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...

[@TheDannyjoblack]

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.

[@Ohrenbanane]

Very nice explanation with great visualization. Also very helpful that you showed this pseudcode and went trough it step by step.

[@diegotrazzi]

This video is a fantastic explanation, clear and well illustrated! Thanks for making it!

[@efecantepe3990]

Man, I am trying to program a checker-engine and this video definitely shows how I am going to start. Excellent.

[@keithdavis00]

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!

[@haribhatt34]

You have forced me to leave a comment, which I rarely do on a KZbin 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.

[@rafsangoni6979]

My university took a screenshot of your pseudo code to teach this topic. But without this video is something else. Nice explanation, great work!

[@henriquesousa6089]

Really good. I was looking for a better explanation of alpha and beta code wise. This did the job perfectly

[@eeriksp]

You have a very clear voice and it is very easy to follow. Thank you!

[@zzador]

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.

[@slepyy3]

The best film on yt about minimax and alpha-beta. Thank you!

[@poneis88]

Thank you very much for the explanation, especially about alpha-beta pruning. It was the clearest explanation I saw so far.

[@gabrielmarcondes9814]

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]

If google starts deleting youtube we're all screwed anyways.

[@chaoticprogramming]

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.

[@_mrundercoverhd_]

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!

[@danielhalachev4714]

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.

[@simonroed6921]

This is my first comment ever on KZbin, but I simply had to comment on this one to show my appreciation for how incredible this explanation was! Thank you!

[@Coder-zx4nb]

This made so much more sense. Way less cluttered than the other popular video on this topic

[@dhimanashish]

Well explained man! I knew how it works but I think I still ended up learning something after watching your video.

[@jatinsaini7790]

This video is the best video on KZbin explaining this algorithm.

[@committedcoder3352]

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.

[@JoseTorres-tr6od]

Look at the pruning that happens from 8:01 to 8:03. When he claims that node is "

[@angusmclellan918]

Thanks for the explanation

[@reema7277]

Thanks a lot! thought he made a mistake

[@bigsmerdo]

yo thanks i was bare confused

[@levanlomia9046]

Thanks for explanation

[@WalksWithBooks]

My alternate formulation of the same concept. Looking at 1:06 (kzbin.info/www/bejne/ol7LmWhno8iaeqs ) 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 "

[@omritahar-yakimgames4212]

You scratch the insides of my brain. Thank you.

[@SeppahBaws]

Oh well nice timing. We had a class about minimax today. Noice!

[@scienceofart9121]

This is the best explanation that I was looking for. So clear

[@Seannyoo900]

Best explanation I've seen so far. Thank you!

[@nocturn9x]

I come from your chess video and this has been amazing. Very well explained!

[@Kudoshi]

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

[@shadowzero3673]

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!

[@marcosalmistraro7869]

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

[@ilkeyigiter3038]

Incredible...I listened to an hour long lecture without understanding it and all I needed was a 11min video.

[@rodrigoborjas7727]

This is the Best algorithm video. It left me min understanding and max confusion.

[@saokz7]

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]

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 KZbin is so precious.

[@Dlegend7]

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

[@code1997]

Thanks for this video mate, you explained this way better and faster than our Professor

[@geoffreymartin8019]

Best explanation of minimax I found. Helped me get through my tic-tac-toe app. Thank You!!

[@evetsize]

Best explanation so far on the entire Internet!!! Thanks a lot

[@ollieellis6189]

having the edges colour schemed was super useful thank you

[@PunmasterSTP]

Minimax? More like "Man, these are some great facts." Thanks for sharing; this was a really illuminating description and demonstration of the algorithms!

[@meowjustme6865]

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

[@JO-vj9kn]

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.

[@spinipsFI]

Wow! So concise examples and pseudocode: Bravo!

[@leducphuclong]

This is the best explanation I ever watched, I'm sure !!

[@ghostfreakali06]

Wow. That was a wonderful explanation. Love the presentation graphics

[@adnansamivlogs7789]

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!

[@MrSonny6155]

I was under the impression that pruning can only occur if there was a value immediately above and that it was doing some sort of local comparison, so seeing 7:23 blew my mind. Now that I've actually seen the algorithm, this makes so much more sense.

[@yuxiaofei3442]

so clear,this is what call good education video,deep explain,yet damn easy grasp