# Mega-R3. Games, Minimax, Alpha-Beta

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=hM2EAvMkhtk
**Transcript page:** https://www.withtranscript.ai/video/hM2EAvMkhtk

## Chapters

- 0:00 — Chapter 1 (0:00)
- 9:04 — Chapter 2 (9:04)
- 10:46 — Chapter 3 (10:46)
- 18:54 — Chapter 4 (18:54)
- 23:41 — Chapter 5 (23:41)
- 25:52 — Chapter 6 (25:52)
- 33:26 — Chapter 7 (33:26)
- 39:29 — Chapter 8 (39:29)
- 47:59 — Chapter 9 (47:59)

## Transcript

**[0:00]:** the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit mitop courseware at ocw.mit.edu today we're going to be talking about games and I know you guys as well as I hope I do the main thing that you guys want to talk about with games is how to do that Alpha Beta thing because it's pretty confusing and it's easy to get lost in a corner or something whereas doing the regular Minx in my experience most 6 or 34 students can do that and they do it right pretty much all the time however we're going to focus on all the different components of games and I put up two provocative Silver Star ideas up on the board which um will come into play here the snow white principal is a

**[1:02]:** new name and has never been revealed until today because I made up the name recently so you will be the first people to hear it and decide if it works better than the the term grandfather clause for the thing that I'm trying to describe because most grandfathers don't eat their children so um here we've got a beautiful game tree it has notes from a through R this is this is our standard game tree from 6034 we've got a maximizer up at the top who's trying to get the highest score possible the minimizer is her opponent and the minimizer is trying to get it to the lowest score possible and it's really unclear who wins or loses at each point they're just trying to get it to the highest or the lowest score all right so let's do a refresher hopefully like the quiz didn't put people into such Panic modes that they forgot Monday's lecture

**[2:01]:** so let's make sure that we can do regular Minx algorithm on this tree and figure out the Mini max value at a so let's see how that works all right so if as you guys remember the game search when you're using regular minia Max is essentially a depth first search and at each level it it chooses between all of the children which whichever value that the parent wants so here at F it would choose the maximum of K and L for instance but that's getting ahead of ourselves because it's a depth first search so we best start at the top I'll help you guys out for a while so we're doing a we need the maximum BCD depth first search we go to B we're looking for the minimum into of E and F so having looked at e our current minimum of E and F is just two for the moment so this is

**[2:59]:** going to be less than or equal to two all right then we go down to F which is a maximizer and it's children are K and L so now I'm going to start making you guys do stuff so what do you think what is the going to be the value Mini max value at F the mini value mini value at F what will that be would be the minimum of K and so that level is um a maximizer Maxim Max f is a Max K and L themselves are minimizers but they're pretty impotent minimizers because they don't get to choose they just have to do k l so the value is the Minimax value is three and yeah the path it would like to go is K so we'll say the Minimax value here is three it's in fact exactly equal to three all right so if this is three and this is two then

**[3:52]:** everyone we know that the value of B is I hear three and two which one is it two that's right so the value here is two great let's go down into this Branch so C is going to be the minimum of G and six but we don't see that yet cuz we're doing a depth research it's going to be the minimum of G now we need the maximum of M and N we're going to need the minimum m is the minimum of Q and R so let's switch sides the minimum of Q and R is one let's see that's right it's one so M has a value of one but I'm going to stay over here because M has a value of one knowing that then we know that g has a value of seven that's right seven is higher than one and since G is a seven we now know going up to C

**[4:45]:** that c has a value of six yes C has a value of six that's the minimum of six and seven so now I'm going to go back down because we've done one of the other sub trees this is a six all right great now we're going to go down to D hopefully it won't be too bad these things usually aren't terrible because they're made to be pruned a lot in Alpha Beta so let's see in D we go down to I and that's just a one we go down to J and let's see what's the Minimax value of J that's right 20 is the maximum of 202 great so what's the minax value of D everyone said it one all right so what's the minax value at a six is Right six is higher than two it's higher than one our value is six and our path is everyone a c h that's it great

**[5:43]:** is everyone good with Mini Max I know that usually a lot of people are there's usually a few people who aren't so if you're one of the people who would like some clarifications on Minx raise your hands there's probably a few other people who would like some to okay uh when you're doing this Max you're whenever vales are not sh you keep uh going down the tree and then just look at what they're trying to find the min max and just whatever values you get you go back up back TR yes our our our general uh the question was when you go um to do the minia Max and let's say you got e was two and you know that b is going to be less than or equal to two but you don't know F yet the question is do you go down the tree find the value at F and then go back

**[6:28]:** up the answer is yes by default we use a depth first search however in non-alpha beta version just regular Minimax turns out it probably doesn't matter what you do I suggest doing a depth first search to get yourself in the mindset of Alpha Beta because order is very very important in Alpha Beta so um but here like I don't know you could do some weird bottom up search or whatever whatever you want it's going to give you the right answer unless it asks what order they evaluated but here's a hint the order they evaluated in um in uh is depth for search ORD so without even doing anything EK l q r n h i o p are the order of static evaluation in um in this tree so we don't have to which minimum Max so the question is we nodes like M and G we don't have to put values next to technically

**[7:26]:** if we were doing this very formally and we couldn't remember and I wasn't up there among the people we could we would put one there so at M we would put a one but people remembered that so we didn't do it but then a g we would put a seven so if we were writing it out very formally we would have a one and a seven and at this D we would have a one and then at the a we would put a six and then that's that's the answer also we'd even put things like less than or greater than part way along the way however I believe that our Alpha Beta search is going to definitely fulfill everyone's quota of pedantically putting lots of numbers next to nodes on on a game tree and so um once you've done Alpha Beta if you can do it correctly you'll think ah Mini Max oh those

**[8:15]:** were the days it's going to be easy because Alpha Beta is a little bit more complicated there's a lot of things that trick people up here for Alpha Beta however I will erase some of these numbers for the moment they're still right but we do it a little differently so what do alpha beta and beta add to this formula well this is a sort of a winning formula except for it's not because it takes too long but it's a very nice formula you as the maximizer say I try to think if I do this what's he going to do and then if he does that what's I'm going to do and then what I what is he going to do if I do that etc etc all the way to the bottom with Alpha and beta we add in what I like to call nuclear options I i' like in this game of maximizer minimizer

**[9:04]:** you can think of it as like the cold war or the pelian war except the palanan war didn't have nukes so probably the Cold War um and you know in the Cold War um or any situation where you're up against an adversary who actually the this doesn't really work as well for the Cold War but in any situation where up you're against an adversary who's only goal in life is to destroy you you always want to find out what the best thing you can possibly do is you know if they hit that button and send nukes in from Cuba or if they send fighter pilots or whatever is going on so the idea of Alpha and beta is that they are numbers that represent the fail safe the worst case because obviously in you know in the Cold War sending nukes was not a good plan but uh um presumably us sending nukes would be

**[9:55]:** better than just being attacked and killed so the alpha and beta represent the wor um the worst possible outcome you would be willing to accept for your side because right now you know you're guaranteed to be able to you're guaranteed to be able to force the conflict to that point or better so the alpha is the nuclear option the fail safe of the maximizer all right nuclear options Alpha is maximizer nuclear option

**[10:35]:** and um beta is the minimizer nuclear

**[10:46]:** option so we ask ourselves and people who were paying attention to it lecture or wrote stuff down know the answer already what could we possibly set to start off before we explore the tree and find anything what will we set as our nuclear option as our sort of fail safe we can always fall back on this number so I mean you could set zero you could try to set you know some low number for the maximizer CU if you set a high number for the maximizer as it's fail safe it's going to be really snoody and just say oh I won't take this path I already have a fail safe that's better than all these paths if you set like 100 you have no treat our default usually in 6034 is to set negative Infinity for Alpha or negative some very large number if you're doing it in your lab uh so if we set

**[11:33]:** negative Infinity as the default for Alpha that negative Infinity is basically maximizer loses so the maximizer goes in thinking oh my God if I don't look at this game tree I automatically lose he's willing to take the first path possibly presented and um that's why that negative Infinity is a good default for Alpha anyone have a good idea what a good default for beta is or just remember positive Infinity that's right because the minimizer comes in and she's like oh crap the maximizer automatically wins if I don't look at this uh I don't look at this node here that makes sure the maximizer and the minimizer both are willing to look at the first path they see every time because like look on this tree if 10 was Alpha the maximizer would just reject out of hand everything except for p and then we wouldn't have a tree the maximizer would lose because he would

**[12:22]:** be like this chest game is very interesting however I have another option and to throw over the table that's 10 for me because you have to pick up the pieces I don't own this set I don't know so that is why we set negative infinity and positive Infinity as the default for Alpha and beta so how do alpha and beta propagate and what do they do the main purpose of Alpha and beta is that as we said Alpha let's say we have some chart of values Alpha which starts at negative Infinity is the worst that the maximizer is ready willing to accept because they know they can get that much or better it starts out that's the worst thing you can have so it's not a problem Infinity is the highest that the minimizer is willing to accept that's beta as you go along that the minimizer sees oh look at that I can guarantee

**[13:15]:** that at best the maximizer gets you know 100 haha beta is now 100 maximizer sees oh yeah well I can guarantee you can get at the lowest you can get me to go to is zero so it's going to be zero and this keeps going on until maybe at 6 Noe not drawn to scale uh maybe at six the maximizer says haha you can't make me go lower than six and the minimizer says aha you can't make me go higher than six and then six is the answer if you ever get to a point where if you ever get to a point where beta gets lower than alpha or Alpha gets lower than beta then you just say screw this I'm not even going to look at the I'm not even going to look at the remaining stuff I'm going to just prune now and go somewhere else that's less pointless than this because if

**[14:12]:** the alpha gets higher than the beta what that's saying is the maximizer says oh man look at this minimizer the lowest you can make me go is one is say 50 and the minimizer says that's strange because the highest that you can make me go is 40 so something's generally um something's generally a Miss there it usually means that one of the two of them doesn't even want to be exploring that Branch at all so you you prune at that point all right so given that that's what we're looking for how do we move the alphas and betas throughout the tree there's a few different ways to draw them and some of them I consider to be very busy um probably in recitation and tutorial you will see a way that's busier and has more numbers technically every node has both an alpha and a beta however the one that that node is paying attention

**[15:03]:** to is the alpha if it's a maximizer and the beta if it's a minimizer so I generally for my purposes only draw the alpha out for the maximizer and only draw the beta out for the minimizer very rarely but it happens they'll sometimes ask you well what's the beta of this node which is a maximizer node so it's good to know how it's derived but I think that it wastes your time to write it out that's my opinion we'll see how goes so the way that it works is the the way that Alpha and beta works is the Snow White principle so does everyone know the story of Snow White so you know there's a beautiful princess there's an evil queen stepmother miramir on the wall who's the first of them all finds out that uh that it's the the stepdaughter so much like in the real world in Snow White the stepdaughter the Snow

**[15:50]:** White had the beauty of her parents she inherited those however much like in the real world maybe or perhaps not um the stepmother had an even better plan she hired a hunter to uh to sort of hunt Snow White pull out Snow White's heart and feed it to her so that she could gain Snow White's Beauty for herself how many people knew that version of the story a few people that's the original version of the story Disney didn't put that in the hunter then brought the heart of a deer which I think in Disney the hunter did kill a deer arbitrarily but it was not explained that that's why he was doing it so in Alpha Beta it's just like that by which I mean you start by inheriting the alpha and beta of your parents but if you see something that you like amongst your children you take it for yourself the Snow White

**[16:41]:** principle so let's see how that goes well I told you guys that the default Alpha was negative Infinity so here Alpha is negative infinity and I told you that the default beta was positive Infinity we're doing a depth first search here all right beta is infinity all right so we come here to e now we could put an alpha but I never put some I never put an alpha or a beta for one of the terminal nodes because it can't really do anything it just you know it's just two so as we go down we take the alpha and beta from our parents but as we go up to a parent if the parent likes what it sees in the child it takes it instead so I ask you all the question would the minimizer prefer this two that it sees from its child or its own Infinity for a beta it likes the two

**[17:38]:** that's absolutely right so two all right great so now we go down to F what is F's Alpha who says who says negative Infinity who says two no one oh you guys are you guys are you guys are good it's negative Infinity technically it also will have a beta of two but we're ignoring the beta and the alphas that have been progressing downward from parents negative Infinity that's why I called it the grandfather clause before because you would often look up to your grandparent to um to see what your default number is so we got an alpha of negative Infinity we then go down to the K it's a static evaluation and now I'm going to start calling on people individually so hopefully people paid attention to the Mob who were always correct um all right so we go down to K and we see a three f is a maximizer node so what does f do now outut yes switches its Alpha to three

**[18:54]:** great all right so that's already that's already quite good it switches Alpha to three it's very happy it's got a three here that's a nice that's a nice value so what does it do let's see what does it do at L at L the next one it's gone to K went back up to F dep for search the next one would be L right inh from anywhere right well technically F could take L um could take L's value of zero if it liked it better than three but it's a maximizer so what doesn't want to take that okay that technically would be correct but I'm sorry I burden you with a trick question um in fact we don't look at L at

**[19:50]:** all does everyone see that I'll explain the alpha at F has reached three but the beta at B is two so B looks down and says wait a minute if I go down to F my enemy's nuclear option my enem is the worst it can be for you know the best it can be for me is three f f is trumpeting around I was thinking of you know eating his hard or whatever but I didn't want to but it's going to be three it's going to be three or higher down um down there at F there's no way I want that I already have my own I already have my own default Escape and that's two that's going to be better than whatever comes out of that horrible F so screw it and we never look it out does everyone get that that is the main principle of Alpha Beta pruning you if you see

**[20:44]:** an alpha it's higher than the beta above it as I said you know if Alpha goes up above the beta or if you see a beta and there's a like if there's a beta down here and it's lower than the alpha above it prune stop doing that the and the question is who prunes who decides that you don't look at L the the person who is thinking not to look at L is always up higher by at least two levels so up here B is saying H I don't want to look at L because f is already so terrible for me that it's just beyond belief it's going to be if if this is 100 it might be 100 if this is if it's even if it's lower I'm still going to get a three there's a sanity check that I've written uh or that I that I sort of came up with just in

**[21:34]:** case you're not sure that you can skip it because on a lot of these tests we ask you which ones do you evaluate which ones do you skip right so or we just say which ones do you evaluate and you don't write the ones that you skip here's my sanity test to see if you can skip it ask yourself if that node contain that I'm about to skip contained a negative infinity or some arbitrarily small number negative Infinity being the minimizer wins would it change anything now that I've answered that if it CH contained a positive Infinity would it change anything if the answer is no both times then you definitely correct in pruning it so look at that zero if it was a negative Infinity minimizer wins what would happen maximizer would say I'm not touching that with a 10-ft pole choosing three the minimizer would say oh screw that I'll take e let's

**[22:26]:** say it was a positive Infinity the maxim would say Eureka Holy Grail I win minimizer would say yeah if I'm a and go down to F and then we go to E and take two so no matter what was there minimizer would go to E and you could say well what if it was exactly two but he still the maximizer would choose K and the minimizer would go to E so there's no reason to go down there we can just prune it off right now does everyone agree everyone see what I'm talking about here great so we're now done because with this Branch because beta is two so now we're up at Old Grand papy a and he has an alpha of negative Infinity everyone what what will he do two he'll take the two it's better than negative Infinity for him it's not wonderful but surely anything is better than an automatic loss all

**[23:19]:** right now our highest know is a two so let's keep that in mind for our Alpha okay so let's let's go over here let's see so what will be the value at C what will be the beta

**[23:41]:** value go back to which one to G uh I'm not at G yet I'm actually um just starting the middle Branch so I'm going to C and what's going to be it starting Data before I U before I go down Infinity that's right default value is easier than it seemed all right so yes beta is equal to Infinity this should be better erased I think it's confusing people great okay so beta is equal to Infinity at C what is going to now we go down depth first sech to G what's going to be our Alpha at Gus ah it would seem so however take a look up at our at the you know great grand papy a it seems to have changed to two so this time it's two why is it two instead of negative Infinity why can we let a be so obnoxious and not start with saying oh I automatically lose well

**[24:36]:** a knows that no matter how awful things get in that middle Branch he could just say screw the whole middle Branch I'm going to be that's something that that the minimizer can't do and we have to start at Infinity for the minimizer but the maximizer can because he has the choice at the top does everyone see that he can just say oh I'm not even going to C yes shows you I'm going to a taking the two so therefore Alpha is actually two at G all right great so we've got an alpha that's two at G we're going to go down to M it's a minimizer all right what's going to be our beta value at

**[25:18]:** M or which is the beta default minus or positive Infinity where the minimizer positive Infinity that's right m is going to be a positive Infinity for beta again it picks it up from C great now we get to some actual values okay so we're at some actual values we are at Q so what's going to what's going to happen at M when M sees that Q is one

**[25:52]:** um wait what do beta say what is beta it says Infinity I'm sorry it's hard to read beta is Infinity ADM

**[26:03]:** so um that's right so beta is going to be they're going to put beta to one because it sees Q great all right so my next question is let's see uh my next question is what's going to happen at

**[26:26]:** R there you have youve you've detected my trap the question is does it look at R the answer is no it doesn't look at R why doesn't look at R does everyone see yeah Alpha is now greater than the beta below it beta has gotten lower than Alpha this is the same thing I was talking about before when we figured out that the alpha here was two the maximizer says wait a minute if I if ma where G says if I go to m the best I'm getting out of this at one cuz if this is negative Infinity he'll minimizer will choose if this is positive Infinity he'll choose one best I'm going to get out of here is one if that's the case I might as well just gone to B and not even gone to C so I'm not going to go to m I'll go to n maybe maybe n's better does

**[27:13]:** everyone see that great so let's say that the maximizer does go to end so what's going to happen with his Alpha it's to be seven that's right going to be seven seven is better than two and maximizer has control to get to that seven at least if it gets to G all right now the minimizer at C we'll do everyone this time the minimizer at C seeing that seven what does the minimizer do anyone so it sees the seven what does it do to its beta it takes the seven better than infinity anyway and yeah then it checks H and everyone again what happens at H takes the six it's lower than seven all right now we'll go back to having people do it on their own well all the way back to the top what does a do when it sees the Six coming out of C changes to six changes

**[28:15]:** to six that's right Alpha equals six great home stretch people home stretch so the minimizer everyone has has a beta of infinity and if I wasn't a static node it would have an alpha of six but it is a static node so it just has a value of one so since it has a value of one everyone the beta becomes one and what next everyone prune that's right why prune well this time it's a himself who can prune a says well darn if I go to D I'm going to get one or something even worse than one might as well take my six while I have it prune all the rest all the way

**[29:08]:** down everyone see that everyone cool with that it's not too bad if you take it one step at a time we did it our answer uh our question is which noes are evaluated in order our answer is everyone e k q uh n h i okay not so obvious I guess few people followed me but it is a e k q NH it's just step first order and we pruned some of them away great so that is Alpha Beta any questions about that before I give some questions about Progressive deepening all right we've got a bunch so first question you in order which evated are we excluding notes like uh FB C and D the question is when asked for the order of evaluation are we includ excluding FB C and D the answer is we're talking about here static evaluation the static evaluator is a very important and interesting function and I'll get back

**[30:16]:** to something a few students have asked me about the static evaluator later and try to explain what it is it's basically the thing that pops out those numbers at the bottom of the leaves so when we ask what is the order of nodes that were statically evaluated we mean leaves only that's a good question any other questions let's see there was one up here before but it's gone might been the same one question so a similar question when you say static notes that just means the leaf notes means the leaf notes that's right the question is does static nodes being the leaf nodes the answer is yes static evaluation is when you compare the value of static to something static evaluation is when you get that number the static node let me explain um unless someone else has a another question about Alpha Beta let me explain static values because I was about to do

**[31:01]:** that there is a question about Alpha Beta I'll come back to both of yours after I answer this you know you were mentioning a snow principle earlier and I'm a little bit confused when you say if we looking at one uh node sure and you're saying like either grab the value from the grandparent or grab it from the children so it always starts uh the question is what is the Snow White principle how does it work every node always starts off with taking the value of the same type alpha or beta from its grandparent it always starts that way now you say why the grandparent wouldn't take it from the parent it actually does but I'm not drawing out the alphas at all the minimizer levels because they don't do anything they just they're only even there to pass them down so all the values pass down down down down down to begin every value

**[31:50]:** in every node in fact starts starts off with its with its grandparents with its parents values okay but then when the node sees a child that's completely done evaluating it's finished like let's say you can't it can't be in the process when when let's say C when C is complete it sees that g is completely done with all of its sub branches and is ready to return a value as if it was or if it's just a static evaluation then it's automatically completely done right because it has no children right a static value like K of three is automatically completely done it's got a three similarly when we came back to G after going to n and we knew that the value was seven that was completely done the value was definitely seven there was no other possibilities right that's after looking at the children yes so once you're done with all the children of

**[32:43]:** G then g g comes up and says guess what guess what guys all right so technically before that you would have said that like G's Alpha is greater than or equal to one and then when we said when we looked at Q and then we looked at M we say it's equal exactly to seven we're done here and then at that point you know when it's fresh and ripe and has all of its highest value or its best value that's when the parent can you know eat its heart and gain that value itself so that's when C says for instance C says oh man I have an I have an Infinity that's that I really like that seven better and it take the seven but then it saw H and it said oh man that's a six that's even better than seven so it took the six Al seven so Alpha takes six because C

**[33:26]:** is a minimizer C took the seven from G but then right after that c saw H and took the six cuz six is even lower uh than seven and then Alpha took the six because six was higher than two so it's not going to look like below the yeah the problem is that the maximizer doesn't have control there the minimizer's got control at C and the minimizer is going to make sure it's as low as possible the maximizer at a his only control is or her only control is the ability to send our A to B or C or D or at least and then at that point at C the minimizer gets to choose if we go to G or H and it's never going to choose G because G is higher than H all right awesome uh is there another question all right let's go back to static evaluations when I first took

**[34:13]:** this class I had some weird thoughts about static evaluations I heard some students ask me this I almost got a question about it onto one of the tests but it was edited to some other weird question that was m to the B to the D minus one or something like that the last minute so I'm going to pose you guys the actual question that would have been on one of the older tests which is the following I had a student who came to be and said you know Mark when we do this alpab Beta pruning and all this other stuff we're trying to assume that we're really saving that much time by you know getting rid of a few static evaluations we in fact when we do Progressive deepening we're always just counting how many static evaluations do we have to do and he said I look at these static evaluations and there's just a

**[34:52]:** three there it takes no time to do the static evaluation it's on the it's on the board it takes much longer to do the alpha beta it's faster by far to not do alpha beta so I had then tried to explain to that student I said okay we need to be clear about what static evaluations are you guys get it easy we put these numbers on the board a static evaluation let's say you're playing a game like chess the static evaluation takes a long time when I was in 6170 Java death lab used the class that used to exist we had a program called anti chest where I use my 6034 skills to write the AI and the static evaluator took a long time and we were timed so getting the static evaluator faster that was the most important thing why does it take a long time well the static evaluator is an evaluation of

**[35:40]:** the board position the state of the game at a snapshot of time and that's not as easy as just saying oh here's the answer because in chess first of all not only did I have to look at how many pieces I had what areas that you know that I controlled also what was anti- chest but that's notwithstanding let's pretend it's regular chess I also had to look if it was in regular chess and I still had to do this in anti chest if my king was in check and what that meant is I had to look at all of my opponent's moves possible moves to see if any of them could take my king because for you know in regular chest it's illegal to put your king into check so you better not even allow that move and regardless getting into Checkmate is negative Infinity for you so it takes a really long time to

**[36:25]:** do static evaluations at least good ones usually you want to avoid them because they're not just some number on the page they are some function you wrote that does a very careful analysis of the state of the game and says I'm going to heris guess that my value is pi and then or some other number and then rates that compared to other states does that make sense to everyone so the answer to the qu the hypothetical question that might have been on the old test what to when the person said I've got this great idea where we do tons of static evaluations you don't have to do this long Alpha Beta is don't do that the static evaluations actually take a long time does that clear it up for people who asked me before about static what is a static evaluation um why are the leaf nodes called Static basically and you might ask why

**[37:15]:** are some of these static just arbitrarily the answer is when you're running out of time to expand deeper and you just need to stop that stage of the game maybe it's just getting too hairy maybe it's spreading out too much you have some heuristic that says this is where I stop for now it's a heuristic guess of the value it's kind of like those fistic values in the search tree that's a guess of how much work you have left to get to the goal here you say well I wish I could go deeper but I just don't have the time so here's what I think how I think I'm doing at this level it's not always right and that's going to lead us into the answer to one of the questions about Progressive deepening so I'll put up the progressive deepening question really quickly so the question is this suppose that let me see this

**[38:00]:** is a maximizer yes suppose that um we do Progressive deepening on the the tree that is only two levels deep what is Progressive deepening in a nutshell if you don't remember from the lecture the idea is this it it doesn't take in this tree it it doesn't work but in trees that actually Branch like two to the end it doesn't take that much time to do like some of the top levels first and then move on to the bottom levels just do them one at a time so let's say we only did it up through J we only did the top two levels of the tree we'd like to reorder the tree so that Alpha Beta can prune as much as it possibly can at least we hope all right so let's pretend that we had a psychic awesome um genius friend who told us that the static values when we went up to two

**[38:50]:** levels remember when we go to two levels FG and J have to get a static value right because we're not going down we do a static evaluation they get the exact correct numbers 3 7 and 20 genius brilliant all right so if that happens how is the be what is the best way that we could reorder that tree oh yeah uh yeah yeah so it's ABC D with values of 2 3 7 6 1 20 I'll draw that this is the non- reordered tree

**[39:29]:** let's see so it's 2 3 7 6 1 20 so what's the best way to reorder well first of all does anyone remember what Patrick said when he talked about Progressive deepening usually no one does so don't worry about it the best way to uh because at that time you guys didn't think oh I have to do this for the quiz you were just thinking oh man we've already heard alphab beta and all this other stuff and this is just a small fact but it's a very important fact and now you know you have to do it for the quiz so you're probably going to remember it the way you do it is you try to guess and you say which one of these is going to be a winner whichever one I think is going to be a winner at that level I put first why is that the case well something interesting you may have noticed here whenever you have

**[40:27]:** a winner like the middle node or whenever you have whatever is the current best for your Alpha you sort of have to explore out a lot of that area like for instance the left node was our current best at two the middle Branch was our current best at that time was six it was the total best we had to explore a good number of nodes but on the right we just saw oh there's one we're done we cut everything off in other words the branch that turns out to be the one that you take you have to do pretty good amount of exploration to prove that it's the right one whereas if it's the wrong one you can sometimes with just one note say this is wrong done so therefore if the one that turns out to be the eventual winner is first of all then it's really easy to reject all the other branches

**[41:13]:** do people see that sort of conceptually a little bit that if you get the best node right away you can just reject all the wrong ones pretty quickly that's our goal so how can we quote get the right one the best one right away well here's how we do it let's say we're at B which one is the minimizer likely to pick assuming that our heris is good and that um these guesses are pretty much close to the truth and turns out they're perfect so this is going to work so which one will the minimizer pick if it has to choose between E and F do we think e perfect which one will pick between G and H H which one will pick between I and J okay so what we're saying is we think it's going to pick e we think it's going to to pick H we think it's going to pick I

**[41:59]:** so first of all we should put E before f h before G and I before J because we think it's going to pick those first those are POS our best ones to invalidate a poor Branch so now between 2 six and one which is what we think we're going to get which one do we think the maximizer is going to take six then if it couldn't take six what would be its next best choice two then one that's just our order simple as that couldn't be anything easier that involves really complex trees a huge number of numbers and reordering those trees so C you guys Told Me CB oh sorry D you told me CB D I think yeah those the ones the maximizer likes and then the ones the minimizer likes you told me was H and before G because H is smaller than G you guys told me E before F and and

**[42:57]:** you guys told me I before J and you guys would be correct in all regards we have 67 2 3 120 all the minimizers choose from smallest to highest the maximizer chooses from highest to lowest of the one that minimizers will take and if we did that you can see we would probably save some time let's see how much time let's say we looked at H first right what we looked at if we looked at H first we would still have actually had to look at Q and N however we would not have had to look at K do people see why if we already knew this brench was six as soon as we saw two for the beta here two is less than six we could have pruned we still would have had to look at I over here because you have to look at at least one thing in the new sub rench and it actually would have saved

**[43:57]:** us one node oops so it winds up that in total how many nodes would we have evaluated if we did um if we did that little scheme of reordering well we normally had to do six right EK qh uh qnh hii how many do we evaluate if we do this um this Progressive deepening scheme how many times we run the static evaluator which of course you know the static evaluator takes a long time anyone have a guess I told you the only one we don't evaluate is K you raise your hand I won't I won't make anyone do uh give this one so I yeah I said the only one we save on is K so we still do EQ H and H and I over here there's two possible answers that I will accept so you have a higher chance of guessing it anyone does everyone agree that we did six before if we

**[44:59]:** didn't do any Progressive deepening we just you know did e k q NH hi I and now we're not doing K okay people are saying five all right good that's not the right answer but at least shows that you can do taking away the one we did at least five over here there's two possible answers though because look over there in order to do the progressive deepening we had to do those static evaluations right so we either did we either did all those static evaluations and these five stat a k q n hi I these five static evaluations so we didn't do the K or or we might have saved ourselves because maybe we were smart and decided to cach the static values when we were going down the tree it's an implementation detail that on this test when we asked that question we didn't say but I mean by C is when we did

**[45:57]:** it here and saw that um e was a two and then here oh we have to do the static value at e if we were smart we might have made a little hash table or something and put down two so we didn't have to do a static evaluation at e and if that happened well we save eh and I and we do three fewer does everyone see that however that's still more than six so it didn't save us time so you might say oh Progressive TP is a waste of time but it's not because this is a very very small not very branchy tree that was made so that you guys could easily do alpha beta and take the quiz and it wouldn't be bad if this tree was actually branching to um double even double at each level it would have what like 16 nodes down here at the bottom then you would want

**[46:45]:** to be doing that Progressive deepening so now I ask you a conceptual Riddle question it's not really that much of a riddle but we'll see if anyone wants to answer again I won't call on you for this it's um according to this test um a student named Steve says okay I know I have to pay to do the progressive deepening here but let's ignore that because it's small in a large tree right it's not going to take that much Let's ignore the cost of the progressive deepening and only look at how much we do here he says when it comes to performing the alpha beta on the final level I'm guaranteed to always prune at least as well or better if I rearrange the nodes based on the best result from Progressive deepening do you

**[47:32]:** agree can I repeat it okay the question is ignoring the cost that we pay progressively deepening here just forget about it at the final step at the final iteration question is am I guaranteed to do at least as well or better in my Alpha Beta pruning when I reorder based on the best level of um based on the best order for Progressive deing here certainly we did but the question is is Steve guaranteed

**[47:59]:** answer what did you say that's the answer and the why which we asked to explain the the answer we got is that doesn't that depend on theistic perfectly correct the answer is no we're not guaranteed and it depends on theistic so if we were guaranteed that would mean our heris stick was Godlike like this heris stick if our heris stick already tells you the correct answer no matter what don't do game search just go to the the empty CH the chess board put all the pieces in the front rows and run the static evaluator on that and it'll say oh it looks like with this game not started that white is stupid so black will win in 15 turns and then you're done and you don't do a search we know that our heris is flawed in some way it could be very flawed if it's flawed so badly that it tells us a very

**[48:45]:** bad result of what's actually going to happen even though we think the minimizer is going to go to H maybe it's wrong by a lot and it goes to G it could take us a even worse path and make us take longer question if it's atic How Could You C the values so you have to recate later the question is how can you cach the values if it's a heuristic so you don't have to recalculate them later the answer is it wouldn't help if there weren't these weird multi-level things where we stop at e some for some reason even though it goes down to five levels the way you could cach it is it is a heris but it's consistent and I don't mean consistent from search I mean it's a consistent heris in in the State game State e is let's say say that's the state where I moved out my night as the

**[49:30]:** maximizer minimizer said you're doing the Night opening really and then did a Counterattack no matter how we get to e or where we go to get to e that's always going to be State e it's always going to have the same turistic value it's not like some guy who like goes around and just randomly pulls a number out of a hat for some we're going to have some value where that gives us points based on state e and it's going to be the same anytime we go to state e does that make sense it is a heuristic but it's always going to give the same value at e no matter how you got to e but it could be really bad in fact you might consider a heris that's the opposite of correct and always tells us the worst move and claims it's the best that's the heris that the minimizer are programmed into our

**[50:13]:** computer perhaps in that case when we do Progressive deepening and we reorder we'll probably get the worst pruning possible so um we may not but we may so in that case you're not guaranteed hope that given a little a few clues in tutorial you guys are going to see some more interesting problems that go into a few other details I at least plan on doing yuan's interesting game problem from last year which asked a bunch of um asked a bunch of um varied things that are a little bit different from these so it should be it should be a lot of fun hopefully or at least useful to um do the next Quiz so have a great weekend don't stress out too much about the quiz
