Mega-R3. Games; Minimax; Alpha-Beta Video Lecture - Artificial Intelligence

the following content is provided under
a Creative Commons license your support
will help MIT OpenCourseWare continue to
offer high quality educational resources
for free
to make a donation or view additional
materials from hundreds of MIT courses
visit MIT opencourseware 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 minimax in my
experience most of those before 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
will come into play here the Snow White
principle is a 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
here we've got a beautiful game tree it
has nodes from a through R this is our
standard game tree from 603 4 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
so let's make sure that we can do
regular minimax algorithm on this tree
and figure out the minimax value at a so
let's see how that works
eyes so if as you guys remember the game
search when you're using regular minimax
is essentially a depth-first search
and at each level it is it chooses
between all the children 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'd best start at the top
I'll help you guys out for a while so
we're doing a we need the maximum of BCG
depth-first search we go to beat we're
looking for the minimum end of ENS so
having looked at e our current minimum
of E and F is just 2 for the moment so
this is going to be less than or equal
to 2 all right then we go down to F
which is a Maximizer and it's children
are K and L so now I'm gonna start
making you guys do stuff so what do you
think what is there gonna be the value
of minimax value at s the minimax value
minimax value at s
so that level is a Maximizer max min max
F is a Maximizer K&L themselves are
minimizer's but there are pretty
impotent minimizer's because they don't
get to choose they just have to do care
out so the value is if the minimax value
is 3 and yeah the past it would like to
go is k so we'll say that the minimax
value here is 3 it's in fact exactly
equal to 3
all right so this is 3 and this is 2
then everyone we know that the value of
B is I here 3 & 2 which one is it -
that's right so the value here is too
great
let's go down into this branch so C is
gonna be the minimum of G and 6 but we
don't see that yet cuz we're doing a
depth-first search it's gonna be the
minimum of G now we need the maximum of
M and n we're gonna need the minimum and
is the minimum of Q and R so let's
switch sides the minimum Q and R is
let's see that's right it's 1 so M has a
value of 1 but I'm gonna stay over here
because M has a value of 1 knowing that
then we know that G has a value of
that's right
7 is higher than 1 and since G is a 7 we
now know going up to C that C has a
value of yes C has a value of 6 that's
the minimum of 6 and 7 so now I'm gonna
go back down because we've done one of
the other sub trees this is a 6 all
right great
now we're gonna 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 1 we go down to J and let's see what's
the Midianites luggage a that's right 20
is the maximum of 20 and 2 great so
what's the minimax value with D everyone
said it one all right so what's the max
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
is it everyone good with minimax 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'd like some
clarifications on minimax raise their
hands there's probably a few other
people who would like something too okay
yes our general the question was when
you go to do the minimax
and let's say you got a was 2 and you
know the B is gonna be less than or
equal to 2 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 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 but here like
I don't know you could do some weird
bottom-up search or whatever whatever
you want it's gonna give you the right
answer unless it asks what order they
evaluated but here's a hint the order
they're evaluated in in is depth-first
search order so without even doing
anything
EK l QR n h io p r the order of static
evaluation and in this tree
so the question is we nodes like m and G
we don't have to put values next to
technically if we were doing this very
formally and we couldn't remember and I
wasn't up there among the people we
could we put one there so at M we would
put a 1 but people remembered that so we
didn't do it but then a G we would put a
7 so if we were writing it out very
formally we would have a 1 and a 7 and
if this D we would have a 1 and then at
the a we would put a 6 and then that's
that's the answer
also we 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 identically putting
lots of numbers next to nodes on a game
tree and so once you've done alpha beta
if you can do it correctly you'll pick
up minimax oh those were the days it's
gonna be easy because alpha beta is a
little bit more complicated there's a
lot of things that trip people up here
for elevator however I will erase some
of these numbers for the moment they're
still right but we do it a little
differently so what the Alpha Beta 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 gonna do and then if he does that
once I'm gonna do and then what it was
he gonna do if I do that et cetera et
cetera all the way to the bottom with
alpha and beta we added what I like to
call nuclear options I'd like in this
game exercise a minimizer you can think
of it as like the Cold War or the
Peloponnesian War cept the publication
where didn't have nukes so probably the
Cold War and you know in the Cold War or
any situation where you're up against an
adversary who actually the color just
doesn't really work as well for the Cold
War but in any situation we're up here
against an adversary whose only goal in
life is to destroy you you always want
to find out what the best
you can possibly do is you know if they
hit that button and said 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 failsafe
the worst case because obviously in you
know in the Cold War
sending nukes was not a good plan but
presumably us sending nukes would be
better than just being attacked and
killed so the alpha and beta represent
the were 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 failsafe
of the Maximizer all right nuclear
options alpha is maximizers nuclear
option and beta is the minimizer's
nuclear option so we ask ourselves and
people who were paying attention at
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
failsafe we can always fall back on this
number so we I mean you could set zero
you could try set you know some low
number for the Maximizer because if you
set a high number for the Maximizer as
its failsafe it's gonna be really snooty
and just say oh I won't take this path I
already have a failsafe that's better
than all these pads if you set like 100
you have no treat our default usually in
6.34 is to set negative infinity for
alpha or negative some very large number
if you're doing it in your lab so if we
set negative infinity as the default for
alpha that negative 50 is basically
Maximizer losses
so the Maximizer goes in thinking oh my
god if I don't look at this gay tree I
automatically lose he's willing to take
the first path possibly presented and
that's why that Nigam 50 is a good
default for alpha anyone have a good
idea what a good default for beta is or
just remember awesome 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 don't look at this note here that
makes sure the Maximizer 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 a Maximizer would
lose because he would be like hmm this
chess game is very interesting however I
have another option foo and then 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 defaults for alpha and
beta so how do I often beta propagated
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 though that the
minimizer sees oh look at that
I can guarantee that at best Maximizer
get 0-100 haha beta is now 100 Maximizer
sees oh yeah well I can guarantee you
can get the lowest you can get me to go
to zero so it's going to be zero and
this keeps going on until maybe at six
note not drawn to scale maybe at six the
Maximizer said haha you can't make me go
lower than six Matt and the middle I
said aha you can't make me go higher
than 6 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 gonna look at the I'm
not even gonna look at the remaining
stuff I'm gonna just prune now and go
somewhere else that's less pointless
than this because if 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 is generally something's
generally amiss 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
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 knows paying attention 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 oh
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 it goes
so the way that it works is this the way
the alpha beta worse 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 mirror mirror on the wall
who's the fairest of them all finds out
that that it's the the stepdaughter so
much like in the real world in Snow
White the stepdaughter there's Snow
White had the beauty of her parents she
inherited those however much like in the
real world maybe or perhaps not the
stepmother had an even better plan she
hired a hunter to
to sort of hunt Snow White pull up snow
its heart and feed it
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
that brought the heart of a deer which I
think in Disney the hunter did kill a
deer or betray early 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 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 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 eat now we could put an alpha
but I never put something I've 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
too so as we go down we take the alpha
beta for 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 to that it seems
from its child or its own infinity for a
beta it likes the two that's absolutely
right so - all right great so now we go
down to F what is F alpha who says who
says negative infinity this does too
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 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 gonna start calling up
people individually so hopefully people
pay attention to the mob who we're
always correct all right so we go down
to K and we see as three F is a
Maximizer node so what does F do now yes
which is it's outfit of three great
all right so that's already that's
already quite good it's which is alpha
two three it's very happy it's got a
three here that's nice that's a nice
value so what does it do let's see what
does it do at L yeah it's gone okay went
back up to F got firstsearch the next
one would be all right
well technically F could take L could
take L value of zero if it liked it
better than three but it's a Maximizer
so what does it want to take that okay
that technically would be correct but
I'm sorry I burden you with a trick
question
in fact we don't look at L at all does
everyone see that I'll explain the Alpha
at F has reached three but the beta at B
is 2 so B looks down and says wait a
minute if I go down to F my enemy's
nuclear option my enemies the worst it
can be for you know the best it can be
for me is 3 F F is trumpeting it around
I was thinking of you know eating his
heart or whatever but I didn't want to
but it's gonna be 3 it's gonna be 3 or
higher down down there at F there's no
way I want that I already have my own I
already have my own default escape plan
and that's to that is 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 if you see an alpha
it's higher than the beta above it as I
said you know if alpha goes up above
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 question is
who prunes who decides that you don't
look at L 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
hmm I don't want to look at Al because F
is already so terrible for me that is
just beyond belief it's gonna be 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 3 there's a sanity check that
I've written or that I sort of came up
with just in 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 note
contained that I'm about to skip contain
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 can't
contain a positive infinity would it
change anything if the answer is no both
times
then you were definitely correct in
pruning it so look at that zero if it
was a nigga to infinity minimizer wins
what would happen Maximizer would say
I'm not touching that with a ten-foot
pole
choosing three the minimizer would say
ah screw that I'll take e let's say it
was a positive infinity the Maximizer is
saying Eureka holy grail I win midnight
I would say yeah if I'm a moron and go
down to F and then we go to E and take
two so no matter what was their
minimizer we go to eat and you could say
well what if it was exactly two but he's
still the Maximizer would choose K and
the minimizer you go to eat 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 grandpappy a
and he has an alpha of negative infinity
everyone why what will he do
he'll take the - it's better than
negative infinity for him it's not
wonderful but surely anything is better
than an automatic loss all right now our
highest note is it - so let's keep that
in mind for our alpha okay so let's go
over here let's see so what will be the
value at C I'm not at you yet I'm
actually just starting the middle branch
so I'm going to see and what's gonna be
starting beta before I before I go down
infinity that's right default value is
easier than it seems alright 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 gonna now we go down depth-first
search to G what's gonna be our alpha at
G ah it would seem so
however take a look up at our at the you
know great-grandpappy a it seems to have
changed to two so this time it's - why
is it - instead of negative infinity why
can we let a be so obnoxious and not
start with saying oh I automatically
lose well a knows that no matter how
awful things get in that middle branch
he can 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 an 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 see yeah shows you I'm
going to a taking the two so therefore
alpha is actually two at G alright great
so we've got an alpha that's 2 at G
we're gonna go down to em it's a
minimizer all right what's gonna be our
beta value at M
or which is the beta default - or
positive infinity where the minimizer
infinity that's right
M is gonna 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 em when MC is the Q is 1
well this beta it says infinity I'm
sorry it's hard to read beta is infinity
again
that's right so beta is gonna be they're
gonna put beta to one because it sees Q
great all right so my next question is
let's see my next question is what's
gonna happen at our very smart you
you've you've detected my trap the
question is does it look at our the
answer is no it doesn't look at our why
does it look at our 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 to the Maximizer
says wait a minute if I if I suppose
what G says if I go to M the best I'm
getting out of this set 1 because if
this is negative infinity he'll
minimizer will choose if this is
positive infinity he'll choose 1 best
I'm gonna get out of here is 1 if that's
the case I might as well just going to
be and not even God to see so I'm not
gonna go to M I'll go to n maybe maybe
ends better does everyone see that great
so let's say that the Maximizer does go
to end so what's going to happen with
this alpha right gonna be seven seven is
better than two and the Maximizer has
control to get to that seven at least if
it gets to G all right now the minimizer
at C will help you everyone this time
the minimizer at sea seeing that seven
what does the minimizer do
so it sees the seven what is it - - 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 is a do when it sees the
six coming out of seat six that's right
alpha equals six great home stretch
people home stretch so the minimizer
everyone has beta of infinity and if I
wasn't just 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 gonna 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 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 the question
is which nodes are evaluated in order
our answer is everyone e K Q n H I okay
not so obvious I guess few people
followed me but it is a ekq NH is just
step first order when we prune some of
them away great so that is alpha beta
any questions about that before I give
some questions about progressive
deepening alright we've got a bunch so
first question
but it is when asked for the order of
evaluation or we include excluding FB C
and D the answers we're talking about
here static evaluation the static
evaluator is a very important and
interesting function and I'll get back
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's one up here
before but that's right the question is
just static nodes being the leaf nodes
the answer is yes Saturday valuation is
when you get that number at the static
node let me explain unless someone else
has a another question about alpha beta
let me explain static values because I
was about to do that there is a question
about alpha beta I'll come back to both
of yours after answer this always starts
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 Alpha is
that all the minimizer levels so 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 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 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 3 is
automatically completely done it's got a
3 similarly when we came back to G after
going to N and we knew that the value
was 7 that was completely done the value
was definitely 7 there was no other
possibilities right yes so once you're
done with all the children of G then G
comes up and says guess what guess what
guys
ok so technically before that you would
have said that like G's alpha is greater
than or equal to 1 and then when we said
when we looked at Q and then we look at
Emma we say it's equal exactly to 7
we're done here and then at that point
you know when it's fresh and ripe it 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 haven't I have
an infinity that's not I really like
that seven better and it takes the 7 but
then it saw H and said oh man that's a 6
that's even better than seven so it took
the 6 so alpha takes 6 because C is a
minimizer C took the 7 from G but then
right after that seesaw h and took the 6
because 6 is even lower than 7 and then
alpha took the 6 because 6 was higher
than 2 yeah the problem is that the
Maximizer doesn't have control there the
minimizer has got control at sea and the
minimizer is gonna make sure it's as low
as possible
the Maximizer at a his only control is
or sure only control is the ability to
send our way to B or C or D or at least
and then at that point it's C the
minimizer gets to choose if we go to G
or H and it's never gonna choose G
because G is higher than age all right
awesome is there another question all
right let's go back to stat evaluations
when I first took 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 gonna pose you guys the actual
question that would have been on one of
the older test which is the following I
had a student who came to me and said
you don't mark when we do this I would
bethe 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 three
there it takes no time to do the second
valuation it's on them 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 hide 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 sixth
170 java def lab that used the class
that used to exist we had a program
called anti chess where I used my 603
four 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 the board position the
state of the game and 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
will you know that I controlled also
well it was an anti chess but that's not
what standing let's pretend is regular
chess I also had to look if it was in
regular chess and I still had to do the
senator says if my king was in checked
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 and regular
chess is a legal to put your key in to
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 do set
of 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
doesn't
careful analysis of the state of the
game and says I'm good heuristic aliy
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
question hypothetically that might have
been on the old test when the person
said I've got this a great idea where we
do tons of static evaluation 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 waters a static evaluation why
are the leaf nodes called static
basically the you might ask why are some
of these is static you 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 heuristic
values in the search tree it'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 gonna lead us
into the answer to water the question is
about progressive deepening so I'll put
up the crow guess of deepening question
really quickly so the question is this
suppose that let me see this is a
Maximizer yes
suppose that we do progressive deepening
on 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 doesn't take
in this tree it doesn't work but in
trees that actually branch like two to
the N 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 genius
friend who told us that the static
values when we went up to two levels
remember we go to two levels F G 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 three seven and twenty genius
brilliant all right so if that happens
how is the bet what is the best way that
we could reorder that tree oh yeah yeah
yeah
so it's ABCD with values of two three
seven six 120 I'll draw that this is the
non reordered tree let's see so it's two
three seven six 120 so what's the best
way to reorder well first of all does
anyone remember what patsak said when
you talked about progressive deepening
usually no one does so don't worry about
it
the best way to 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 alpha 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 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 to
the middle branch was our current past
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 all
there's one we're done and we cut
everything off in other words the branch
that turns out to be the one that you
take you have to do a 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 node say this is wrong done so
therefore if the one that turns out to
be the eventual winner is first of all
that it's really easy to reject all the
other branches 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 heuristic is good and that
these guesses are pretty much close to
the truth and turns out they're perfect
so this is gonna 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
gonna pick e we think it's gonna pick H
we think it's gonna fit I so first of
all we should put a before F X before G
and I before J because we think it's
gonna pick those first those are
positive our best ones to invalidate a
poor branch so now between 2 6 and 1
which is what we think we're gonna get
which one do we think the Maximizer is
going to take 6 then if it couldn't take
6 what would be its next best choice 2
then 1 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 see you guys
told me CB s ID you told me CBD I think
yeah those are 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 before app and you guys told me
I before J and you guys would be correct
in all regards we have 6 7 2 3 1 20
all the minimizer's choose from smallest
to highest the Maximizer chooses from
highest to lowest of the one that
minimizer's 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 well we
looked at if we look 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 French was six as soon as we
saw two for the beta here two is less
than six we could have proved 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 branch and it
actually only would have saved just one
node oops so it winds up that in total
how many nodes would be evaluated if we
did if we did that little scheme of
reordering well we normally had to do
six right EK q h q nhi how many do we
evaluate if we do this this progressive
deepening scheme how many times we run
the static evaluator which is of course
you know the static evaluator takes a
long time I even 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 to give this one so yeah I said
the only one we save on is case 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 anyway does that agree that
we did six before if we didn't do any
progressive deepening we just you know
did e KQ n H 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
8kq and h i these five static
evaluations we didn't do the k or or we
might have saved ourselves because maybe
we were smart and decided to cast the
about static values when we were going
down the tree it said implementations
you tailed it on this test when we ask
that question we didn't say but I mean
by cache is when we did it here and saw
that he was a two and then here oh we
have to do the static value at E but 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 e H 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
though progressive G beings 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 double even double at
each level it would have what like 16
nodes down here at the bottom then you
would want to be doing that progressive
deepening so now
I asked 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
according to this test 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 gonna 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 agree to I
repeat it okay the question is ignoring
the cost that we pay progressively
deepening here just forget about it at
the final step in 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 based on the best order for
progressive deepening here certainly we
did but the question is is Steve
guaranteed answer that's the answer and
the whyatt which we asked to explain the
answer we got is that doesn't that
depend on the heuristic perfectly
correct the answer is no we're not
guaranteed and it depends on the hero
state so if we were guaranteed that
would mean our heuristic was godlike
like this heuristic if our your hosting
already tells you the correct answer no
matter what don't do game search just go
to the empty chat of the chessboard put
all the pieces in the front rows and run
the stack 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 heuristic is flawed in some way
it could be very flawed if it's flawed
so badly that it tells us a very bad
result of what's actually gonna happen
even though we think the minimizer is
gonna go to H maybe it's wrong by a lot
it goes to G it could take us even worse
path and make us take longer question
the question how can you catch the
values if it's a heuristic so you don't
have to recover it them later the answer
is it wouldn't help if there weren't
these weird multi-level things where we
stopped at ease up for some reason even
though it goes down to five levels the
way you could cache it is it is a
heuristic but it's consistent and I
don't mean consistent from search I mean
it's a consistent heuristic in in the
state game state II is let's say that's
the state where I moved out my night as
the Maximizer minimums and said you're
doing the night opening really and then
did a counter attack no matter how we
get to eat or where we go to get to e
that's always gonna be state e it's
always gonna have the same heuristic
value it's not like some guy who like
goes around and just randomly pulls a
number out of a hat for something we're
gonna have some value where that gives
us points based on state e and it's
gonna be the same any time we go to
state eat does that make sense it is a
heuristic but it's always gonna 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 heuristic that's the
opposite of correct it always tells us
the worst move it claims it's the best
that's the heuristic that the
minimizer's were programmed into our
computer perhaps in that case when we do
progressive deepening and we reorder
we'll probably get the worst pruning
possible so we may not but we may so in
that case you're not guaranteed hope
that's given a little a few clues in
tutorial you guys are gonna see some
more interesting problems that go into a
few other details I at least plan on
doing you ins interesting game problem
from last year which asked a bunch of
asked a bunch of for 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 do the
next quiz so have a great weekend don't
stress out too much about the quiz