Minimax with Alpha Beta Pruning

Поделиться
HTML-код
  • Опубликовано: 22 дек 2024

Комментарии •

  • @bryanbocao4906
    @bryanbocao4906 6 лет назад +231

    Great explanation! Some important notes as well:
    1) only in a Max node can update the corresponding alpha, so does Min for beta.
    2) v can only be returned up to its parent
    3) alpha and beta can only be passed down from its parent
    4) cut the current node from the tree whenever alpha >= beta
    In the graph on the right whiteboard, shouldn't all the alpha, beta are initialized as -infinity and infinity, respectively?
    At 13:07, for the completeness of the logic flow, I think we should set the beta to be 2 in the node(v=2, alpha=8, beta= ), then because alpha(8) > beta(2), we prune the right subtree.

    • @rampage14x13
      @rampage14x13 5 лет назад +9

      all solid things to point out, thanks

    • @kingtqos1514
      @kingtqos1514 5 лет назад

      It works like a charm, Thanks!

    • @superuser8636
      @superuser8636 4 года назад +6

      Yeah, this algorithm is total shit

    • @imnacho4127
      @imnacho4127 3 года назад +3

      beta would never assigned the value of two; the function would return before that variable assignment.

    • @kevin-lamquesnel9067
      @kevin-lamquesnel9067 Год назад +1

      Thanks this helped me so much, you have no idea

  • @yashvats9703
    @yashvats9703 Год назад +3

    He is god. He explained everything in just 13 minutes. I wish if I came across this video earlier it could have saved my time. Great teacher!!

  • @amellperalta
    @amellperalta 7 лет назад +154

    Excellent explanation! The video is clear, concise, and precise. We want more videos from you. Please teach us more about AI.

  • @oshawastaken
    @oshawastaken 2 года назад +5

    5 year later and still best video on alpha-beta pruning. Thank you sir.

    • @johnlevine2909
      @johnlevine2909  2 года назад +4

      Thanks for making me feel old! Very glad it's useful 😀

  • @PauloViniciusMoreiraDutra
    @PauloViniciusMoreiraDutra 3 года назад +2

    the best explanation about minimax. You are a great professor. I watched a lot of videos about minimax algorithm, but only your video I understood clearly

  • @GtaRockt
    @GtaRockt 3 года назад +18

    Great teacher, got a B on my AI exam with your videos about tree search algorithms 👌 explained it way better in a couple of minutes than my teacher in an hour

  • @RahulSam
    @RahulSam 7 лет назад +136

    You are a great lecturer, not many people can do this.

  • @nilsmartel2295
    @nilsmartel2295 4 года назад +3

    Every single time I see that you have uploaded a video about a topic, I lose all fear, that I'm not going to be able to understand it. This is not an exaggeration, you've helped me avoid so much confusion and desperation. Thank you so much John!

  • @jonathancui3063
    @jonathancui3063 4 года назад +12

    As a self-learner, this video is by far the best explanation I've ever seen. Clean, concise, and to the point.

  • @jabodey
    @jabodey 6 лет назад +14

    THANK YOU SIR! I finally know alpha beta pruning!!! Your explanation was crystal clear. If you taught my AI course, I would never ditch class!!

  • @sagnik3105
    @sagnik3105 7 лет назад +12

    This definitely has to be the most thorough explanation I found on the topic. Thank you! :D

  • @andrewweems9427
    @andrewweems9427 7 лет назад +5

    Your videos are so concise and helpful. They're the only thing keeping my grade decent in my Intelligent Systems class.

  • @adamkawsara6881
    @adamkawsara6881 6 лет назад +2

    Wonderful video. This helped a lot! Working through the example in real time and explaining your thought process as you went really helped make this click.

  • @kiyimbafahad6169
    @kiyimbafahad6169 3 месяца назад +1

    This is the hotest content online about this chapter!
    So concise and precise!🎉

  • @mkamp
    @mkamp 7 лет назад +38

    Thanks. That was my nth video on that topic and this time it clicked. Thanks for taking the time to go through it so deliberately. :)

  • @XxBleedRainbowxX
    @XxBleedRainbowxX 6 лет назад +1

    Just wanted to thank you for your great videos! Watching them pre-exam to refresh and they're all very clear and informative

  • @prasangsinghal262
    @prasangsinghal262 5 лет назад +4

    He saved my exam. Thnxx sir for such a great explanation.

  • @AdityaRaj_Purohit
    @AdityaRaj_Purohit 6 лет назад +5

    One of the best video on youtube to understand Alpha Beta pruning.
    Want more video like this to get more understanding of AI.

  • @pellekools6475
    @pellekools6475 7 лет назад +2

    Great explanation! I already knew what steps to take, but it wasn't really clear why I should take those steps. It is clear to me now.

  • @Fionasfung
    @Fionasfung 2 года назад

    This is the best video I have seen which explains the algorithm along with the graph.

  • @benaya6
    @benaya6 5 лет назад +1

    it's just amazing. all your videos are the definition of crystal clear explanation. perfect. I wish you'll do more videos

  • @syedahabali2450
    @syedahabali2450 7 лет назад +4

    Respect to you sir. You explained it so well! I'm very grateful!

  • @ArushitMudgal
    @ArushitMudgal 6 лет назад +3

    Watched it in approximately 9 minutes (X1.5 speed) and this has been the most precise and to-the-point explanation I have watched so far and believe me I have watched many. Thank you sir

  • @BeSharpInCSharp
    @BeSharpInCSharp 4 года назад

    I have to admit you are the only one who could explain and impart knowledge to even the dumbest person like me. You are the great great teacher.

  • @meharabdullah8608
    @meharabdullah8608 7 лет назад +2

    Fantastic explanation. No one on RUclips has ever explained this algorithm so nicely using it's pseudo code . Very nice Sir, Respect

  • @GauravYadavdv31
    @GauravYadavdv31 6 лет назад

    One of the best explanation, Thank you John Levine.

  • @cookiejar3094
    @cookiejar3094 8 месяцев назад

    Your videos help me so much with my course, thanks!

  • @mesosiderite4670
    @mesosiderite4670 Год назад +3

    I want to thank you sir,
    you have done what my teacher was unable to do, a good explanation,
    it took me three days to understand this, and finally I understood thanks to this video

  • @dadas7852
    @dadas7852 7 лет назад +10

    This is the best video about this topic

  • @ahlamalbimani2070
    @ahlamalbimani2070 6 лет назад

    Thank you. I've seen many videos and could not understand until I saw this video. Many thanks for your clear explanation!!

  • @hemmahbeast
    @hemmahbeast 6 лет назад

    Nice lesson, Biblo. The great eye watching you is pleased.

  • @fejohnson
    @fejohnson 6 лет назад +2

    this is amazingly helpful for me! thank you sir for this explanation!

  • @_justinxu
    @_justinxu 4 года назад

    Don't expect to instantly understand this topic, but your video did it. Thanks. :D

  • @Jantol93
    @Jantol93 3 года назад

    The best explanation of alpha beta pruning. "If the value is greater than beta that means min is going to prefer the branch that lead to beta." That line made it click for me.

  • @Shimu-x8r
    @Shimu-x8r 13 дней назад

    I'm so thankful that this video exists in RUclips ❤❤❤❤

  • @rv.9658
    @rv.9658 2 года назад

    Watching this once saves me so much time that might've gone into reading through a textbook section on this particular algorithm

  • @dbnnoman5596
    @dbnnoman5596 3 года назад

    Thank You so much sir!
    God Bless you!

  • @sergiovasquez5643
    @sergiovasquez5643 3 года назад +1

    Great presentation of work. would it be possible to link the supplementary material associated with this lecture?

  • @TheZ0mi
    @TheZ0mi 6 лет назад

    Thank you Sir, after checking many videos on the same topic, your lecture makes me understand the topic.

  • @trenduniverse3826
    @trenduniverse3826 2 месяца назад

    God Bless This Beautiful Explanation🙏

  • @onecleanrun
    @onecleanrun 6 лет назад

    Brilliant explanation. Just what I needed. Thank you.

  • @shivamroy1775
    @shivamroy1775 7 лет назад

    Thank You . You're an amazing teacher .

    • @johnlevine2909
      @johnlevine2909  7 лет назад +2

      Thanks Shivam! Glad you found it useful.

  • @ريمالمحمد-ن2ت
    @ريمالمحمد-ن2ت Год назад

    Thank you for this amazing video and explaination, not many have the ability to do this 🌸🖤

  • @nh1622
    @nh1622 6 лет назад

    Really good!! Thanks for taking the time to explain it properly.

  • @nassimmehalli7043
    @nassimmehalli7043 6 лет назад +1

    an excellent teacher , thank's a lot. we'r waiting for more courses about AI :) Good luck

  • @jennachen1411
    @jennachen1411 5 лет назад

    Thank you very very much! It takes a long time for me to understand the alpha-beta pruning .Luckly ,I find this vedio.

  • @ManishSharma-cf3or
    @ManishSharma-cf3or 6 лет назад

    Awesome!! Seen most of your videos(Loved A* video too) and I must say that this topic was a bit tricky till I saw this ! You make it sound so simple

  • @johnphilipespia1167
    @johnphilipespia1167 3 года назад

    Thank you so much! You're the best!!

  • @sashinthat3173
    @sashinthat3173 2 года назад

    Goated Explanation Sir!

  • @alexanderyau6347
    @alexanderyau6347 6 лет назад +3

    Wow, this lecture helps me understand the alpha-beta algorithm, the pseudo code is very helpful to understand. Quite intuitive. Where is the link for the assignment?

  • @TrangPham-kc7ft
    @TrangPham-kc7ft 4 года назад

    Thank you so much for your video. It's really clear.

  • @madeline-qk3vg
    @madeline-qk3vg Год назад

    this is life-saving sir thanks a lot ^-^

  • @Noah-357
    @Noah-357 9 месяцев назад

    What would be a real life example ?. For example, when robo vacuum is trying to clean a house, what would be the example of pruning here ?. Is pruning happening when robo vacuum for example when it says task finish although it's not like skipping task because there are an obstacles blocking its way?

  • @dijkstra5952
    @dijkstra5952 6 лет назад

    Is it just me or is he the actor who played Benjamin Linus from LOST (Michael Emerson)? He both looks and speaks exactly like Ben.

  • @Tash98
    @Tash98 5 лет назад

    The only explanation that made sense to me!

  • @dimmo15
    @dimmo15 6 лет назад +1

    Thank you sir! I was wondering if there is a formula that can calculate the maximum number of nodes that can be pruned in a tree with a depth of d and a branching factor of b.

  • @vinicius2699
    @vinicius2699 6 лет назад +1

    Damn, you are good. Thanks for helping

  • @nicolemb05
    @nicolemb05 Год назад

    This is so helpful!! Thank you so much!

  • @hangchen
    @hangchen 4 года назад

    OMG! Very very clear! I came from CS188 step by step.

  • @xdxdxd1
    @xdxdxd1 5 лет назад

    Amazing videos! Thank you!

  • @dien2971
    @dien2971 5 лет назад

    Thank you, sir. You are a great teacher!

  • @AntonAtef
    @AntonAtef Год назад +1

    Great explanation 👌

  • @j_m_b_1914
    @j_m_b_1914 2 года назад +1

    I must be missing something because the following scenario seems like a possible scenario where alpha beta pruning can discount a superior position down the road.
    In chess, isn't it possible to have a move sequence where moves 6 ply out may show an inferior score for white but if the line was analyzed further, we'd see that white might be able to force a mate by taking a material loss. Wouldn't alpha beta pruning possibly discount such a line by abandoning further computational depth for that line such that it would never be able to see that a temporary drop in maximization of white's score actually sets up for a win for white?
    I guess my question can be reduced to this:
    Is it possible for alpha beta pruning to discount a line that is temporarily inferior (low score) but a few moves further out we discover a forced mate? Could alpha beta pruning throw out the analysis for such lines?
    Also, the entire principle of the minimax algo (in my opinion) is the scoring we give specific positions based on what information has been learned about chess over the centuries. We rank certain material with specific scores and also certain positions with specific scores. If the methodology of scoring the current state of the chess game is imperfect, then the minimax algo may not always be 100% optimal in the search tree it explores based on those scores.
    Let me give a quick counter example to (hopefully) better illustrate my argument. In the game of chess, there is really only one ultimate score -- is there a sequence of moves from the current game position where white (or black if playing black) can force a checkmate of the opposing king. Every other analysis within the game is of no consequence if it doesn't lead to a line where the opposing king is checkmated (or if checkmating is not possible, the only other analysis of consequence is trying to draw the current game). A new chess engine called Oracle is created using hardware from thousands of years into the future. Oracle is able to analyze 100 ply within the game in a matter of microseconds. Oracle discovers a line where white sacrifices four pieces (let's say a pawn, a knight, a bishop and a rook) in order to force a mate on the opposing king approximately 20 moves out.
    Now in this example, wouldn't current engines stop processing this line after the first or second piece was lost because the minimax score / alpha beta pruning? The current engine might discount the sequence of moves and call the first sacrifice a blunder because it never processed this particular line deeper.
    I could be way off here because my knowledge of minimax with A/B pruning is incomplete -- that's why I'm throwing this out there for others with more experience. Is this a disadvantage of minimax with AB pruning?

  • @jebaanto7649
    @jebaanto7649 3 года назад

    Awesome explanation sir thanks from india

  • @DAISY-d2u
    @DAISY-d2u Месяц назад

    I did not understand why the last branch was pruned, at V=2,alpha=8 and beta=' '(where the values are 9,-1), alpha was definitely > 9 and alpha>beta

  • @SentryProductions1
    @SentryProductions1 6 лет назад

    Would the -2 value not be pruned as we have a deep cut off situation ? We can see that Max will be = 8? Is there point in exploring -2?

  • @AGCrush
    @AGCrush 3 года назад

    Great Explanation! Thanks alot.

  • @amirbaba9677
    @amirbaba9677 3 года назад

    this video was so helpful.
    thank you.

  • @aynurememmedova9436
    @aynurememmedova9436 2 года назад

    Thanks teacher...I watch your videos in Azerbaijan✨

  • @user-xp3me9ws9c
    @user-xp3me9ws9c 6 лет назад

    thank you for the video, it really helped me a lot doing my exam study!!

  • @jonesmukuta1910
    @jonesmukuta1910 3 года назад

    Good work right there!!!

  • @hadialhassan5078
    @hadialhassan5078 3 дня назад

    amazing explanation
    would be better to set Alpha to -minus infinity and Beta to Plus infinity and to set v initially to -infinity if we're max and +infinity if we're min. Helps clarify the decision making.

  • @TheTahlia1988
    @TheTahlia1988 7 лет назад +2

    Again, superb teaching. Thank you!

  • @bushrhaddad3141
    @bushrhaddad3141 6 лет назад

    Very clear explanation, Thank you

  • @harrisonjin8359
    @harrisonjin8359 4 года назад

    Best explanation by far

  • @linh6360
    @linh6360 5 лет назад

    thank you so much for the lecture.

  • @tonycui6891
    @tonycui6891 2 года назад +1

    Alpha-beta pruning using {v, α, β}: 4:33

  • @simoneditzzz
    @simoneditzzz 2 года назад

    thanks man, you gave me a great favor

  • @mohamedibrahimhassan291
    @mohamedibrahimhassan291 2 года назад

    loved the way you explaine

  • @pratyushshrivastava4362
    @pratyushshrivastava4362 9 месяцев назад

    Great explanation!

  • @llcooljake1
    @llcooljake1 7 лет назад

    Thank you! Finally clicked after watching this video.

  • @김건우-t8s
    @김건우-t8s Год назад

    Thanks. your explain is quit clear😊

  • @guoshenli4193
    @guoshenli4193 3 года назад

    great explanation!!! Thank you!!!

  • @bangminh5712
    @bangminh5712 7 лет назад

    Please make a video on Negamax as well, would be perfect if includes Transposition in the algorithm either. And thanks for the lesson, thank you.

  • @dgglovesbb
    @dgglovesbb Год назад

    Thank you so much!

  • @s70591520
    @s70591520 3 года назад

    this guy makes me wanna go back to school

  • @beri4138
    @beri4138 4 года назад

    Very good video. I will now attempt to code my own tic-tac-toe solver :)

  • @matteomastandrea5680
    @matteomastandrea5680 2 года назад

    this mans single handedly getting me through AI

  • @joaquinvanloon7341
    @joaquinvanloon7341 7 лет назад

    Great video, great explanatiom!

  • @ammarzorig2771
    @ammarzorig2771 4 года назад

    Thank you Dr

  • @blackfromabove9383
    @blackfromabove9383 3 года назад

    Many thanks for explanation!

  • @ImranAkbarUK
    @ImranAkbarUK 6 лет назад +1

    very good Explanation Sir! :)

  • @hoomanjafari4633
    @hoomanjafari4633 5 лет назад

    Thanks a lot, you made my day !

  • @shantanulokhande3730
    @shantanulokhande3730 Год назад

    Thank you so much sir. !!!!

  • @trongnguyenhuu1005
    @trongnguyenhuu1005 Час назад

    i got exam on paper, so can i show it on paper because proffessor just look the paper, can not watch step i take like update value of alpha and beta?

  • @konstantinrebrov675
    @konstantinrebrov675 4 года назад

    You did not define the term "pruning". What do you mean "that will show you where the search can be pruned"?

    • @beri4138
      @beri4138 4 года назад

      It means the search will never explore that path. Pruned nodes and their child nodes will be ignored by the minimax algorithm to save computing time.

  • @shehrozkhan9563
    @shehrozkhan9563 2 года назад

    Sirrr love your vids

  • @patriknovotny7219
    @patriknovotny7219 7 лет назад

    Hello, is there any chance to get slides, what are you talking about in video ? Thank you :)

  • @simha3154
    @simha3154 7 лет назад

    This is amazing. Thanks!

  • @mertdusunceli5159
    @mertdusunceli5159 6 лет назад

    why does 8 get placed as alpha in the level 2 right node ?