Advertisement
English transcript
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.
PROFESSOR: 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 6034 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 it has never been revealed until today.
Because I made up name recently.
So you will be the first people to hear it and decide
if it works better than 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 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 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 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.
All right, as you guys remember, the game search
when using regular minimax is essentially
a depth first search.
And at each level, it chooses between all
of the children whichever value that the parent wants.
So here after 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 up for a while.
So we're doing A. We need the maximum of B, C,
D, depth first search.
We go to B. We're looking for the minimum of E and F.
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 its children are K and L. So now I'm
going to start making you guys do stuff.
So what do you think?
What is going to be the minimax value at F?
The minimax value at F, what will that be?
AUDIENCE: [INAUDIBLE]
PROFESSOR: So that level is a maximizer-- max, min, max.
F is a maximizer.
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 or L. So the minimax value is three.
And yeah, the path 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.
So if this is 3 and this is 2, then everyone,
we know that the value of B is?
AUDIENCE: [INAUDIBLE]
PROFESSOR: I hear 3 and 2.
Which one is it?
AUDIENCE: 2.
PROFESSOR: 2, that's right.
So the value here is 2.
Great, let's go down into this branch.
So C is going to be the minimum of G and 6.
But we don't see that yet.
Because we're doing a depth first search.
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?
AUDIENCE: 1.
PROFESSOR: Let's see.
That's right, it's 1.
So M has a value of 1.
But I'm going to stay over here.
Because M has a value of 1.
Knowing that, then we know that G has a value of?
AUDIENCE: 7
PROFESSOR: 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?
AUDIENCE: 6.
PROFESSOR: Yes, C has a value of 6.
That's the minimum 6 and 7.
So now I'm going to go back down.
Because we've done one of the other sub-trees.
This is a 6.
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 1.
We go down to J. And let's see, what's the minimax value of J?
AUDIENCE: It's 20.
PROFESSOR: That's right.
20 is the maximum of 20 and 2.
Great, so what's the minimax value of D?
Everyone said it-- 1.
All right, so what's the minimax value at A?
AUDIENCE: 6.
PROFESSOR: 6 is right.
6 is higher than 2.
It's higher than 1.
Our value is 6.
And our path is-- everyone-- A, C, H. That's it.
Great, is 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
would like some clarifications on minimax, raise your hand.
There's probably a few other people who would like some too.
OK.
AUDIENCE: When you're doing this minimax, whatever values
are not showing, you keep going down the tree
and then just look at whether you're
trying to find the minimax.
And just whatever values you get you go back up one?
PROFESSOR: Yes.
The question was, when you go to do the minimax-- and let's
say you got E was 2, and you know
that B is going to 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,
it turns out it probably doesn't matter what you do.
I suggested doing a depth first search to get yourself
in the mindset of alpha-beta.
Because order is very, very important in alpha-beta.
But here, I don't know, you could do some weird bottom
up search.
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're evaluated in is depth first search order.
So without even doing anything, E, K, L, Q, R, N, H, I, O, P
are the order of starting evaluation in this tree.
AUDIENCE: [INAUDIBLE]
PROFESSOR: So the question is, 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 would put 1 there.
So at M, we would put a 1.
But people remembered that.
So we didn't do it.
But then at G, we would put a 7.
So if we were writing it out very formally,
we would have a 1 and a 7.
And at this D, we would have a 1.
And then at the A, we would put a 6.
And then that's the answer.
Also, we've 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 a game tree.
And so once you've done alpha-beta,
if you can do it correctly, you'll
think, oh, minimax, oh, those 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 trip 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 all sort of a winning formula,
except for it's not.
Because it takes too long.
But it's a very nice formula.
U is the maximizer, say.
I would try to think, if I do this, what's he going to do?
And then if he does that, what am I going to do?
And then what is he going to do if I
do that, et cetera, et cetera, all the way to the bottom.
With alpha and beta, we add in what
I like to call nuclear options.
I'd like in this game of maximizer minimizer--
you can think of it as like the Cold War or the Peloponnesian
War, except the Peloponnesian War didn't have nukes, so
probably the Cold War.
And in the Cold War, or any situation
where you're up against an adversary who-- actually,
this doesn't really work as well for the Cold War.
But in any situation where you're
up against an adversary whose only goal in life
is to destroy you, you always want
to find out what the best thing you can possibly do
is 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 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 worst possible outcome
you'd be willing to accept for your side.
Because right now, you know 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.
Nuclear options-- alpha is maximizer's 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 fail-safe?
We could always fall back on this number.
So you could set 0.
You could try to set some low number for the maximizer.
Because if you set a high number for the maximizer
as its fail-safe, it's going to be really snooty 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 tree.
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.
So if we set negative infinity as a 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 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 node
here.
That makes sure the maximizer and the minimizer
both are willing to look at the first path they see every time.
Because 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 be like, hmm,
this test game is very interesting.
However, I have another option-- pft,
and then you 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 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, the minimizer
sees, oh, look at that.
I can guarantee that at best the maximizer gets 100.
Haha, beta is now 100.
The maximizer says, oh yeah?
Well I can guarantee that the lowest you can get me to go to
is 0.
So it's going to be 0.
And this keeps going on until maybe at 6-- note,
not drawn to scale.
Maybe at 6, the maximizer said, haha,
you can't make me go lower than 6.
And the minimizer says, aha, you can't make me go higher than 6.
And then 6 is the answer.
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 remaining stuff.
I'm going to 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, say, 50.
And the minimizer says, that's strange.
Because the highest that you can make me go is 40.
So 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 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 that node is 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,
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 it goes.
So the way that it works, the way that alpha and beta works,
is the Snow White principal.
So does everyone know the story of Snow White?
So 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 it's the stepdaughter.
So much like in the real world, in Snow White,
the stepdaughter, 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 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 principle.
So let's see how that goes.
Well, I told you guys that the default alpha was--
AUDIENCE: Negative infinity.
PROFESSOR: 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 an alpha or a beta
for one of the terminal nodes.
Because it can't really do anything.
It's just 2.
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 2 that it sees from its child or its own infinity
for a beta?
AUDIENCE: 2
PROFESSOR: It likes the 2.
That's absolutely right.
So 2.
All right, great, so now we go down to F. What is F's alpha?
Who says negative infinity?
Who says 2?
No one-- oh, you guys are good.
It's negative infinity.
Technically, it also will have a beta of 2.
But we're ignoring the beta.
And the alphas that have been progressing downward
from the parents-- negative infinity.
That's why I called it the grandfather clause before.
Because you would often look up to your grandparent to see what
your default number is.
So we get 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.
All right, so we go down to K. And we see a 3.
F is a maximizer node.
So what does F do now?
AUDIENCE: Switches its alpha to 3.
PROFESSOR: Yes, switches its alpha to 3, great.
All right, so that's already quite good.
It switches alpha to 3.
It's very happy.
It's got a 3 here.
That's a nice value.
So what does it do at L, the next node?
It's gone to K, went back up to F. Depth
first search, the next one would be L, right?
AUDIENCE: [INAUDIBLE]
PROFESSOR: Well, technically F could take L's value of 0
if it liked it better than 3.
But it's a maximizer.
So does it want to take that?
AUDIENCE: [INAUDIBLE]
PROFESSOR: OK, that technically would be correct.
But I'm sorry.
I burdened 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 3.
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 enemy is the worst it can be for-- the best it
can be for me is 3.
F is trumpeting it around.
I was thinking of eating his heart, or whatever,
but I didn't want to.
But it's going to be 3.
It's going to be 3 or higher down there at F.
There's no way I want that.
I already have my own default escape plan.
And that's 2.
That's going to be better than whatever comes out
of that horrible F. So screw it.
And we never look at L. Does everyone get that?
That is the main principle of alpha-beta pruning.
If you see an alpha that's higher than the beta above it--
as I said, if alpha goes up above the beta--
or if you see a beta, like if there's a beta down here,
and it's lower than the alpha above it, prune it.
Stop doing that.
And 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 L. Because F is already so terrible for me
that it's just beyond belief.
If this is 100, it might be 100.
Even if it's lower, I'm still going to get a three.
There's a sanity check that I've written 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 one's do you evaluate, which ones do you skip, right?
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 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
contained a positive infinity, would it change anything?
If the answer is no both times, then you're
definitely correct in pruning it.
So look at that 0.
If it was a negative infinity, minimizer wins,
what would happen?
The maximizer would say, I'm not touching that was a 10 foot
pole, choosing 3.
The minimizer would say, screw that, I'll take E.
Let's say it was a positive infinity.
The maximizer would say, eureka, holy grain, I win.
The minimizer would say, yeah, if I'm a moron,
and go down to F, and then would go to E and take 2.
So no matter what was there, the minimizer would go to E.
And you could say, well, what if it was exactly 2?
But still the maximizer would choose
K. 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 with this branch.
Because beta is 2.
So now we're up at old grandpappy A.
And he has an alpha of negative infinity.
Everyone, what will he do?
He'll take the 2.
It's better than negative infinity for him.
It's not wonderful.
B
…
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.
PROFESSOR: 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 6034 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 it has never been revealed until today.
Because I made up name recently.
So you will be the first people to hear it and decide
if it works better than 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 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 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 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.
All right, as you guys remember, the game search
when using regular minimax is essentially
a depth first search.
And at each level, it chooses between all
of the children whichever value that the parent wants.
So here after 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 up for a while.
So we're doing A. We need the maximum of B, C,
D, depth first search.
We go to B. We're looking for the minimum of E and F.
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 its children are K and L. So now I'm
going to start making you guys do stuff.
So what do you think?
What is going to be the minimax value at F?
The minimax value at F, what will that be?
AUDIENCE: [INAUDIBLE]
PROFESSOR: So that level is a maximizer-- max, min, max.
F is a maximizer.
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 or L. So the minimax value is three.
And yeah, the path 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.
So if this is 3 and this is 2, then everyone,
we know that the value of B is?
AUDIENCE: [INAUDIBLE]
PROFESSOR: I hear 3 and 2.
Which one is it?
AUDIENCE: 2.
PROFESSOR: 2, that's right.
So the value here is 2.
Great, let's go down into this branch.
So C is going to be the minimum of G and 6.
But we don't see that yet.
Because we're doing a depth first search.
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?
AUDIENCE: 1.
PROFESSOR: Let's see.
That's right, it's 1.
So M has a value of 1.
But I'm going to stay over here.
Because M has a value of 1.
Knowing that, then we know that G has a value of?
AUDIENCE: 7
PROFESSOR: 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?
AUDIENCE: 6.
PROFESSOR: Yes, C has a value of 6.
That's the minimum 6 and 7.
So now I'm going to go back down.
Because we've done one of the other sub-trees.
This is a 6.
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 1.
We go down to J. And let's see, what's the minimax value of J?
AUDIENCE: It's 20.
PROFESSOR: That's right.
20 is the maximum of 20 and 2.
Great, so what's the minimax value of D?
Everyone said it-- 1.
All right, so what's the minimax value at A?
AUDIENCE: 6.
PROFESSOR: 6 is right.
6 is higher than 2.
It's higher than 1.
Our value is 6.
And our path is-- everyone-- A, C, H. That's it.
Great, is 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
would like some clarifications on minimax, raise your hand.
There's probably a few other people who would like some too.
OK.
AUDIENCE: When you're doing this minimax, whatever values
are not showing, you keep going down the tree
and then just look at whether you're
trying to find the minimax.
And just whatever values you get you go back up one?
PROFESSOR: Yes.
The question was, when you go to do the minimax-- and let's
say you got E was 2, and you know
that B is going to 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,
it turns out it probably doesn't matter what you do.
I suggested doing a depth first search to get yourself
in the mindset of alpha-beta.
Because order is very, very important in alpha-beta.
But here, I don't know, you could do some weird bottom
up search.
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're evaluated in is depth first search order.
So without even doing anything, E, K, L, Q, R, N, H, I, O, P
are the order of starting evaluation in this tree.
AUDIENCE: [INAUDIBLE]
PROFESSOR: So the question is, 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 would put 1 there.
So at M, we would put a 1.
But people remembered that.
So we didn't do it.
But then at G, we would put a 7.
So if we were writing it out very formally,
we would have a 1 and a 7.
And at this D, we would have a 1.
And then at the A, we would put a 6.
And then that's the answer.
Also, we've 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 a game tree.
And so once you've done alpha-beta,
if you can do it correctly, you'll
think, oh, minimax, oh, those 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 trip 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 all sort of a winning formula,
except for it's not.
Because it takes too long.
But it's a very nice formula.
U is the maximizer, say.
I would try to think, if I do this, what's he going to do?
And then if he does that, what am I going to do?
And then what is he going to do if I
do that, et cetera, et cetera, all the way to the bottom.
With alpha and beta, we add in what
I like to call nuclear options.
I'd like in this game of maximizer minimizer--
you can think of it as like the Cold War or the Peloponnesian
War, except the Peloponnesian War didn't have nukes, so
probably the Cold War.
And in the Cold War, or any situation
where you're up against an adversary who-- actually,
this doesn't really work as well for the Cold War.
But in any situation where you're
up against an adversary whose only goal in life
is to destroy you, you always want
to find out what the best thing you can possibly do
is 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 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 worst possible outcome
you'd be willing to accept for your side.
Because right now, you know 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.
Nuclear options-- alpha is maximizer's 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 fail-safe?
We could always fall back on this number.
So you could set 0.
You could try to set some low number for the maximizer.
Because if you set a high number for the maximizer
as its fail-safe, it's going to be really snooty 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 tree.
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.
So if we set negative infinity as a 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 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 node
here.
That makes sure the maximizer and the minimizer
both are willing to look at the first path they see every time.
Because 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 be like, hmm,
this test game is very interesting.
However, I have another option-- pft,
and then you 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 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, the minimizer
sees, oh, look at that.
I can guarantee that at best the maximizer gets 100.
Haha, beta is now 100.
The maximizer says, oh yeah?
Well I can guarantee that the lowest you can get me to go to
is 0.
So it's going to be 0.
And this keeps going on until maybe at 6-- note,
not drawn to scale.
Maybe at 6, the maximizer said, haha,
you can't make me go lower than 6.
And the minimizer says, aha, you can't make me go higher than 6.
And then 6 is the answer.
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 remaining stuff.
I'm going to 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, say, 50.
And the minimizer says, that's strange.
Because the highest that you can make me go is 40.
So 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 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 that node is 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,
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 it goes.
So the way that it works, the way that alpha and beta works,
is the Snow White principal.
So does everyone know the story of Snow White?
So 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 it's the stepdaughter.
So much like in the real world, in Snow White,
the stepdaughter, 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 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 principle.
So let's see how that goes.
Well, I told you guys that the default alpha was--
AUDIENCE: Negative infinity.
PROFESSOR: 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 an alpha or a beta
for one of the terminal nodes.
Because it can't really do anything.
It's just 2.
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 2 that it sees from its child or its own infinity
for a beta?
AUDIENCE: 2
PROFESSOR: It likes the 2.
That's absolutely right.
So 2.
All right, great, so now we go down to F. What is F's alpha?
Who says negative infinity?
Who says 2?
No one-- oh, you guys are good.
It's negative infinity.
Technically, it also will have a beta of 2.
But we're ignoring the beta.
And the alphas that have been progressing downward
from the parents-- negative infinity.
That's why I called it the grandfather clause before.
Because you would often look up to your grandparent to see what
your default number is.
So we get 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.
All right, so we go down to K. And we see a 3.
F is a maximizer node.
So what does F do now?
AUDIENCE: Switches its alpha to 3.
PROFESSOR: Yes, switches its alpha to 3, great.
All right, so that's already quite good.
It switches alpha to 3.
It's very happy.
It's got a 3 here.
That's a nice value.
So what does it do at L, the next node?
It's gone to K, went back up to F. Depth
first search, the next one would be L, right?
AUDIENCE: [INAUDIBLE]
PROFESSOR: Well, technically F could take L's value of 0
if it liked it better than 3.
But it's a maximizer.
So does it want to take that?
AUDIENCE: [INAUDIBLE]
PROFESSOR: OK, that technically would be correct.
But I'm sorry.
I burdened 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 3.
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 enemy is the worst it can be for-- the best it
can be for me is 3.
F is trumpeting it around.
I was thinking of eating his heart, or whatever,
but I didn't want to.
But it's going to be 3.
It's going to be 3 or higher down there at F.
There's no way I want that.
I already have my own default escape plan.
And that's 2.
That's going to be better than whatever comes out
of that horrible F. So screw it.
And we never look at L. Does everyone get that?
That is the main principle of alpha-beta pruning.
If you see an alpha that's higher than the beta above it--
as I said, if alpha goes up above the beta--
or if you see a beta, like if there's a beta down here,
and it's lower than the alpha above it, prune it.
Stop doing that.
And 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 L. Because F is already so terrible for me
that it's just beyond belief.
If this is 100, it might be 100.
Even if it's lower, I'm still going to get a three.
There's a sanity check that I've written 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 one's do you evaluate, which ones do you skip, right?
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 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
contained a positive infinity, would it change anything?
If the answer is no both times, then you're
definitely correct in pruning it.
So look at that 0.
If it was a negative infinity, minimizer wins,
what would happen?
The maximizer would say, I'm not touching that was a 10 foot
pole, choosing 3.
The minimizer would say, screw that, I'll take E.
Let's say it was a positive infinity.
The maximizer would say, eureka, holy grain, I win.
The minimizer would say, yeah, if I'm a moron,
and go down to F, and then would go to E and take 2.
So no matter what was there, the minimizer would go to E.
And you could say, well, what if it was exactly 2?
But still the maximizer would choose
K. 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 with this branch.
Because beta is 2.
So now we're up at old grandpappy A.
And he has an alpha of negative infinity.
Everyone, what will he do?
He'll take the 2.
It's better than negative infinity for him.
It's not wonderful.
B
…