Advertisement
English transcript
SPEAKER 1: It was about 1963 when a noted philosopher here
at MIT, named Hubert Dreyfus--
Hubert Dreyfus wrote a paper in about 1963 in which he had
a heading titled, "Computers Can't Play Chess." Of course,
he was subsequently invited over to the artificial
intelligence laboratory to play the
Greenblatt chess machine.
And, of course, he lost.
Whereupon Seymour Pavitt wrote a rebuttal to Dreyfus' famous
paper, which had a subject heading, "Dreyfus Can't Play
Chess Either."
But in a strange sense, Dreyfus might have been right
and would have been right if he were to have said computers
can't play chess the way humans play chess yet.
In any case, around about 1968 a chess master named David
Levy bet noted founder of artificial intelligence John
McCarthy that no computer would beat the world champion
within 10 years.
And five years later, McCarthy gave up, because it had
already become clear that no computer would win in a way
that McCarthy wanted it to win, that is to say by playing
chess the way humans play chess.
But then 20 years after that in 1997, Deep Blue beat the
world champion, and chess suddenly became uninteresting.
But we're going to talk about games today, because there are
elements of game-play that do model some of the things that
go on in our head.
And if they don't model things that go on in our head, they
do model some kind of intelligence.
And if we're to have a general understanding of what
intelligence is all about, we have to understand that kind
of intelligence, too.
So, we'll start out by talking about various ways that we
might design a computer program to
play a game like chess.
And we'll conclude by talking a little bit about what Deep
Blue adds to the mix other than tremendous speed.
So, that's our agenda.
By the end of the hour, you'll understand and be able to
write your own Deep Blue if you feel like it.
First, we want to talk about how it might be possible for a
computer to play chess.
Let's talk about several approaches
that might be possible.
Approach number one is that the machine might make a
description of the board the same way a human would; talk
about pawn structure, King safety, whether it's a good
time to castle, that sort of thing.
So, it would be analysis and perhaps some strategy mixed up
with some tactics.
And all that would get mixed up and, finally, result in
some kind of move.
If this is the game board, the next thing to do would be
determined by some process like that.
And the trouble is no one knows how to do it.
And so in that sense, Dreyfus is right.
None the game playing programs today incorporate any of that
kind of stuff.
And since nobody knows how to do that, we
can't talk about it.
So we can talk about other ways, though,
that we might try.
For example, we can have if-then rules.
How would that work?
That would work this way.
You look at the board, represented by this node here,
and you say, well, if it's possible to move the Queen
pawn forward by one, then do that.
So, it doesn't do any of evaluation of the board.
It doesn't try anything.
It just says let me look at the board and select a move on
that basis.
So, that would be a way of approaching a game
situation like this.
Here's the situation.
Here are the possible moves.
And one is selected on the basis of an
if-then rule like so.
And nobody can make a very strong chess player
that works like that.
Curiously enough, someone has made a pretty good checkers
playing program that works like that.
It checks to see what moves are available on the board,
ranks them, and picks the highest one available.
But, in general, that's not a very good approach.
It's not very powerful.
You couldn't make it--
well, when I say, couldn't, it means I can't think of any way
that you could make a strong chess playing
program that way.
So, the third way to do this is to look ahead and evaluate.
What that means is you look ahead like so.
You see all the possible consequences of moves, and you
say, which of these board situations is best for me?
So, that would be an approach that comes in here like so and
says, which one of those three situations is best?
And to do that, we have to have some way of evaluating
the situation deciding which of those is best.
Now, I want to do a little, brief aside, because I want to
talk about the mechanisms that are popularly used to do that
kind of evaluation.
In the end, there are lots of features of the chessboard.
Let's call them f1, f2, and so on.
And we might form some function of those features.
And that, overall, is called the static value.
So, it's static because you're not exploring any consequences
of what might happen.
You're just looking at the board as it is, checking the
King's safety, checking the pawn structure.
Each of those produces a number fed into this function,
out comes a value.
And that is a value of the board seen from your
perspective.
Now, normally, this function, g, is reduced to a linear
polynomial.
So, in the end, the most popular kind of way of forming
a static value is to take f1, multiply it times some
constant, c1, add c2, multiply it times f2.
And that is a linear scoring polynomial.
So, we could use that function to produce numbers from each
of these things and then pick the highest number.
And that would be a way of playing the game.
Actually, a scoring polynomial is a little bit
more than we need.
Because all we really need is a method that looks at those
three boards and says, I like this one best.
It doesn't have to rank them.
It doesn't have to give them numbers.
All it has to do is say which one it likes best.
So, one way of doing that is to use a linear scoring
polynomial.
But it's not the only way of doing that.
So, that's number two and number three.
But now what else might we do?
Well, if we reflect back on some of the searches we talked
about, what's the base case against which everything else
is compared much the way of doing search that doesn't
require any intelligence, just brute force?
We could use the British Museum algorithm and simply
evaluate the entire tree of possibilities; I move, you
move, I move, you move, all the way down to--
what?--
maybe 100, 50 moves.
You do 50 things.
I do 50 things.
So, before we can decide if that's a good idea or not, we
probably ought to develop some vocabulary.
So, consider this tree of moves.
There will be some number of choices
considered at each level.
And there will be some number of levels.
So, the standard language for this as we call this the
branching factor.
And in this particular case, b is equal to 3.
This is the depth of the tree.
And, in this case, d is two.
So, now that produces a certain number of terminal or
leaf nodes.
How many of those are there?
Well, that's pretty simple computation.
It's just b to the d.
Right, Christopher, b to the d?
So, if you have b to the d at this level, you have one.
b to the d at this level, you have b.
b to the d at this level, you have [? d ?] squared.
So, b to the d, in this particular case, is 9.
So, now we can use this vocabulary that we've
developed to talk about whether it's reasonable to
just do the British Museum algorithm, be done with it,
forget about chess, and go home.
Well, let's see.
It's pretty deep down there.
If we think about chess, and we think about a standard game
which each person does 50 things, that
gives a d about 100.
And if you think about the branching factor in chess,
it's generally presumed to be, depending on the stage of the
game and so on and so forth, it varies, but it might
average around 14 or 15.
If it were just 10, that would be 10 to the 100th.
But it's a little more than that, because the branching
factor is more than 10.
So, in the end, it looks like, according to Claude Shannon,
there are about 10 to the 120th leaf nodes down there.
And if you're going to go to a British Museum treatment of
this tree, you'd have to do 10 to the 120th static
evaluations down there at the bottom if you're going to see
which one of the moves is best at the top.
Is that a reasonable number?
It didn't used to seem practicable.
It used to seem impossible.
But now we've got cloud computing and everything.
And maybe we could actually do that, right?
What do you think, Vanessa, can you do that, get enough
computers going in the cloud?
No?
You're not sure?
Should we work it out?
Let's work it out.
I'll need some help, especially from any of you who
are studying cosmology.
So, we'll start with how many atoms are
there in the universe?
Volunteers?
10 to the--
SPEAKER 2: 10 to the 38th?
SPEAKER 1: No, no, 10 to the 38th has been offered.
That's why it's way too low.
The last time I looked, it was about 10 to the 80th atoms in
the universe.
The next thing I'd like to know is how many seconds are
there in a year?
It's a good number have memorized.
That number is approximately pi times 10 to the seventh.
So, how many nanoseconds in a second?
That gives us 10 to the ninth.
At last, how many years are there in the
history of the universe?
SPEAKER 3: [INAUDIBLE].
14.7 billion.
SPEAKER 1: She offers something on the order of 10
billion, maybe 14 billion.
But we'll say 10 billion to make our calculation simple.
That's 10 to the 10th years.
If we will add that up, 80, 90, plus 16, that's 10 to the
106th nanoseconds in the history of the universe.
Multiply it times the number of atoms in the universe.
So, if all of the atoms in the universe were doing static
evaluations at nanosecond speeds since the beginning of
the Big Bang, we'd still be 14 orders of magnitudes short.
So, it'd be a pretty good cloud.
It would have to harness together lots of universes.
So, the British Museum algorithm is
not going to work.
No good.
So, what we're going to have to do is we're going to have
to put some things together and hope for the best.
So, the fifth way is the way we're actually going to do it.
And what we're going to do is we're going to look ahead, not
just one level, but as far as possible.
We consider, not only the situation that we've developed
here, but we'll try to push that out as far as we can and
look at these static values of the leaf nodes down here and
somehow use that as a way of playing the game.
So, that is number five.
And number four is going all the way down there.
And this, in the end, is all that we can do.
This idea is multiply invented most notably by Claude Shannon
and also by Alan Turing, who, I found out from a friend of
mine, spent a lot a lunch time conversations talking with
each other about how a computer might play chess
against the future when there would be computers.
So, Donald, Mickey and Alan Turing also invented this over
lunch while they were taking some time off from cracking
the German codes.
Well, what is the method?
I want to illustrate the method with the simplest
possible tree.
So, we're going to have a branching factor of 2 not 14.
And we're going to have a depth of 2 not something
highly serious.
Here's the game tree.
And there are going to be some numbers
down here at the bottom.
And these are going to be the value of the board from the
perspective of the player at the top.
Let us say that the player at the top would like to drive
the play as much as possible toward the big numbers.
So, we're going to call that player the maximizing player.
He would like to get over here to the 8, because that's the
biggest number.
There's another player, his opponent, which we'll call the
minimizing player.
And he's hoping that the play will go down to the board
situation that's as small as possible.
Because his view is the opposite of the maximizing
player, hence the name minimax.
But how does it work?
Do you see which way the play is going to go?
How do you decide which way the play is going to go?
Well, it's not obvious at a glance.
Do you see which way it's going to go?
It's not obvious to the glance.
But if we do more than a glance, if we look at the
situation from the perspective of the minimizing player here
at the middle level, it's pretty clear that if the
minimizing player finds himself in that situation,
he's going to choose to go that way.
And so the value of this situation, from the
perspective of the minimizing player, is 2.
He'd never go over there to the 7.
Similarly, if the minimizing player is over here with a
choice between going toward a 1 or toward an 8, he'll
obviously go toward a 1.
And so the value of that board situation, from the
perspective of the minimizing player, is 1.
Now, we've taken the scores down here at the bottom of the
tree, and we back them up one level.
And you see how we can just keep doing this?
Now the maximizing player can see that if he goes to the
left, he gets a score of 2.
If he goes to the right, he only gets a score of 1.
So, he's going to go to the left.
So, overall, then, the maximizing player is going to
have a 2 as the perceived value of that situation there
at the top.
That's the minimax algorithm.
It's very simple.
You go down to the bottom of the tree, you compute static
values, you back them up level by level, and then you decide
where to go.
And in this particular situation, the maximizer goes
to the left.
And the minimizer goes to the left, too, so the play ends up
here, far short of the 8 that the maximizer wanted and less
than the 1 that the minimizer wanted.
But this is an adversarial game.
You're competing with each other.
So, you don't expect to get what you want, right?
So, maybe we ought to see if we can make that work.
There's a game tree.
Do you see how it goes?
Let's see if the system can figure it out.
There it goes, crawling its way through the tree.
This is a branching factor of 2, just like our sample, but
now four levels.
You can see that it's got quite a lot of work to do.
That's 2 to the fourth, one, two, three, four, 2 to the
fourth, 16 static evaluations to do.
So, it found the answer.
But it's a lot of work.
We could get a new tree and restart it, maybe speed it up.
There is goes down that way, get a new tree.
Those are just random numbers.
So, each time it's going to find a different path through
the tree according to the numbers that it's generated.
Now, 16 isn't bad.
But if you get down there around 10 levels deep and your
branching factor is 14, well, we know those numbers get
pretty awful pretty bad, because the number of static
evaluations to do down there at the bottom
goes as b to the d.
It's exponential.
And time has shown, if you get down about seven or eight
levels, you're a jerk.
And if you get down about 15 or 16 levels, you beat the
world champion.
So, you'd like to get as far down in the tree as possible.
Because when you get as far down into the tree as
possible, what happens is as these that these crude
measures of bored quality begin to clarify.
And, in fact, when you get far enough, the only thing that
really counts is piece count, one of those features.
If you get far enough, piece count and a few other things
will give you a pretty good idea of what to do if you get
far enough.
But getting far enough can be a problem.
So, we want to do everything we can to
get as far as possible.
We want to pull out every trick we can find to get as
far as possible.
Now, you remember when we talked about branching down,
we knew that there were some things that we could do that
would cut off whole portions of the search tree.
So, what we'd like to do is find something analogous to
this world of games, so we cut off whole portions of this
search tree, so we don't have to look at
those static values.
What I want to do is I want to come back and redo this thing.
But this time, I'm going to compute the static
values one at a time.
I've got the same structure in the tree.
And just as before, I'm going to assume that the top player
wants to go toward the maximum values, and the next player
wants to go toward the minimum values.
But none of the static values have been computed yet.
So, I better start computing them.
That's the first one I find, 2.
Now, as soon as I see that 2, as soon as the minimizer sees
that 2, the minimizer knows that the value of this node
can't be any greater than 2.
Because he'll always choose to go down this way if this
branch produces a bigger number.
So, we can say that the minimizer is assured already
that the score there will be equal to or less than 2.
Now, we go over and compute the next number.
There's a 7.
Now, I know this is exactly equal to 2, because he'll
never go down toward a 7.
As soon as the minimizer says equal to 2, the maximizer
says, OK, I can do equal to or greater than 2.
One, minimizer says equal to or less than 1.
Now what?
Did you prepare those 2 numbers?
The maximizer knows that if he goes down here, he can't do
better than 1.
He already knows if he goes over here, he an get a 2.
It's as if this branch doesn't even exist.
Because the maximizer would never choose to go down there.
So, you have to see that.
This is the important essence of the notion the alpha-beta
algorithm, which is a layering on top of minimax that cuts
off large sections of the search tree.
So, one more time.
We've developed a situation so we know that the maximizer
gets a 2 going down to the left, and he sees that if he
goes down to the right, he can't do better than 1.
So, he says to himself, it's as if that branch doesn't
exist and the overall score is 2.
And it doesn't matter what that static value is.
It can be 8, as it was, it can be plus 1,000.
It doesn't matter.
It can be minus 1,000.
Or it could be plus infinity or minus infinity.
It doesn't matter, because the maximizer will always
go the other way.
So, that's the alpha-beta algorithm.
Can you guess why it's called the alpha-beta algorithm?
Well, because in the algorithm there are two parameters,
alpha and beta.
So, it's important to understand that alpha-beta is
not an alternative to minimax.
It's minimax with a flourish.
It's something layered on top like we layered things on top
of branch and bound to make it more efficient.
We layer stuff on top of minimax to
make it more efficient.
As you say to me, well, that's a pretty easy example.
And it is.
So, let's try a little bit more complex one.
This is just to see if I can do it without screwing up.
The reason I do one that's complex is not just to show
how tough I am in front of a large audience.
But, rather, there's certain points of interest that only
occur in a tree of depth four or greater.
That's the reason for this example.
But work with me and let's see if we can work
our way through it.
What I'm going to do is I'll circle the numbers that we
actually have to compute.
So, we actually have to compute 8.
As soon as we do that, the minimizer knows that that node
is going to have a score of equal to or less than 8
without looking at anything else.
Then, he looks at 7.
So, that's equal to 7.
Because the minimizer will clearly go to the right.
As soon as that is determined, then the maximizer knows that
the score here is equal to or greater than 8.
Now, we evaluate the 3.
The minimizer knows equal to or less than 3.
SPEAKER 4: [INAUDIBLE].
SPEAKER 1: Oh, sorry, the minimizer at 7, yeah.
OK, now what happens?
Well, let's see, the maximizer gets a 7 going that way.
He can't do better than 3 going that way, so we got
another one of these cut off situations.
It's as if this branch doesn't even exist.
So, this static evaluation need not be made.
And now we know that that's not merely equal to or greater
than 7, but exactly equal to 7.
And we can push that number back up.
That becomes equal to or less than 7.
OK, are you with me so far?
Let's get over to the other side of the tree
as quickly as possible.
So, there's a 9, equal to or less than 9, 8 equal to 8,
push the 8 up equal or greater than 8.
The minimizer can go down this way and get a 7.
He'll certainly never go that way where the
maximizer can get an 8.
Once again, we've got a cut off.
And if this branch didn't exist, then that means that
these static evaluations don't have to be made.
And this value is now exactly 7.
But there's one more thing to note here.
And that is that not only do
…
at MIT, named Hubert Dreyfus--
Hubert Dreyfus wrote a paper in about 1963 in which he had
a heading titled, "Computers Can't Play Chess." Of course,
he was subsequently invited over to the artificial
intelligence laboratory to play the
Greenblatt chess machine.
And, of course, he lost.
Whereupon Seymour Pavitt wrote a rebuttal to Dreyfus' famous
paper, which had a subject heading, "Dreyfus Can't Play
Chess Either."
But in a strange sense, Dreyfus might have been right
and would have been right if he were to have said computers
can't play chess the way humans play chess yet.
In any case, around about 1968 a chess master named David
Levy bet noted founder of artificial intelligence John
McCarthy that no computer would beat the world champion
within 10 years.
And five years later, McCarthy gave up, because it had
already become clear that no computer would win in a way
that McCarthy wanted it to win, that is to say by playing
chess the way humans play chess.
But then 20 years after that in 1997, Deep Blue beat the
world champion, and chess suddenly became uninteresting.
But we're going to talk about games today, because there are
elements of game-play that do model some of the things that
go on in our head.
And if they don't model things that go on in our head, they
do model some kind of intelligence.
And if we're to have a general understanding of what
intelligence is all about, we have to understand that kind
of intelligence, too.
So, we'll start out by talking about various ways that we
might design a computer program to
play a game like chess.
And we'll conclude by talking a little bit about what Deep
Blue adds to the mix other than tremendous speed.
So, that's our agenda.
By the end of the hour, you'll understand and be able to
write your own Deep Blue if you feel like it.
First, we want to talk about how it might be possible for a
computer to play chess.
Let's talk about several approaches
that might be possible.
Approach number one is that the machine might make a
description of the board the same way a human would; talk
about pawn structure, King safety, whether it's a good
time to castle, that sort of thing.
So, it would be analysis and perhaps some strategy mixed up
with some tactics.
And all that would get mixed up and, finally, result in
some kind of move.
If this is the game board, the next thing to do would be
determined by some process like that.
And the trouble is no one knows how to do it.
And so in that sense, Dreyfus is right.
None the game playing programs today incorporate any of that
kind of stuff.
And since nobody knows how to do that, we
can't talk about it.
So we can talk about other ways, though,
that we might try.
For example, we can have if-then rules.
How would that work?
That would work this way.
You look at the board, represented by this node here,
and you say, well, if it's possible to move the Queen
pawn forward by one, then do that.
So, it doesn't do any of evaluation of the board.
It doesn't try anything.
It just says let me look at the board and select a move on
that basis.
So, that would be a way of approaching a game
situation like this.
Here's the situation.
Here are the possible moves.
And one is selected on the basis of an
if-then rule like so.
And nobody can make a very strong chess player
that works like that.
Curiously enough, someone has made a pretty good checkers
playing program that works like that.
It checks to see what moves are available on the board,
ranks them, and picks the highest one available.
But, in general, that's not a very good approach.
It's not very powerful.
You couldn't make it--
well, when I say, couldn't, it means I can't think of any way
that you could make a strong chess playing
program that way.
So, the third way to do this is to look ahead and evaluate.
What that means is you look ahead like so.
You see all the possible consequences of moves, and you
say, which of these board situations is best for me?
So, that would be an approach that comes in here like so and
says, which one of those three situations is best?
And to do that, we have to have some way of evaluating
the situation deciding which of those is best.
Now, I want to do a little, brief aside, because I want to
talk about the mechanisms that are popularly used to do that
kind of evaluation.
In the end, there are lots of features of the chessboard.
Let's call them f1, f2, and so on.
And we might form some function of those features.
And that, overall, is called the static value.
So, it's static because you're not exploring any consequences
of what might happen.
You're just looking at the board as it is, checking the
King's safety, checking the pawn structure.
Each of those produces a number fed into this function,
out comes a value.
And that is a value of the board seen from your
perspective.
Now, normally, this function, g, is reduced to a linear
polynomial.
So, in the end, the most popular kind of way of forming
a static value is to take f1, multiply it times some
constant, c1, add c2, multiply it times f2.
And that is a linear scoring polynomial.
So, we could use that function to produce numbers from each
of these things and then pick the highest number.
And that would be a way of playing the game.
Actually, a scoring polynomial is a little bit
more than we need.
Because all we really need is a method that looks at those
three boards and says, I like this one best.
It doesn't have to rank them.
It doesn't have to give them numbers.
All it has to do is say which one it likes best.
So, one way of doing that is to use a linear scoring
polynomial.
But it's not the only way of doing that.
So, that's number two and number three.
But now what else might we do?
Well, if we reflect back on some of the searches we talked
about, what's the base case against which everything else
is compared much the way of doing search that doesn't
require any intelligence, just brute force?
We could use the British Museum algorithm and simply
evaluate the entire tree of possibilities; I move, you
move, I move, you move, all the way down to--
what?--
maybe 100, 50 moves.
You do 50 things.
I do 50 things.
So, before we can decide if that's a good idea or not, we
probably ought to develop some vocabulary.
So, consider this tree of moves.
There will be some number of choices
considered at each level.
And there will be some number of levels.
So, the standard language for this as we call this the
branching factor.
And in this particular case, b is equal to 3.
This is the depth of the tree.
And, in this case, d is two.
So, now that produces a certain number of terminal or
leaf nodes.
How many of those are there?
Well, that's pretty simple computation.
It's just b to the d.
Right, Christopher, b to the d?
So, if you have b to the d at this level, you have one.
b to the d at this level, you have b.
b to the d at this level, you have [? d ?] squared.
So, b to the d, in this particular case, is 9.
So, now we can use this vocabulary that we've
developed to talk about whether it's reasonable to
just do the British Museum algorithm, be done with it,
forget about chess, and go home.
Well, let's see.
It's pretty deep down there.
If we think about chess, and we think about a standard game
which each person does 50 things, that
gives a d about 100.
And if you think about the branching factor in chess,
it's generally presumed to be, depending on the stage of the
game and so on and so forth, it varies, but it might
average around 14 or 15.
If it were just 10, that would be 10 to the 100th.
But it's a little more than that, because the branching
factor is more than 10.
So, in the end, it looks like, according to Claude Shannon,
there are about 10 to the 120th leaf nodes down there.
And if you're going to go to a British Museum treatment of
this tree, you'd have to do 10 to the 120th static
evaluations down there at the bottom if you're going to see
which one of the moves is best at the top.
Is that a reasonable number?
It didn't used to seem practicable.
It used to seem impossible.
But now we've got cloud computing and everything.
And maybe we could actually do that, right?
What do you think, Vanessa, can you do that, get enough
computers going in the cloud?
No?
You're not sure?
Should we work it out?
Let's work it out.
I'll need some help, especially from any of you who
are studying cosmology.
So, we'll start with how many atoms are
there in the universe?
Volunteers?
10 to the--
SPEAKER 2: 10 to the 38th?
SPEAKER 1: No, no, 10 to the 38th has been offered.
That's why it's way too low.
The last time I looked, it was about 10 to the 80th atoms in
the universe.
The next thing I'd like to know is how many seconds are
there in a year?
It's a good number have memorized.
That number is approximately pi times 10 to the seventh.
So, how many nanoseconds in a second?
That gives us 10 to the ninth.
At last, how many years are there in the
history of the universe?
SPEAKER 3: [INAUDIBLE].
14.7 billion.
SPEAKER 1: She offers something on the order of 10
billion, maybe 14 billion.
But we'll say 10 billion to make our calculation simple.
That's 10 to the 10th years.
If we will add that up, 80, 90, plus 16, that's 10 to the
106th nanoseconds in the history of the universe.
Multiply it times the number of atoms in the universe.
So, if all of the atoms in the universe were doing static
evaluations at nanosecond speeds since the beginning of
the Big Bang, we'd still be 14 orders of magnitudes short.
So, it'd be a pretty good cloud.
It would have to harness together lots of universes.
So, the British Museum algorithm is
not going to work.
No good.
So, what we're going to have to do is we're going to have
to put some things together and hope for the best.
So, the fifth way is the way we're actually going to do it.
And what we're going to do is we're going to look ahead, not
just one level, but as far as possible.
We consider, not only the situation that we've developed
here, but we'll try to push that out as far as we can and
look at these static values of the leaf nodes down here and
somehow use that as a way of playing the game.
So, that is number five.
And number four is going all the way down there.
And this, in the end, is all that we can do.
This idea is multiply invented most notably by Claude Shannon
and also by Alan Turing, who, I found out from a friend of
mine, spent a lot a lunch time conversations talking with
each other about how a computer might play chess
against the future when there would be computers.
So, Donald, Mickey and Alan Turing also invented this over
lunch while they were taking some time off from cracking
the German codes.
Well, what is the method?
I want to illustrate the method with the simplest
possible tree.
So, we're going to have a branching factor of 2 not 14.
And we're going to have a depth of 2 not something
highly serious.
Here's the game tree.
And there are going to be some numbers
down here at the bottom.
And these are going to be the value of the board from the
perspective of the player at the top.
Let us say that the player at the top would like to drive
the play as much as possible toward the big numbers.
So, we're going to call that player the maximizing player.
He would like to get over here to the 8, because that's the
biggest number.
There's another player, his opponent, which we'll call the
minimizing player.
And he's hoping that the play will go down to the board
situation that's as small as possible.
Because his view is the opposite of the maximizing
player, hence the name minimax.
But how does it work?
Do you see which way the play is going to go?
How do you decide which way the play is going to go?
Well, it's not obvious at a glance.
Do you see which way it's going to go?
It's not obvious to the glance.
But if we do more than a glance, if we look at the
situation from the perspective of the minimizing player here
at the middle level, it's pretty clear that if the
minimizing player finds himself in that situation,
he's going to choose to go that way.
And so the value of this situation, from the
perspective of the minimizing player, is 2.
He'd never go over there to the 7.
Similarly, if the minimizing player is over here with a
choice between going toward a 1 or toward an 8, he'll
obviously go toward a 1.
And so the value of that board situation, from the
perspective of the minimizing player, is 1.
Now, we've taken the scores down here at the bottom of the
tree, and we back them up one level.
And you see how we can just keep doing this?
Now the maximizing player can see that if he goes to the
left, he gets a score of 2.
If he goes to the right, he only gets a score of 1.
So, he's going to go to the left.
So, overall, then, the maximizing player is going to
have a 2 as the perceived value of that situation there
at the top.
That's the minimax algorithm.
It's very simple.
You go down to the bottom of the tree, you compute static
values, you back them up level by level, and then you decide
where to go.
And in this particular situation, the maximizer goes
to the left.
And the minimizer goes to the left, too, so the play ends up
here, far short of the 8 that the maximizer wanted and less
than the 1 that the minimizer wanted.
But this is an adversarial game.
You're competing with each other.
So, you don't expect to get what you want, right?
So, maybe we ought to see if we can make that work.
There's a game tree.
Do you see how it goes?
Let's see if the system can figure it out.
There it goes, crawling its way through the tree.
This is a branching factor of 2, just like our sample, but
now four levels.
You can see that it's got quite a lot of work to do.
That's 2 to the fourth, one, two, three, four, 2 to the
fourth, 16 static evaluations to do.
So, it found the answer.
But it's a lot of work.
We could get a new tree and restart it, maybe speed it up.
There is goes down that way, get a new tree.
Those are just random numbers.
So, each time it's going to find a different path through
the tree according to the numbers that it's generated.
Now, 16 isn't bad.
But if you get down there around 10 levels deep and your
branching factor is 14, well, we know those numbers get
pretty awful pretty bad, because the number of static
evaluations to do down there at the bottom
goes as b to the d.
It's exponential.
And time has shown, if you get down about seven or eight
levels, you're a jerk.
And if you get down about 15 or 16 levels, you beat the
world champion.
So, you'd like to get as far down in the tree as possible.
Because when you get as far down into the tree as
possible, what happens is as these that these crude
measures of bored quality begin to clarify.
And, in fact, when you get far enough, the only thing that
really counts is piece count, one of those features.
If you get far enough, piece count and a few other things
will give you a pretty good idea of what to do if you get
far enough.
But getting far enough can be a problem.
So, we want to do everything we can to
get as far as possible.
We want to pull out every trick we can find to get as
far as possible.
Now, you remember when we talked about branching down,
we knew that there were some things that we could do that
would cut off whole portions of the search tree.
So, what we'd like to do is find something analogous to
this world of games, so we cut off whole portions of this
search tree, so we don't have to look at
those static values.
What I want to do is I want to come back and redo this thing.
But this time, I'm going to compute the static
values one at a time.
I've got the same structure in the tree.
And just as before, I'm going to assume that the top player
wants to go toward the maximum values, and the next player
wants to go toward the minimum values.
But none of the static values have been computed yet.
So, I better start computing them.
That's the first one I find, 2.
Now, as soon as I see that 2, as soon as the minimizer sees
that 2, the minimizer knows that the value of this node
can't be any greater than 2.
Because he'll always choose to go down this way if this
branch produces a bigger number.
So, we can say that the minimizer is assured already
that the score there will be equal to or less than 2.
Now, we go over and compute the next number.
There's a 7.
Now, I know this is exactly equal to 2, because he'll
never go down toward a 7.
As soon as the minimizer says equal to 2, the maximizer
says, OK, I can do equal to or greater than 2.
One, minimizer says equal to or less than 1.
Now what?
Did you prepare those 2 numbers?
The maximizer knows that if he goes down here, he can't do
better than 1.
He already knows if he goes over here, he an get a 2.
It's as if this branch doesn't even exist.
Because the maximizer would never choose to go down there.
So, you have to see that.
This is the important essence of the notion the alpha-beta
algorithm, which is a layering on top of minimax that cuts
off large sections of the search tree.
So, one more time.
We've developed a situation so we know that the maximizer
gets a 2 going down to the left, and he sees that if he
goes down to the right, he can't do better than 1.
So, he says to himself, it's as if that branch doesn't
exist and the overall score is 2.
And it doesn't matter what that static value is.
It can be 8, as it was, it can be plus 1,000.
It doesn't matter.
It can be minus 1,000.
Or it could be plus infinity or minus infinity.
It doesn't matter, because the maximizer will always
go the other way.
So, that's the alpha-beta algorithm.
Can you guess why it's called the alpha-beta algorithm?
Well, because in the algorithm there are two parameters,
alpha and beta.
So, it's important to understand that alpha-beta is
not an alternative to minimax.
It's minimax with a flourish.
It's something layered on top like we layered things on top
of branch and bound to make it more efficient.
We layer stuff on top of minimax to
make it more efficient.
As you say to me, well, that's a pretty easy example.
And it is.
So, let's try a little bit more complex one.
This is just to see if I can do it without screwing up.
The reason I do one that's complex is not just to show
how tough I am in front of a large audience.
But, rather, there's certain points of interest that only
occur in a tree of depth four or greater.
That's the reason for this example.
But work with me and let's see if we can work
our way through it.
What I'm going to do is I'll circle the numbers that we
actually have to compute.
So, we actually have to compute 8.
As soon as we do that, the minimizer knows that that node
is going to have a score of equal to or less than 8
without looking at anything else.
Then, he looks at 7.
So, that's equal to 7.
Because the minimizer will clearly go to the right.
As soon as that is determined, then the maximizer knows that
the score here is equal to or greater than 8.
Now, we evaluate the 3.
The minimizer knows equal to or less than 3.
SPEAKER 4: [INAUDIBLE].
SPEAKER 1: Oh, sorry, the minimizer at 7, yeah.
OK, now what happens?
Well, let's see, the maximizer gets a 7 going that way.
He can't do better than 3 going that way, so we got
another one of these cut off situations.
It's as if this branch doesn't even exist.
So, this static evaluation need not be made.
And now we know that that's not merely equal to or greater
than 7, but exactly equal to 7.
And we can push that number back up.
That becomes equal to or less than 7.
OK, are you with me so far?
Let's get over to the other side of the tree
as quickly as possible.
So, there's a 9, equal to or less than 9, 8 equal to 8,
push the 8 up equal or greater than 8.
The minimizer can go down this way and get a 7.
He'll certainly never go that way where the
maximizer can get an 8.
Once again, we've got a cut off.
And if this branch didn't exist, then that means that
these static evaluations don't have to be made.
And this value is now exactly 7.
But there's one more thing to note here.
And that is that not only do
…