6. Search Games; Minimax; and Alpha-Beta Video Lecture - Artificial Intelligence

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
we not have to make these
static evaluations down here,
but we don't even have to
generate these moves.
So, we save two ways, both on
static evaluation and on move
generation.
This is a real winner, this
alpha-beta thing, because it
saves as enormous amount
of computation.
Well, we're on the way now.
The maximizer up here is
guaranteed equal to or
greater than 7.
Has anyone found the winning
media move yet?
Is it to the left?
I know that we better keep
going, because we want to
trust any oracles.
So, let's see.
There's a 1.
We've calculated that.
The minimizer can be guaranteed
equal to or less
than 1 at that particular
point.
Think about that for a while.
At the top, the maximizer
knows he can go
left and get a 7.
the minimizer, if the play ever
gets here, can ensure
that he's going to drive the
situation to a board
number that's 1.
So, the question is will
the maximizer ever
permit that to happen?
And the answer is surely not.
So, over here in the development
of this side of
the tree, we're always comparing
numbers at adjacent
levels in the tree.
But here's a situation where
we're comparing numbers that
are separated from each
other in the tree.
And we still concluded that no
further examination of this
node makes any sense at all.
This is called deep cut off.
And that means that this whole
branch here might as well not
exist, and we won't have to
compute that static value.
All right?
So, it looks--
you have this stare of
disbelief, which
is perfectly normal.
I have to reconvince myself
every time that
this actually works.
But when you think your way
through it, it is clear that
these computations that
I've x-ed out
don't have to be made.
So, let's carry on and see if we
can complete this equal to
or less than 8, equal
to 8, equal to 8--
because the other branch
doesn't even exist--
equal to or less than 8.
And we compare these two
numbers, do we keep going?
Yes, we keep going.
Because maybe the maximizer
can go to the right and
actually get to that 8.
So, we have to go over here
and keep working away.
There's a nine, equal
to or less than 9,
another 9 equal to 9.
Push that number up equal
to or greater than 9.
The minimizer gets an
8 going this way.
The maximizer is insured of
getting a 9 going that way.
So, once again, we've got
a cut off situation.
It's as if this doesn't exist.
Those static evaluations
are not made.
This move generation is not made
and computation is saved.
So, let's see if we can do
better on this very example
using this alpha-beta idea.
I'll slow it down a little bit
and change the search type to
minimax with alpha-beta.
We see two numbers on each of
those nodes now, guess what
they're called.
We already know.
They're alpha and beta.
So, what's going to happen is
the algorithm proceeds through
trees that those numbers are
going to shrink wrap
themselves around
the situation.
So, we'll start that up.
Two static evaluations
were not made.
Let's try a new tree.
Two different ones
were not made.
A new tree, still again, two
different ones not made.
Let's see what happens when we
use the classroom example, the
one I did up there.
Let's make sure that I
didn't screw it up.
I'll slow that down to 1.
2, same answer.
So, you probably didn't realize
it at the start.
Who could?
In fact, the play goes down that
way, over this way, down
that way, and ultimately to
the 8, which is not the
biggest number.
And it's not the smallest
number.
It's the compromised number
that's arrived at virtue of
the fact that this is an
adversarial situation.
So, you say to me, how much
energy, how much work do you
actually saved by doing this?
Well, it is the case that in
the optimal situation, if
everything is ordered right,
if God has come down and
arranged your tree in just
the right way, then the
approximate amount of work you
need to do, the approximate
number of static evaluations
performed, is approximately
equal to 2 times b
to the d over 2.
We don't care about this 2.
We care a whole lot
about that 2.
That's the amount of
work that's done.
It's b to the d over 2,
instead of b to d.
What's that mean?
Suppose that without
this idea, I can
go down seven levels.
How far can I go down
with this idea?
14 levels.
So, it's the difference
between a
jerk and a world champion.
So, that, however, is only in
the optimal case when God has
arranged things just right.
But in practical situations,
practical game situations, it
appears to be the case,
experimentally, that the
actual number is close to this
approximation for optimal
arrangements.
So, you'd never not want
to use alpha-beta.
It saves an amazing
amount of time.
You could look at
it another way.
Suppose you go down the same
number of levels, how much
less work do you have to do?
Well, quite a bit.
The square root [INAUDIBLE],
right?
That's another way of looking
at how it works.
So, we could go home at this
point except for one problem,
and that is that we pretended
that the branching factor is
always the same.
But, in fact, the branching
factor will vary with the game
state and will vary
with the game.
So, you can calculate how much
computing you can do in two
minutes, or however much time
you have for an average move.
And then you could say,
how deep can I go?
And you won't know for
sure, because it
depends on the game.
So, in the earlier days of
game-playing programs, the
game-playing program left a
lot of computation on the
table, because it would make a
decision in three seconds.
And it might have made a much
different move if it used all
the competition it
had available.
Alternatively, it might be
grinding away, and after two
minutes was consumed.
It had no move and just
did something random.
That's not very good.
But that's what the early
game-playing program's did,
because no one knew how
deep they could go.
So, let's have a look at the
situation here and say, well,
here's a game tree.
It's a binary game tree.
That's level 0.
That's level 1.
This is level d minus 1.
And this is level d.
So, down here you
have a situation
that looks like this.
And I left all the game
tree out in between .
So, how many leaf nodes
are there down here?
b to the d, right?
Oh, I'm going to forget about
alpha alpha-beta for a moment.
As we did when we looked at
some of those optimal
searches, we're going to add
these things one at a time.
So, forget about alpha-beta,
assume we're just doing
straight minimax.
In that case, we would have to
calculate all the static
values down here
at the bottom.
And there are b to d of those.
How many are there at
this next level up?
Well, that must be b
to the d minus 1.
How many fewer nodes are there
at the second to the last, the
penultimate level, relative
to the final level?
Well, 1 over b, right?
So, if I'm concerned about not
getting all the way through
these calculations at the d
level, I can give myself an
insurance policy by calculating
out what the
answer would be if I only went
down to the d minus 1th level.
Do you get that insurance
policy?
Let's say the branching factor
is 10, how much does that
insurance policy cost me?
10% of my competition.
Because I can do this
calculation and have a move in
hand here at level d minus 1 for
only 1/10 of the amount of
the computation that's required
to figure out what I
would do if I go all the way
down to the base level.
OK, is that clear?
So this idea is extremely
important in its general form.
But we haven't quite got there
yet, because what if the
branching factor turns out to be
really big and we can't get
through this level either?
What should we do to
make sure that we
still have a good move?
SPEAKER 5: [INAUDIBLE].
SPEAKER 1: Right, we can do
it at the b minus 2 level.
So, that would be up here.
And at that level, the amount
of computation would be b to
the d minus 2.
So, now we've added 10%
plus 10% of that.
And our knee jerk is begin
to form, right?
What are we going to do in the
end to make sure that no
matter what we've got a move?
CHRISTOPHER: Start from
the very first--
SPEAKER 1: Correct, what's
that, Christopher?
CHRISTOPHER: Start from
the very first level?
SPEAKER 1: Start from the very
first level and give our self
an insurance policy for every
level we try to calculate.
But that might be real costly.
So, we better figure out if this
is going to be too big of
an expense to bear.
So, let's see, if we do what
Christopher suggests, then the
amount of computation we need
in our insurance policy is
going to be equal 1--
we're going to do it up here at
this level, 2, even though
we don't need it, just to make
everything work out easy.
1 plus b, that's getting or
insurance policy down here at
this first level.
And we're going to add b squared
all the way down to b
to d minus 1.
That's how much we're going to
spend getting an insurance
policy at every level.
I wished that some of that high
school algebra, right?
Let's just do it for fun.
Oh, unfortunate choice
of variable names.
bs is equal to--
oh, we're going to multiply
all those by b.
Now, we'll subtract the first
one from the second one, which
tells us that the amount of
calculation needed for our
insurance policy is equal
to b to the d minus 1
over b minus 1.
Is that a big number?
We could do a little algebra on
that and say that b to the
d is a huge number.
So, that minus one
doesn't count.
And B is probably 10 to 15.
So, b minus 1 is, essentially,
equal to b.
So, that's approximately equal
b to the d minus 1.
So, with an approximation
factored in, the amount of
computation needed to do
insurance policies at every
level is not much different from
the amount of computation
needed to get an insurance
policy at just one level, the
penultimate one.
So, this idea is called
progressive deepening.
And now we can visit our gold
star idea list and see how
these things match
up with that.
First of all, the dead horse
principle comes to the fore
when we talk about alpha-beta.
Because we know with alpha-beta
that we can get rid
of a whole lot of the tree and
not do static evaluation, not
even do move generation.
That's the dead horse we
don't want to beat.
There's no point in doing that
calculation, because it can't
figure into the answer.
The development of the
progressive deepening idea, I
like to think of in terms of
the martial arts principle,
we're using the enemy's
characteristics against them.
Because of this exponential
blow-up, we have exactly the
right characteristics to have
a move available at every
level as an insurance policy
against not getting through to
the next level.
And, finally, this whole idea
of progressive deepening can
be viewed as a prime example
of what we like to call
anytime algorithms that always
have an answer ready to go as
soon as an answer is demanded.
So, as soon as that clock runs
out at two minutes, some
answer is available.
It'll be the best one that the
system can compute in the time
available given the
characteristics of the game
tree as it's developed so far.
So, there are other kinds
of anytime algorithms.
This is an example of one.
That's how all game playing
programs work, minimax, plus
alpha-beta, plus progressive
deepening.
Christopher, is alpha-beta
a alternative to minimax?
CHRISTOPHER: No.
SPEAKER 1: No, it's not.
It's something you layer
on top of minimax.
Does alpha-beta give you a
different answer from minimax?
CHRISTOPHER: No.
No, it doesn't.
SPEAKER 1: Let's see everybody
shake their head
one way or the other.
It does not give you an answer
different from minimax.
That's right.
It gives you exactly
the same answer,
not a different answer.
It's a speed-up.
It's not an approximation.
It's a speed-up.
It cuts off lots of the tree.
It's a dead horse principle
at work.
You got a question,
Christopher?
CHRISTOPHER: Yeah, since all
of the lines progressively
[INAUDIBLE], is it possible to
keep a temporary value if the
value [INAUDIBLE] each node of
the tree and then [INAUDIBLE]?
SPEAKER 1: Oh, excellent
suggestion.
In fact, Christopher
has just--
I think, if I can jump ahead
a couple steps--
Christopher has reinvented
a very important idea.
Progressive deepening not only
ensures you have an answer at
any time, it actually improves
the performance of alpha-beta
when you layer alpha-beta
on top of it.
Because these values that are
calculated at intermediate
parts of the tree are used to
reorder the nodes under the
tree so as to give you maximum
alpha-beta cut-off.
I think that's what you
said, Christopher.
But if it isn't, we'll talk
about your idea after class.
So, this is what every game
playing program does.
How is Deep Blue different?
Not much.
So, Deep Blue, as of 1997, did
about 200 million static
evaluations per second.
And it went down, using
alpha-beta,
about 14, 15, 16 levels.
So, Deep Blue was minimax,
plus alpha-beta, plus
progressive deepening, plus
a whole lot of parallel
computing, plus an opening book,
plus special purpose
stuff for the end game, plus--
perhaps the most important
thing--
uneven tree development.
So far, we've pretended that the
tree always goes up in an
even way to a fixed level.
But there's no particular reason
why that has to be so.
Some situation down at the
bottom of the tree may be
particularly dynamic.
In the very next move, you might
be able to capture the
opponent's Queen.
So, in circumstances like that,
you want to blow out a
little extra search.
So, eventually, you get to
the idea that there's no
particular reason to
have the search go
down to a fixed level.
But, instead, you can develop
the tree in a way that gives
you the most confidence
that your
backed-up numbers are correct.
That's the most important of
these extra flourishes added
by Deep Blue when it beat
Kasparov in 1997.
And now we can come back
and say, well, you
understand Deep Blue.
But is this a model of
anything that goes
on in our own heads?
Is this a model of any kind
of human intelligence?
Or is it a different kind
of intelligence?
And the answer is
mixed, right?
Because we are often in
situations where we are
playing a game.
We're competing with another
manufacturer.
We have to think what the other
manufacturer will do in
response to what we do
down several levels.
On the other hand, is going
down 14 levels what human
chess players do when they win
the world championship?
It doesn't seem, even to them,
like that's even a remote
possibility.
They have to do something
different, because they don't
have that kind of computational
horsepower.
This is doing computation in the
same way that a bulldozer
processes gravel.
It's substituting raw power
for sophistication.
So, when a human chess master
plays the game, they have a
great deal of chess knowledge
in their head and they
recognize patterns.
There are famous experiments,
by the way, that demonstrate
this in the following way.
Show a chessboard to a chess
master and ask them to
memorize it.
They're very good at that, as
long as it's a legitimate
chessboard.
If the pieces are placed
randomly, they're no
good at it at all.
So, it's very clear that they've
developed a repertoire
of chess knowledge that makes
it possible for them to
recognize situations and play
the game much more like number
1 up there.
So, Deep Blue is manifesting
some kind of intelligence.
But it's not our intelligence.
It's bulldozer intelligence.
So, it's important to understand
that kind of
intelligence, too.
But it's not necessarily the
same kind of intelligence that
we have in our own head.
So, that concludes what we're
going to do today.
And, as you know, on Wednesday
we have a celebration of
learning, which is familiar to
you if you take a 309.1.
And, therefore, I will
see you on Wednesday,
all of you, I imagine.