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:

Support the creation of more tutorials:

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

[MrSupa]

This is the most aesthetic algorithm video I've seen

[kenhaley]

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!

[yanlinzhu]

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

[coldwind]

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

[pvtejeswarpanda]

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!

[nathanalgren]

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.

[ar_]

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.

[machineworld]

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

[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

[Khoaky]

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.

[gabeharding]

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

[vasile-simionsularea]

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

[haroldiv]

Two minutes into this video taught me more than an hour's lecture my university gave.

[AnawneeMawse]

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

[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

[lvlpopcap]

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.

[albamo]

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!

[austinmontgomery]

brother you are my computer science lifeline. thank you for all the videos, you have helped me in multiple classes and in my own personal development in computer graphics tremendously.