6. Search: Games, Minimax, and Alpha-Beta

  Переглядів 444,759

MIT OpenCourseWare

MIT OpenCourseWare

10 років тому

MIT 6.034 Artificial Intelligence, Fall 2010
View the complete course: ocw.mit.edu/6-034F10
Instructor: Patrick Winston
In this lecture, we consider strategies for adversarial games such as chess. We discuss the minimax algorithm, and how alpha-beta pruning improves its efficiency. We then examine progressive deepening, which ensures that some answer is always available.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

КОМЕНТАРІ: 261
@66javi66
@66javi66 4 роки тому
Patrick Winston, the professor of this lecture, pass away this July... Thank you Patrick.
@joefagan9335
@joefagan9335 3 роки тому
Oh sorry to hear that. RIP
@ThePaypay88
@ThePaypay88 3 роки тому
is it because of Corona?
@dipmodi844
@dipmodi844 3 роки тому
So sad hearing that, true jem of a teacher. RIP
@BabbyCat3008
@BabbyCat3008 2 роки тому
@@ThePaypay88 His McDonald's belly
@piyushsingh6462
@piyushsingh6462 2 роки тому
,,🙏🏻🙏🏻🙏🏻 respect from India Rest in peace 🕊️🕊️🕊️ A great professor....
@yassinehani
@yassinehani 5 років тому
Minimax : 16:17 alpha beta simple example : 21:51 alpha beta big example : 24:54
@ahmedmamdouhkhaled8750
@ahmedmamdouhkhaled8750 9 місяців тому
thx
@yassinehani
@yassinehani 9 місяців тому
@@ahmedmamdouhkhaled8750 welcome, good luck ^^
@kardsh
@kardsh 7 років тому
didn't pay attention in my classes, now here i am at 4 am watching a lecture from 7 years ago......
@kardsh
@kardsh 7 років тому
thank you for saving my ass. also, Christopher impressed me at the end lol
@darkweiss1234
@darkweiss1234 7 років тому
same boat here mate
@JNSStudios
@JNSStudios 7 років тому
This was 3 year ago... this isn't 2021!
@kardsh
@kardsh 7 років тому
Viral Villager I came from the future
@JNSStudios
@JNSStudios 7 років тому
Nafolchan O.o
@johnnybegood8669
@johnnybegood8669 4 роки тому
R.I.P. Patrick Winston, your work will last forever
@BrunoAlmeidaSilveira
@BrunoAlmeidaSilveira 8 років тому
One of the best lectures in the series, fantastic professor and amazing didactic. Many thanks to MIT for this contribution.
@Atknss
@Atknss 6 років тому
Are u serious? The class and professor disappointed me. The small dwarf guy explains very well. But this professor...Not even close.
@MrEvilFreakout
@MrEvilFreakout 5 років тому
@@Atknss can you tell me where i can find this mestirious dwarf that can help me understand AI, would be much appreciated, thank you in advance :)
@nesco3836
@nesco3836 3 роки тому
I dont know where u study or what u study but this is an amazing lecture abt AI. If u cant follow thats allows seriously conclusions about you tho
@MichielvanderBlonk
@MichielvanderBlonk 2 роки тому
@@MrEvilFreakout I think he plays in Game of Thrones. Ask George R.R. Martin. LOL no seriously I would like to know too. Although I think this lecture was pretty good.
@RyanCarmellini
@RyanCarmellini 8 років тому
Great lecture. Very clearly explained alpha beta pruning. I liked the greater than and less than comparisons on each level. This was much clearer then just defining alpha and beta at each level.
@sixpooltube
@sixpooltube 6 років тому
This is the Breaking Bad of AI lectures. Epic beyond comparison. I've watched it more than once and I've learned something new every time.
@moosesnWoop
@moosesnWoop 4 роки тому
Love these lectures - think about them throughout my day. Well seasoned Lecture. Sad to hear about his passing.
@mass13982
@mass13982 8 років тому
Amazing professor. My hat off to you sir
@JenniferLaura92
@JenniferLaura92 9 років тому
what a great explanation. Elaborated very well! thank you
@codykala7014
@codykala7014 6 років тому
This was an excellent lecture. The explanation of alpha-beta pruning was so clear and easy to follow, and Prof. Winston is excellent at presenting the material in an engaging fashion. And I loved how Prof. Winston goes the extra mile to tie in these concepts to real life situations such as Deep Blue. Thank you so much!
@ishratrhidita9393
@ishratrhidita9393 5 років тому
He is an amazing professor. I would have considered myself lucky to be in his class.
@yyk900820
@yyk900820 6 років тому
Love this professor. Calm clear explanation. Smooth voice. And humour.
@maresfillies6041
@maresfillies6041 9 років тому
For those who want to know where he talks about Min Max go to 25:00. It saved my ass.
@KulbhushanChand
@KulbhushanChand 8 років тому
+Mares Fillies Thanks , World needs more people like you.
@mekaseymour1784
@mekaseymour1784 6 років тому
bless you
@chg_m
@chg_m 6 років тому
fuck you. it starts around min 16.
@flavillus
@flavillus 6 років тому
thats alpha-beta part, not the original min-max.
@zes7215
@zes7215 5 років тому
no such thing as savex about it, doesnt matter, schoolx, scox, these gamex etc. meaningless, cepit, do, be can do,be any nmw and any be perfx. also buyer not seller, always test profx not for test
@adityavardhanjain
@adityavardhanjain Рік тому
This lecture is so good. It clears the concept on a theoretical and practical aspects both.
@insidioso4304
@insidioso4304 6 років тому
Greetings from the Politecnico di Milano; thank you for these beautiful lectures!
@jaceks6338
@jaceks6338 6 років тому
This prof explains stuff so well. Respect.
@Apollys
@Apollys 7 років тому
Wowwww I've never seen anyone evaluate the time cost of brute forcing chess the way he did! Amazing! This guy is just amazing.
@tcveatch
@tcveatch 4 місяці тому
He’s only off by 10^10. While still being right. See my other comment.
@alakamyok1261
@alakamyok1261 4 роки тому
Amazing teacher, thanks to engineers of yesterday, and MIT, we have access to these gems.
@DusanResin
@DusanResin 5 років тому
Great explanation! It's basically everything you need to build any game with AI opponent in one lecture. And you can easily determinate the level of difficulty by limiting the depth level of calculating.
@narobot
@narobot 7 років тому
This is such a great video, I am pretty amazed at how anyone could have came up with this. Great lecture.
@bhargavaramudu3242
@bhargavaramudu3242 4 роки тому
This lecture is awesome...such a great professor he is...I absolutely love him
@shiningyrlife
@shiningyrlife 9 років тому
best minimax and alpha beta pruning explanation i ever see!
@hslyu
@hslyu 2 роки тому
You gave me a great inspiration. Rest in peace my teacher.
@cameronmoore7675
@cameronmoore7675 6 років тому
Came here for a good explanation of alpha-beta pruning, and got what I came for. Fantastic lecture! ...but what really blew me away was how *absurdly clean* that blackboard is. Just look at it!
@EliusMaximus
@EliusMaximus 3 роки тому
Amazing lecture, I am very grateful that this has been recorded, thank you for spreading knowledge for free
@celialiang1485
@celialiang1485 3 роки тому
Thank you for this great speech. RIP professor.
@avinkon
@avinkon 3 місяці тому
Patrick Winston has a great teaching style with a subtle humor , childlike playfulness, enthusiasm , energetic and engaging lecture, enjoyed thoroughly :)
@FreshEkie
@FreshEkie 7 років тому
Excellent, very helpful for my Artificial Intelligence exam. Greetings from Germany.
@dagual4473
@dagual4473 8 років тому
Thanks to the guy who wrote the subtitles. It clearly made me understand beter.
@ohserra
@ohserra 9 років тому
Thank you Professor Patrick! I wish I have had some professors like you!
@sagarpanwar2724
@sagarpanwar2724 4 роки тому
The most clear explanation of Alpha Beta Pruning and Minimax
@OlivierNayraguet
@OlivierNayraguet 4 роки тому
I am into AI and Game Theory now with Columbia Engineering, I really enjoyed this presentation. So long professor.
@myj313
@myj313 5 років тому
Seems like a really nice professor. My AI professor also nice and good teacher but leaves out some details which I learn it from here. Thanks for great courses!
@junweima
@junweima 5 років тому
I pray every day for more lectures
@richardwalker3760
@richardwalker3760 9 років тому
Phenomenal lecture. Thank you.
@zfranklyn
@zfranklyn 6 років тому
Such a great, clear lecturer!
@ahgiynq
@ahgiynq 4 роки тому
Thank you for these great lectures
@shubhamsawant5609
@shubhamsawant5609 2 роки тому
Cleared the outlook for Games search
@themathaces8370
@themathaces8370 3 роки тому
Beautiful lecture. Thanks very much.
@AlexandrSudakov
@AlexandrSudakov 2 роки тому
I wish I had such a lecturer in my university :) Especially I liked the moment about cloud computing at 11:07
@stevenstefano8778
@stevenstefano8778 3 роки тому
Great video and lecture! Required viewing from my AI professor at Pace University. Worth every second!
@IsaacBhasme
@IsaacBhasme 9 років тому
Good lecture. Elaborated very well.
@-_Nuke_-
@-_Nuke_- 5 місяців тому
I wanted to say a huge thank you, this was an amazing lecture! I can only imagine the elegance of modern chess engines like StockFish and LC0... StockFish being a brute force and neural network hybrid and LC0 being a pure neural netword powerhouse... The amount of knowledge someone could get from studying them would be extraordinary! If only I could had the pleasure...
@mofakah5906
@mofakah5906 4 роки тому
Came for just the minimax but I stayed for the whole lecture. Thanks MIT
@garimamandal98
@garimamandal98 Рік тому
Very well explained. All my doubts got cleared
@rohitdas475
@rohitdas475 2 роки тому
Pruning explained in the perfect way !!
@EngenhariadeSoftwareLuciana
@EngenhariadeSoftwareLuciana 8 років тому
perfect lecture!
@GoogleUser-ee8ro
@GoogleUser-ee8ro 5 років тому
Prof Winston is quite a genius in giving funny Memorable names for algorithms - British Museum, dead horse, Marshall Art etc. Also the way he explained how Deep Blue applied minimax + alphabet prune + Progressive Deepening etc immediate relate the material to real-life applications. Good Job! But I hope he could explain more on how paralleled computing helped alpha beta punning in DB.
@MichielvanderBlonk
@MichielvanderBlonk 2 роки тому
Perhaps it can be organized by branch: one process takes a branch, then when it splits it also splits the process in two. Of course when b=15 that can become cumbersome I guess.
@__-to3hq
@__-to3hq 5 років тому
I'm glad I never went to a university, someone like me needs to hear or see something done a few times, this is better for me video lectures from MIT xD
@sondredyvik5815
@sondredyvik5815 9 років тому
Great lecture!
@AChannelFrom2006
@AChannelFrom2006 8 років тому
Thank you very much for these.
@behind-the-scenes420
@behind-the-scenes420 Рік тому
Excellent instructor ever. Love from Comsats Islamabad
@charlesrodriguez6276
@charlesrodriguez6276 3 роки тому
Since school is online anyways and the whole course is project-based for me. I'm going to MIT online for my Fall semester.
@berke-ozgen
@berke-ozgen 2 роки тому
Great and impressive lecture.
@nadianyc9262
@nadianyc9262 5 років тому
you saved my life , thank youu
@perseusgeorgiadis7821
@perseusgeorgiadis7821 Рік тому
Finally. Someone explained this stuff in a way I could understand
@amrmoneer5881
@amrmoneer5881 4 роки тому
This is beautiful. he explained it in simple terms very vell
@davidiswhat
@davidiswhat 5 років тому
Damn, this was good. I ended up skipping the proof like stuff and could only really understood the actual algorithm. Might watch more of these.
@maliknaveedphotography
@maliknaveedphotography 7 років тому
Sir u R Great ! Really This is Excellent Lecture :) Thanks
@keyboard_toucher
@keyboard_toucher Рік тому
Human chess players do use the alpha-beta approach (even if we don't recognize it by name), we just have a lot of additional tricks like heuristics about which moves to explore and the order in which to do so.
@chemicalfiend101
@chemicalfiend101 4 роки тому
I didn't think anyone would call a bulldozer sophisticated, but they are! This course is quite eye-opening.
@dalest.hillaire5542
@dalest.hillaire5542 6 років тому
Very clear and concise.
@brianbaker1124
@brianbaker1124 6 років тому
wonderful lecture
@robertjurjevic6580
@robertjurjevic6580 8 років тому
thanks for this lecture :)
@35sherminator
@35sherminator 8 років тому
Great lecture
@maresfillies6041
@maresfillies6041 9 років тому
Awesome lecture, I have a test on these topics today. :D
@larry_the
@larry_the 2 роки тому
How'd you do on it?
@shawntsai3277
@shawntsai3277 7 років тому
This professor is perfect. It is waste of time to attend the same classes in other school.
@HenriqueLuisSchmidt
@HenriqueLuisSchmidt 9 років тому
great lecture!
@debangan
@debangan 3 роки тому
The dude with leg up just reinvented a whole damn idea in a class. No wonder he is in MIT and I am not.
@QueenGraceFace
@QueenGraceFace 10 років тому
This is really helpful! Great lecture :)
@XTrumpet63X
@XTrumpet63X 7 років тому
I feel proud that I've been watching MIT lectures enough to have gotten the "celebration of learning" reference. xD
@axelkennedal5656
@axelkennedal5656 5 років тому
What does it mean?
@jamesbalajan3850
@jamesbalajan3850 3 роки тому
@@axelkennedal5656 Euphemism for an exam?
@majusumanto9016
@majusumanto9016 5 років тому
I find something here about alpha & betha, what if we're changing the position between 3 and 9 on the left tree...then the first cut off wouldn't happen... so the interesting thing is the alpha betha depended on the evaluation method... For example if you're doing evaluation from the right position so the cut-off will be different :D ... anyway thank you for the explanation... it's really clear
@Conor.Mcnuggets
@Conor.Mcnuggets 7 років тому
@ 29:34, for the deep cut, did he compare two Max nodes? or compared the bottom Min node with the root Max node?
@ShivangiSingh-wc3gk
@ShivangiSingh-wc3gk 6 років тому
I got thrown off a little on the alpha beta part. So at each level we when we make comparisons do we look at the values from both the min and max perspective?
@vasugupta1
@vasugupta1 6 років тому
very nicely explained the concepts my ai lecturer couldnt teach
@nXqd
@nXqd 9 років тому
thanks mr winston. This is so good :)
@myrsinivak6993
@myrsinivak6993 6 років тому
When exactly does A-B prune the most nodes?
@WepixGames
@WepixGames 4 роки тому
R.I.P Patrick Winston
@EchoVids2u
@EchoVids2u 5 років тому
30:29 Shouldn't the root then be = 8 ?
@JITCompilation
@JITCompilation 2 роки тому
Lectures like this make me wish I didn't screw around so much in high school :C should've gone to MIT instead of my crappy uni
@xinxingyang4477
@xinxingyang4477 4 роки тому
A problem I can not understand about the minimax algorithm is about the other player. Do we consider the other player can make the same calculation of the tree to a similar depth? What if they can not and made some decisions to different branches... Will that be a problem? Or not a problem?
@khairolhazeeq5426
@khairolhazeeq5426 4 роки тому
I have a few questions. The first one is, is Minimax considered as a state space search? If it is is there a Goal state/node?
@alpotato6531
@alpotato6531 4 місяці тому
rip. great explanations!
@haoyangy7026
@haoyangy7026 6 років тому
Jeez this prof is so cool in the way he talks about things wish I have a teacher like that so I don't have to watch this in a class with a super bad teacher lol
@MrChanyw
@MrChanyw 9 років тому
Great explanation minimax saved my ass! thankssss
@wolftribe66
@wolftribe66 4 роки тому
24:59 man had a tree prepared like a G
@nicoscarpa
@nicoscarpa 5 років тому
In the alpha-beta example, the branch that doesn't actually get created is just the right-most one that leads to the terminal node (not computed, because of the "cut"). Is that right? If it's right, than the statement "it's as if that branch doesn't exist" (24:00) must be interpreted such that the algorithm will never choose the action that leads to the right-hand node (the one
@spectator5144
@spectator5144 Рік тому
yes
@cagmz
@cagmz 7 років тому
Can anyone explain how the deep cut off works at 28:13? Is the maximizer making a comparison from the root to the minimizer value just above the leaf?
@amitrokade1140
@amitrokade1140 7 років тому
Whenever u get a fixed value of a node (here 27 at the top) , you compare that fixed value to the next deepest first node(here 1) and then again the usual way of checking nodes... I was also confused for a while there..
@rj-nj3uk
@rj-nj3uk 5 років тому
When the intro didn't said "This content is provided under MIT open course ware...." I thought my earphone broke.
@BertVerhelst
@BertVerhelst 9 років тому
I wonder how much you save by using the tree of the last move as a basis for the next one, since the min player can be a human, and he might not take the branch you predicted. So the alpha beta algorithm assumes the min player will always take the option that is most in the min player's own interest, which is not always the case in computationally "flawed" humans.
@richardwalker3760
@richardwalker3760 9 років тому
If the computer is the superior player, then it doesn't matter when the human makes a poor move. The computer, when doing the initial search, decided that the branch in question was "too good to be true." Thus when the human makes that move, the computer can re-discover the path that was originally "too good to be true" with less effort than it took to find it the first time (because we are one level deeper in the tree). Bottom line: Computers (when properly programmed) spend the bulk of their time analyzing the game under the assumption that the opponent is just as good as the computer. Whenever the opponent makes a poor move, the computer can recognize and capitalize on that gain relatively quickly, making the time wasted earlier irrelevant.
@MichielvanderBlonk
@MichielvanderBlonk 2 роки тому
@@richardwalker3760 Probably caching values or entire trees can be of value? Otherwise you are recalculating things you've seen before.
@tcveatch
@tcveatch 4 місяці тому
On full depth search (13:44 ish) he says 10*(80+10+9+7) = 10^106 but it’s actually 10^116. Sure his point holds but he’s just off by a factor of 10^10=10 billion.
@Apollys
@Apollys 7 років тому
"Marshall" Arts >_< I was hoping it was a pun, but it looks like it's not...
@GettoFeng
@GettoFeng 8 років тому
anybody got what the student said at 42:00 ?
@mccleod6235
@mccleod6235 Рік тому
Great lecture, but I hope that AI has advanced far enough now to automatically filter the coughing noises out of the audio. It sounds like a TB clinic in there.
@rahulaollove
@rahulaollove 6 років тому
what software is he using for it ?
@rnmisrahi
@rnmisrahi Рік тому
Small error: to convert seconds to nanoseconds you need to add 6 to the exponential factor, not 3. Still, this would not impact the point made by this brilliant professor
@rubiskelter
@rubiskelter 7 років тому
21:36 It's not "branching down", he says "branch and bound" from previous class.
@Ceilvia
@Ceilvia 5 років тому
This Prof draws beautiful trees
@thomascook8570
@thomascook8570 8 років тому
I paused the video just after he explained the 2^2 British museum method, and I thought "hang on, shouldn't the player who's making the move be trying to figure out what the implications of planning 5 moves ahead are given that each second successive state has to make assumptions about what the opponent would do in the intermediate state? So I started thinking about how you might predict an opponents move and even got onto thinking if you could use a neural network to predict it based off the opponents previous moves!" Then he explained minimax and I felt stupid... Although it does raise a second question, "If you matched two of these algorithms against each other, is the result deterministic?" Any ideas?
@Apollys
@Apollys 7 років тому
Yes, of course. Then you simply have a single deterministic program.
@marmathic9874
@marmathic9874 6 років тому
Not necessarily. The algorithms can use random numbers if there are moves with the same value.
@MichielvanderBlonk
@MichielvanderBlonk 2 роки тому
@@marmathic9874 But they don't. And combining two deterministic algorithms always results in a new deterministic algorithm, and thus a deterministic result.
7. Constraints: Interpreting Line Drawings
49:13
MIT OpenCourseWare
Переглядів 132 тис.
5. Search: Optimal, Branch and Bound, A*
48:37
MIT OpenCourseWare
Переглядів 249 тис.
🔥 Україна виходить у ФІНАЛ ЄВРОБАЧЕННЯ-2024! Реакція alyona alyona та Jerry Heil #eurovision2024
00:10
Євробачення Україна | Eurovision Ukraine official
Переглядів 251 тис.
Minimax: How Computers Play Games
14:37
Spanning Tree
Переглядів 187 тис.
Algorithms Explained - minimax and alpha-beta pruning
11:01
Sebastian Lague
Переглядів 1 млн
Coding Adventure: Chess
29:22
Sebastian Lague
Переглядів 3,7 млн
Lecture 2: From Soviet Communism to Russian Gangster Capitalism
1:10:43
YaleCourses
Переглядів 788 тис.
Lecture 2: Airplane Aerodynamics
1:12:07
MIT OpenCourseWare
Переглядів 3 млн
Mega-R3. Games, Minimax, Alpha-Beta
50:56
MIT OpenCourseWare
Переглядів 83 тис.
26. Chernobyl - How It Happened
54:24
MIT OpenCourseWare
Переглядів 2,8 млн