
Korean: 
1963년에 여기 MIT의 유명한 철학자였던
휴버트 드레이퍼스는
글을 썼는데 그 글의 제목은
"컴퓨터는 체스를 할 수 없다"였습니다
그리고 그는 후에 인공지능 연구실의
그린블랫 체스 기계를 
써보도록 초대되었죠
물론 그는 졌습니다
그리고 세이머 페빗은 
드레이퍼스의 글을 반박하는
"드레이퍼스도 체스를 
할 수 없다"라는 글을 적었죠

English: 
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."

English: 
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

Korean: 
하지만 드레이퍼스가
“아직 컴퓨터는 사람과 같은 방법으로
체스를 할 수 없다”라고 했다면
그의 말이 맞았을지도 모릅니다
1968년 데이빗 레비라는 체스마스터는
인공지능의 창시자 존 매카시에게
10년 안에는 컴퓨터가 세계 챔피언을
이길 수 없을 거라 했습니다
그리고 5년 후 매카시는 포기했습니다
그가 원했던 것처럼 컴퓨터가
사람이 하는 방법으로 체스를 해서
이기게 할 수 없다는 
것을 깨달았기 때문입니다
하지만 20년 후 1997년에
딥 블루(Deep Blue)가 
세계 챔피언을 이기면서
체스에 대한 관심은 사그라들었습니다
그래도 오늘 우리는 게임을 다룰 것입니다

Korean: 
게임 속에는 우리의 사고과정을
모델링하는 요소가 있기 때문입니다
만약 사고과정을 모델링하는 것이 아니라면
어떤 지능같은 것을 모델링하는 것이겠죠
만약 지능이란 
무엇인지 제대로 알고 싶다면
이런 종류의 지능도
이해해야 합니다
우선 체스 프로그램을
어떻게 디자인할 수 있을지
생각해보며 시작할 겁니다
그리고 딥 블루는 엄청난 속도 외에
어떤 요소가 더해진 것인지 
이야기하며 마무리할 겁니다
이게 오늘의 계획입니다
수업이 끝날 때쯤 여러분은 원한다면
직접 딥 블루를 만들 수 있을 정도로
이해하게 될 겁니다
우선 컴퓨터가 어떻게 체스를
할 수 있을지 얘기해봅시다
여러 가지 가능한 접근 방식을
탐구해봅시다
첫 번째 접근은 
컴퓨터가 인간이 하는 듯
체스 보드를 깊이 이해하는 겁니다
체스 폰(Pawn)의 배치와 킹이 안전한지

English: 
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

English: 
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.

Korean: 
캐슬링(Castling)을 해도 
되는지 등 말입니다
분석을 하고 전략을 세우는 겁니다
여러 전술도 동원하겠죠
이것이 모두 섞여서
어떤 움직임을 뽑아내는 겁니다
만약 이 노드를 게임 보드라 한다면
다음 움직임은 저런 
과정으로 결정될 것입니다
문제는 이걸 아무도 
해내지 못했다는 겁니다
이런 의미에서 드레이퍼스는 맞았죠
오늘날의 어떤 게임 프로그램도
이런 식으로 돌아가지 않습니다
어떻게 하는지 아직
아무도 모르기 때문에
배울 수 없어요
하지만 다른 시도를 해볼 수 있습니다
예를 들면, 조건문(IF-THEN RULES)을
쓸 수 있습니다
어떻게 할까요?
이렇게 합니다

English: 
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.

Korean: 
이 노드가 체스 보드라고 했을 때
만약 퀸의 폰을 앞으로 한 칸
움직일 수 있다면
움직이면 됩니다
보드 상황을 분석하거나
이런저런 시도를 하지 않고
그저 보드를 보고
다음 이동을 선택하는 것입니다
다음과 같은 상황에서
이 접근 방법을 쓸 수 있습니다
이런 상황이 있고
이게 가능한 이동입니다
어떤 조건문에 따라
이중 하나가 선택되는 겁니다
이렇게는 절대 막강한 플레이어를
만들 수 없습니다
흥미롭게도 이 방법으로 꽤 괜찮은
체커스 프로그램을 
만든 사람은 있습니다
현재 보드에서 어떤 
이동을 할 수 있는지 보고
순위를 매겨
가장 높은 것을 선택합니다
하지만 좋은 접근은 아닙니다
강력하지 않아요

English: 
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.

Korean: 
이런 접근법으로는
막강한 체스 프로그램을 만들 방법이
도저히 떠오르지 않네요
세 번째 접근 방법은
앞을 내다보며 이를 평가하는 것입니다
무슨 말이냐면
모든 이동에 대해 가능한 결과를 보고
이 중 어떤 것이 가장 좋은지 봅니다
그러니까 여기에 있다고 했을 때
이 셋 중 어떤 게 가장 좋은지 봅니다
이를 위해서 각각 상황이
얼마나 좋은지를 
평가할 수 있어야 합니다
잠시 다른 얘기로 넘어가서
이런 평가를 하는데 
흔히 쓰이는 방법들을
간략히 다뤄보겠습니다

Korean: 
체스 보드에는 
여러 특징이 있을 겁니다
이를 f1, f2, ... 이라고 하고
이들에 대한 함수를 만들어
이 함수의 해를 
정적 가치(static value)라고 합니다
정적인 이유는 앞으로 
일어날 수 있는 상황을
분석하는 것이 아니라
그저 보드의 현재 상태를 보고
킹의 안전과 
폰의 배치를 보기 때문입니다
이는 각각 숫자로 표현되어
함수에 넣으면 어떤 값이 나옵니다
이 값이 여러분의 입장에서 봤을 때의
현재 보드의 가치인 겁니다
일반적으로 이 g라는 함수는
선형 다항식으로 간추려집니다
결과적으로 이 정적 가치를 계산하는
가장 대표적인 방법은

English: 
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.

Korean: 
(c1 x f1) + (c2 x f2) + ... 와
같이 더해 나아가는 것입니다
이를 선형 평가 다항식
(linear scoring polynomial)이라 합니다
이 함수를 통해 어떤 값들을 구하고
그중 가장 큰 것을 선택합니다
이렇게 게임을 해나갈 수 있겠죠
사실 이 평가 다항식은
필요 이상입니다
우리는 그저 저 세 상황 중
어떤 것이 가장 좋은지만 알면 됩니다
순위는 필요 없습니다
값을 알 필요도 없습니다
어떤 것이 가장 좋은지만 알면 됩니다
이를 아는 방법 중 하나가
선형 평가 다항식인 겁니다
이 방법만 있는 건 아닙니다
어쨌든 이게 두 번째와
세 번째 접근이었습니다
또 어떻게 해볼 수 있을까요?

English: 
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?

English: 
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.

Korean: 
지금까지 배운 검색 방법을 생각해보면
우리가 늘 기준점으로 삼았던
아무런 지능도 사용하지 않는
검색 방법이 뭐였나요?
영국박물관 알고리즘을 써서
트리 전체를 분석할 수도 있습니다
나와 상대방이 계속 
반복적으로 이동하면
총 몇 번이나 할까요?
100번 아니면 50번 정도?
상대방도 50번
나도 50번 이동하는 겁니다
이게 좋은 방법인지 판단하기 전에
우선 용어 정리를
하는 게 좋을 듯합니다
여기 가능한 이동을
담은 트리가 있습니다

Korean: 
각 단계에서 몇 가지
선택지가 있을 겁니다
그리고 여러 단계로 이루어질 겁니다
이를 나타내는 표준 용어는
분기 계수(branching factor)입니다
이 상황에서 b는 3입니다
이것은 트리의 깊이(depth)입니다
여기서 d는 2입니다
이 두 값을 통해 트리의
단말 노드의 개수를 알 수 있어요
여기서는 몇 개인가요?
간단한 계산이죠
b의 d승입니다
크리스토퍼, b의 d승이 맞나요?

English: 
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?

Korean: 
여기서 b의 d승은 1이고
이 단계에서 b의 d승은 b이고
이 단계에서 b의 
d승은 b의 제곱입니다
따라서 이 트리의 
b의 d승은 9입니다
이제 이런 용어를 사용해서
과연 영국박물관 
알고리즘을 쓰는 게 합리적인지
체스는 더 이상 생각하지 
않아도 되는지 알 수 있어요
자 봅시다
트리의 깊이는 굉장히 깊어질 겁니다
체스 경기에서 한 사람이 어림잡아
평균 50번 움직인다고 하면
d는 100 정도 됩니다
체스의 분기 계수를 생각해보면
물론 게임의 진행 
상황에 따라 달라지겠지만
평균적으로 14나 15 정도입니다
그냥 10이라고 두면 
10의 100승이 됩니다

English: 
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.

Korean: 
하지만 10은 넘으니
실제는 이보다 더 클 겁니다
결과적으로 클로드 섀넌에 따르면
총 10의 120승 개의 
단말 노드가 있습니다
만약 영국박물관 알고리즘을 쓴다면
총 10의 120승 개의
단말 노드를 정적 분석을 해야 합니다
위에 있을 때 어떤 이동이
가장 좋은지 알기 위해서요
합리적인 것 같나요?
이전에는 실현 불가능해 보였어요
전에는 불가능했겠지만
이제 클라우드 컴퓨팅 같은 것을
쓰면 가능할 수도 있어요
버네사, 어떻게 생각해요?
클라우드에 컴퓨터가 
충분하다면 할 수 있을까요?
잘 모르겠나요?
직접 계산해볼까요?

English: 
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?

Korean: 
한번 해봅시다
여러분이 도움이 필요합니다
특히 여러분 중 우주론을 
공부하는 사람이 있다면요
첫 번째로 우주에 원자가
몇 개나 있는지 알아봅시다
말할 사람?
10의 몇 승?
학생1: 38승?
아니죠 10의 38승을 말했는데
그건 너무 적고
제가 마지막으로 봤을 때는
10의 80승 정도였습니다
우주의 원자 개수 말입니다
다음에 알고 싶은 것은
일 년은 총 몇 초일까요?
외워두기 좋은 숫자죠
파이(pi) 곱하기 10의 7승 정도입니다
일초는 몇 나노초인가요?

English: 
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?

English: 
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

Korean: 
10의 9승입니다
마지막으로 우주의 역사는
얼마나 되었나요?
학생: 147억 년이요
100억 몇이라고 얘기하네요
140억 정도?
계산을 위해서 100억이라고 해둡시다
그럼 10의 10승 년입니다
이를 모두 더하면
10의 106승의 나노초가 우주의 역사입니다
이를 우주의 원자 개수로 곱하니
만약 우주에 있는 
모든 원자가 빅뱅 때부터

Korean: 
나노초의 단위 속도로 
정적 분석을 하고 있었다 해도
아직 10의 14승이 모자랍니다
우리가 쓰는 클라우드는
여러 우주를 합쳐 써야 할 겁니다
따라서 영국박물관 알고리즘은
사용할 수 없습니다
쓸모없습니다
이제 우리가 해야 할 것은
여러 방법을 합쳐서 
최선을 다해야 합니다
다섯 번째 방법이 
실제로 우리가 다룰 방법인데
무엇이냐면 다음 단계만이 아니라
가능한 한 멀리 앞을 내다보는 겁니다

English: 
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.

Korean: 
여기 있는 상황만 따지는 것이 아니라
최대한 깊이 내려가서
여기 밑에 있는 
단말 노드의 정적 가치를 보고
이를 사용해서 게임을 하는 겁니다
이게 다섯 번째 방법입니다
네 번째는 밑에 모든 걸 봤었죠
하지만 결국 우리가 
할 수 있는 건 이 다섯 번째입니다
이 방법은 여러 명이 생각해냈는데
클로드 섀넌이 가장 유명하지만
제 친구에게 들은 바로는, 앨런 튜링도
함께 점심시간마다 어떻게

English: 
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

English: 
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.

Korean: 
컴퓨터가 미래에 체스를 
할 수 있을지 얘기를 했었다고 합니다
그렇게 도널드 미치와 앨런 튜링은
독일군 암호를 해독할 때 
잠시 쉬는 동안 점심을 먹으며
이 방법을 생각해냈죠
이 방법이 대체 뭘까요?
가장 단순한 트리를 가지고
설명해 보겠습니다
분기 계수가 14가 아닌 2이고
그리고 깊이도 간단하게 2로 해봅시다
여기 게임 트리가 있어요
여기 밑에는
어떤 값들이 있겠죠
이 값들은, 선수 입장에서 위에서
내려다볼 때의 보드 가치입니다
선수는 가장 큰 값을 향해가며
게임을 하고 싶다고 가정해봅시다
이 선수를 최대지향 선수
(maximizing player)라고 부릅시다

Korean: 
그는 여기 8로 가고 싶습니다
가장 큰 값이니까요
이 선수의 상대는
최소지향 선수(minimizing player)입니다
그가 원하는 것은 경기가
가장 작은 값으로 가기를 바랍니다
최대지향 선수와
반대되는 입장이니까요
이런 걸 미니맥스(minimax)라고도 하죠
그래서 어떻게 되는 걸까요?
어떤 식으로 
게임이 진행될지 보이나요?
대결이 어떻게 
될지 어떻게 판단할까요?
한눈에 봐서는 알기 어렵죠
어떻게 될지 알 것 같나요?
한눈에 봐서는 어렵죠
하지만 더 깊이 들여다보면
즉 최소지향 선수의 입장에서
여기 중간 단계의 상황을 보면
만약 이 선수가 여기에 있다면
왼쪽으로 갈 것이라는 건 알 수 있죠
따라서 최소지향 선수의 입장에서

English: 
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

Korean: 
이 상황의 가치는 2입니다
절대 여기 7로 가지 않을 겁니다
마찬가지로 만약 최소지향 선수가
여기 1과 8의 선택지에 놓인다면
당연히 1로 갈 것입니다
따라서 최소지향 선수에게
이 보드 상황의 가치는 1입니다
우리는 지금 가장 밑에 있는 값을
한 단계 위로 끌고 왔어요
이를 계속해나가면 되겠죠?
최대지향 선수의 입장에서는
여기서 왼쪽으로 가면 2이고
오른쪽으로 가면 1이니
왼쪽으로 갈 것입니다
종합적으로 최대지향 선수의 입장에서
여기 꼭대기 상황의 가치는 2입니다
이게 미니맥스 알고리즘입니다
매우 간단하죠
트리의 가장 밑으로 가서
정적 가치를 모두 계산하고
한 단계 한 단계 위로 끌어오고

English: 
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

English: 
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.

Korean: 
다음 이동을 결정합니다
이 상황에서
최대지향 선수는 왼쪽으로 갑니다
최소지향 선수도 왼쪽으로 가고
게임은 여기서 끝이 납니다
최대지향 선수가 
원했던 8보다는 훨씬 작고
최소지향 선수가 원했던 1보다는 크죠
하지만 이는 대결입니다
서로 경쟁하는 것이죠
따라서 원하는 대로 얻을 수는 없겠죠?
실제로 이걸 돌려보면 되는지 봅시다
게임 트리입니다
어떻게 되는지 보이나요?
프로그램이 할 수 있는지 봅시다
여기 트리 위를 돌아다니고 있네요
우리가 봤던 예시처럼 
분기 계수는 2이지만
깊이는 4입니다
생각보다 할 일이 많아지죠
2의 4승 개의 단말노드입니다

English: 
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.

Korean: 
하나, 둘, 셋, 넷
총 16개의 정적 분석을 합니다
답을 찾았습니다
하지만 많은 일을 했죠
새로운 트리를 만들고 
이번엔 속도를 높여봅시다
빠르게 계산하네요
새로운 트리를 만듭시다
임의의 숫자로 채워지고
매번 채워진 숫자들에 따라
트리에서 새로운 결과를 냅니다
16은 아주 크지 않아요
하지만 10단계쯤 내려가고
분기 계수가 14쯤 되면
심각할 정도로 많아집니다
정적 분석을 해야 하는
단말 노드의 개수는
b의 d승 개가 되니까요
기하급수적이죠
7 혹은 8단계만 내려가도
충분히 엄청난 겁니다
만약 15단계 이상 내려가면
세계 챔피언도 이길 수 있겠죠
가능한 한 깊이 
내려가는 것이 좋습니다

English: 
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.

Korean: 
깊이 내려가면 내려갈수록
이 불확실했던 값들이
점점 더 분명해지기 때문입니다
사실 충분히 밑으로 가면
노드의 개수만 보면 됩니다
만약 충분히 내려간다면
노드의 개수와 몇 가지 다른 정보로
다음 이동을 쉽게 정할 수 있습니다
하지만 깊이 내려가는 건 쉽지 않습니다
우리는 깊이 가도록
최선을 다할 겁니다
가능한 모든 방법을 총동원해서
내려가고 싶습니다
전에 분기 한정법을 다뤘을 때
우리는 탐색하는 트리의
큰 부분을 때서 없앴습니다
우리는 이와 비슷한 방법을
게임에 적용해 검색 트리의
일부분을 잘라버리고 모든 값을
계산하지 않았으면 좋겠습니다
다시 돌아와 아까 한 걸 반복할 텐데
대신 이번에는 정적 가치를
하나씩 계산해봅시다

Korean: 
똑같은 트리로 시작합니다
아까와 같이 꼭대기 선수는
최대지향 선수이고 그다음 선수는
최소지향 선수라 가정해봅시다
하지만 아직 정적 가치는 
하나도 계산하지 않았습니다
이제 시작해봅시다
가장 먼저 2를 찾았습니다
이 2를 보자마자 최소지향 선수는
이 바로 위 노드의 가치가 2 이상이
될 수 없다는 것을 압니다
만약 다른 가지의 값이 더 크다면
무조건 왼쪽으로 갈 테니까요
따라서 최소지향 선수는
여기 가치는 2 이하라는 걸 압니다
이제 다음 값을 계산합니다
7이네요
이제 이 위 노드는 확실히 2입니다
절대 7로 가지 않을 테니까요
최소지향 선수가 2를 확정하는 순간
최대지향 선수는 여기가 
2 이상이라 확정할 수 있습니다

English: 
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.

English: 
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.

Korean: 
1이면 최소지향 선수는 
이 위가 1 이하인 걸 압니다
그다음엔 뭐죠?
저 두 값을 비교할까요?
최대지향 선수는 오른쪽으로 가면
커봤자 1이라는 걸 압니다
왼쪽으로 가면 2라는 것도 압니다
오른쪽 가지는 취급하지 않는 겁니다
최대지향 선수는 절대 
이쪽으로 가지 않을 테니까요
이걸 이해해야 합니다
이는 미니맥스 알고리즘 위에 추가하는
알파-베타(alpha-beta)
알고리즘의 중요한 개념입니다
트리의 상당한 부분을 자르게 해주죠
다시 정리해보면
지금 이 상황에서 최대지향 선수는
왼쪽으로 가면 2라는 것을 알고
오른쪽으로 가면 
최대 1이라는 걸 압니다

English: 
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.

Korean: 
따라서 이 가지는 없다고 생각하고
최종 점수는 2라고 결론을 냅니다
여기의 정적 가치는 전혀 상관이 없죠
아까처럼 8이어도 되고
1000이어도 상관이 없어요
-1000이어도 됩니다
아니면 무한대도 상관없습니다
왜냐하면 최대지향 선수는
항상 반대로 갈 테니까요
이게 알파-베타 알고리즘입니다
왜 알파-베타 알고리즘이라 불릴까요?
매개 변수가 두 개 있기 때문이죠
알파와 베타요
이 방법은 미니맥스 알고리즘과
다른 알고리즘이 아니고
미니맥스에 기능을 추가한 것입니다
위에 한 층 더한 거죠
분기 한정법에 방법을 추가해
효율성을 높였던 것처럼
미니맥스 알고리즘에 추가해
더 효율적으로 만드는 것입니다
지금까지는 정말 간단한 예시였습니다

English: 
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

Korean: 
좀 더 복잡한 예시를 봅시다
중간에 망치지 않게 미리 준비했습니다
이렇게 복잡한 예시를 보는 이유는
여러분한테 잘난척하기 위해서가 아니고
깊이가 4 이상인 트리에서만 보이는
흥미로운 점이 있기 때문입니다
그래서 이 예시를 보는 겁니다
저와 함께 이 트리를
따라가 봅시다
우리가 실제로 계산해야 하는
숫자들에 동그라미를 칠 겁니다
이 8은 실제로 계산해야 합니다
이걸 계산하면 최소지향 선수는
위 노드는 최대 8이라는 것을
다른 걸 보지 않아도 알 수 있습니다
그리고 그는 7을 봅니다
그러면 여기는 7이 됩니다
최소지향 선수는 
오른쪽으로 갈 테니까요
이게 정해지면 최대지향 선수는

English: 
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,

Korean: 
이 노드가 8 이상이라는 걸 압니다
이제 여기 3을 계산합니다
최소지향 선수는 여기가
최대 3이라는 걸 알게 됩니다
미안해요 여기는 7이네요
자 다음은 어떻게 되나요?
최대지향 선수는 이쪽으로 가면 7이고
왼쪽으로 가면 잘해봐야 3이니
가지를 잘라버릴 수 있는 상황입니다
이 가지는 없다고 생각해도 되겠죠
따라서 이 값은 
계산하지 않아도 됩니다
그렇게 되면 여기는 최소 7이 아니라
정확히 7이라는 걸 알고
이 값을 가지고 올라갈 수 있어요
그러면 여기가 최대 7이 되네요
지금까지 따라오고 있나요?
빠르게 트리를 모두
채워봅시다
여기가 9면 위는 최대 9이고

Korean: 
8이니까 위도 8이 되고 
또 위로 올리면 최소 8입니다
최소지향 선수는 
왼쪽으로 내려가면 7이니
오른쪽으로 가지 않습니다
최대지향 선수가 
8이 될 수도 있으니까요
이번에도 가지를 자를 수 있습니다
여기 가지가 원래부터 없었던 듯이
이 밑에 값들은 계산할 필요가 없겠죠
그리고 여기는 정확히 7이 됩니다
여기서 중요한 또 한 가지 포인트는
단순히 이 값들을 
계산 안 해도 될 뿐만 아니라
이 움직임 자체를 
고려하지 않아도 됩니다
두 번 절약하는 거죠
정적 가치 계산과 
이동 연산 모두 필요 없어요
알파-베타 알고리즘은 정말 우수하죠
연산량을 엄청나게 절약하니까요
거의 다 해갑니다
꼭대기의 최대지향 선수는
최소 7이라는 걸 압니다
혹시 답을 이미 알아낸 사람이 있나요?
왼쪽으로 가나요?
아직은 계속해봐야 합니다

English: 
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

English: 
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.

Korean: 
우리는 아무 신탁도 믿지 않으니까요
자 봅시다
여기 1은 계산합니다
최소지향 선수는 여기서
최대 1이라는 걸 알 수 있습니다
잠시 생각해봅시다
꼭대기에 있는 
최대지향 선수는 왼쪽으로 가면
7이라는 것을 압니다
최소지향 선수는 여기까지 온다면
가능하다면 여기 1로
상황을 몰아갈 것입니다
최대지향 선수가 이렇게 되게
가만히 있을까요?
당연히 그럴 리 없죠
트리의 왼쪽을 볼 때
우리는 계속 전후 단계의 값과
비교했었습니다
하지만 여기 오른쪽에서는
서로 멀리 떨어진 값들을 비교합니다
하지만 그래도 나머지 노드를
볼 필요가 없다는 걸 알 수 있습니다

English: 
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.

Korean: 
이를 깊은 가지치기(deep cutoff)라고 하죠
무슨 의미냐면 이 전체 가지는
원래 없었다 생각하고 
계산하지 않는다는 겁니다
알겠나요?
뭔가 미심쩍은 눈빛을 하고 있는데
충분히 그럴 수 있어요
저도 이게 실제로 된다는 게
여러 번 생각해야 납득되거든요
하지만 차례차례 생각해보면
여기 없앤 연산들은 실제로 할 필요가
없다는 것이 분명합니다
예시를 끝까지 봅시다
여기는 최대 8이고
그 위는 정확히 8이 됩니다
다른 가지는 취급하지 않으니까요
여기는 최대 8이고
이 두 숫자를 
비교해도 더 나아가나요?
네 계속합니다
최대지향 선수가 오른쪽으로 가서
정말 8을 실현할 수도 있으니까요
따라서 오른쪽도 계속 봐야 합니다

Korean: 
여기는 9이고 위는 최대 9이고
이쪽도 9이니 위는 9가 됩니다
값을 위로 가져가면 최소 9가 되고
최소지향 선수는 왼쪽으로 가면 8이고
최대지향 선수는 
여기 9로 가기를 원하겠죠
또 가지치기를 할 수 있어요
이 가지는 없다고 생각해도 됩니다
나머지 정적 가치는 계산하지 않습니다
이 이동은 보지 않아 
연산을 또 절약합니다
아까 본 예시에 알파-베타 알고리즘을
적용하면 나아지는지 봅시다
속도를 좀 줄이고
탐색 방법을 알파-베타를 
쓰는 미니맥스로 바꿔보겠습니다
이제 각 노드에 값이 두 개 있습니다
이게 뭘까요?
이미 알죠
알파와 베타입니다
지금부터 알고리즘은 
트리를 따라 내려가면서
이 두 값의 범위를
점점 좁혀나갈 것입니다
자 시작해봅시다

English: 
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.

Korean: 
두 개의 단말노드를 계산하지 않았네요
새로운 트리로 해봅시다
이번엔 다른 두 개를 계산 안 했네요
또 새로운 트리를 만들면
역시나 두 개입니다
방금 칠판에서 본 예시를 돌려보면
어떻게 되는지 봅시다
제가 제대로 했기를 빕니다
속도를 1로 줄이면
휴, 같은 답입니다
처음에는 몰랐겠지만
당연히 모르겠죠
사실 경기는 이쪽으로 이렇게 흘러가
결국 8에서 끝납니다

English: 
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

Korean: 
가장 큰 값은 아닙니다
가장 작은 값도 아니죠
대결하는 상황이기 때문에
적당히 타협된 중간값이죠
이렇게 하면 도대체 얼마나 할 일이
줄어드는 건지 궁금하죠?
최적의 경우에는
모든 게 원하는대로 된다면
즉 신이 내려와 
최적의 순서로 배열해준다면
그럼 여러분이 해야 하는 일의 양은
계산해야 하는 정적 가치의 수는
어림잡아 2b의 d/2승입니다
이 2는 상관없지만
여기 2는 중요합니다

English: 
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.

Korean: 
이게 실제 하는 일의 양입니다
b의 d승에서 b의 d/2승이 되었습니다
이게 무슨 뜻이죠?
이 방법을 안 쓰고
7단계까지 내려갈 수 있었다면
이 방법을 쓰면 
얼마나 갈 수 있을까요?
14단계입니다
이는 세계 챔피언을 
이기냐 마냐의 차이입니다
하지만 이는 신이 모든 걸 맞춰줬을 때의
최적의 상황입니다
하지만 실제 상황에서도
실험 결과에 따르면
최적의 상황과 연산량은
크게 다르지 않다고 합니다
따라서 알파-베타를
쓰는 것이 좋습니다
시간을 많이 절약할 수 있죠
또 다르게 생각해볼 수도 있어요
만약 같은 깊이를 내려간다면
얼마나 일을 덜 해도 되는 걸까요?
꽤 줄겠죠?
제곱근의 양일 겁니다

English: 
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?

English: 
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.

Korean: 
이렇게 생각해 볼 수도 있는 겁니다
이제 집에 돌아가도 될 것 같지만
한 문제가 남았어요
우리는 지금까지
분기 계수가 일정하다고 가정했습니다
하지만 실제로 분기 계수는
경기 상황에 따라서 계속 달라집니다
2분 안에 얼마나 계산을 하는지나
한 이동에 얼마나 
걸리는지 볼 수도 있고
또 얼마나 깊이 
갈 수 있는지 볼 수도 있겠죠
확답을 얻을 수는 없습니다
경기마다 달라지니까요
초기에 개발된 게임 프로그램은
계산을 모두 하지 않았습니다
3초안에 결정을 해야 했으니까요
만약 가능한 모든 경우를 계산했다면
다른 이동을 결정했을 수도 있겠죠
아니면 2-3분이 
넘도록 연산을 계속하다가
이동을 정하지 못하고

Korean: 
이상한 짓을 할 수도 있죠
좋은 상황은 아니겠죠
하지만 초기에는 그랬습니다
아무도 얼마나 깊이 갈지 몰랐으니까요
이번에는 다른 상황을 봅시다
여기 게임 트리가 있어요
이진 트리입니다
여긴 0단계이고
여긴 1단계입니다
여긴 d-1단계입니다
그리고 여긴 d단계입니다
여기 밑에는
이런 상황이 있습니다
중간은 일부러 그리지 않았습니다
여기 밑에 단말노드는 몇 개일까요?
b의 d승이겠죠?
잠깐 알파-베타 알고리즘을 잊고
탐색에서 했던 것처럼
하나하나 추가해나갈 겁니다
따라서 우선은 알파-베타를 쓰지 않고
기본적인 미니맥스 알고리즘만 씁니다
그렇게 되면 이 밑에 있는
모든 정적 가치를 계산해야 됩니다

English: 
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.

Korean: 
총 b의 d승 개이죠
바로 위 단계에는 몇 개일까요?
b의 d-1승 개입니다
마지막 단계보다 그 전 단계는
노드가 얼마나 적나요?
1/b개겠죠?
만약 이 d 번째 단계까지 
내려올 수 없을 것 같다면
이 d-1번째 단계까지 
내려왔을 때의 값을 계산하여
일종의 보험을 들 수 있을 겁니다
이 보험의 개념을 알겠나요?
만약에 분기 계수가 10이면
이 보험의 비용은 얼마일까요?
총 연산의 10%입니다
왜냐하면 d-1단계까지만 가면
d 단계까지 내려갈 때보다

English: 
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

English: 
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

Korean: 
10분의 1의 연산량으로
이동을 결정할 수 있기 때문입니다
알겠나요?
이 개념은 일반적으로 굉장히 중요합니다
하지만 그 전에 생각할 것은
만약 분기 계수가 너무 커서
그 전 단계까지도 
갈 수 없다면 어떡하죠?
그래도 좋은 이동을 하기 위해
뭘 해야 할까요?
맞아요, d-2 단계를 보면 됩니다
여기를 말하는 거겠죠
이 단계에서 계산량은
b의 d-2승입니다
자 이제 10%의 
10%를 또 더했습니다
이제 어떻게 되는지 눈치챘죠?
어떤 상황에서든 이동을 결정하도록

English: 
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?

Korean: 
보장하기 위해서 어떡할까요?
학생: 꼭대기에서-
뭐라고요, 크리스토퍼?
학생: 꼭대기에서 시작합니다
꼭대기에서 시작하고
단계마다 보험을 드는 겁니다
하지만 이는 비용이 클 수도 있어요
따라서 이렇게 하는 게
가치가 있는지 따져봐야 합니다
크리스토퍼가 말한 대로 해보면
보험을 들기 위해 필요한 연산량은
우선 1입니다
첫 번째 단계는 필요 없지만
편의성을 위해 꼭대기부터 시작합시다
1 + b
b는 1단계에서의 보험 비용입니다
그리고 b의 제곱을 더하고
b의 d-1승까지 쭉 더할 겁니다
이게 우리가 매 단계
보험을 들기 위해 필요한 연산량입니다
고등학교 수준 계산이죠

English: 
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.

Korean: 
심심풀이로 같이해봅시다
변수 이름이 조금 그렇네요
bS는
모든 항을 b로 곱한 다음에
첫 번째 식을 두 번째 식에서 빼면
계산을 해보면 
보험을 들기 위한 비용은
(b의 d-1승)/(b-1)이 나옵니다
이건 큰 숫자인가요?
계산을 조금 해보면
b의 d승은 엄청나게 크니
여기 -1은 무시해도 됩니다
b는 어림잡아 10에서 15사이겠죠

English: 
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.

Korean: 
b-1은 b나 마찬가지이니
결국 b의 d-1승 정도가 될 겁니다
적당히 근사치를 구해보니
매 단계에서 보험을 드는 비용의 합은
한 단계에서만 보험을 드는 비용과
큰 차이가 없습니다
이 개념을 점진적 심화
(progressive deepening)라고 합니다
이제 다시 우리의 
전략 리스트로 돌아가
이 모든 게 어떻게 
맞아떨어지는지 봅시다
우선 죽은 말의 원칙은
알파-베타와 관련이 있습니다
왜냐하면 알파-베타를 사용해서
트리의 큰 부분을 떼어내서
정적 계산과 이동 연산을 
하지 않아도 됐었으니까요

Korean: 
죽은 말은 때려도 소용이 없듯이
계산을 해봤자 답을 구하는데
도움이 되지 않으니까요
점진적 심화의 개념은
무술의 원칙 같은 겁니다
적의 특징을 유용하게 써먹는 거죠
기하급수적으로 증가하는 덕분에
특정 단계까지 도달하지 못해도
그 전의 모든 단계에 대해
보험을 들어 놀 수 있는 겁니다
마지막으로, 점진적 심화는
애니타임 알고리즘
(Anytime Algorithm)의 좋은 예시입니다
답을 요구하는 순간에
늘 답이 준비되어 있다는 의미죠
2분이라는 제한 시간이 끝나도
항상 답은 있습니다
제한 시간 안에 시스템이
구할 수 있는 최선의 답입니다
현재 주어진 게임 트리의
상황을 바탕으로 말입니다
애니타임 알고리즘의 종류는 
많지만 이건 그중 하나입니다

English: 
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.

English: 
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--

Korean: 
모든 게임 프로그램은 이렇게 작동합니다
미니맥스에 알파-베타와 
점진적 심화를 추가하는 거죠
크리스토퍼, 알파-베타는 
미니맥스와 다른 거였나요?
학생: 아니요
아니었습니다
미니맥스에 추가할 수 있는 것이었죠
알파-베타를 
사용하면 다른 답이 나오나요?
학생: 아니요
학생: 다르지 않습니다
여러분 모두 머리를
양쪽으로 흔들어 보세요
미니맥스와 다른 답이 나오지 않습니다
맞았어요
똑같은 답을 줍니다
다르지 않아요
더 빨라질 뿐이죠
근삿값도 아닙니다
더 빨라집니다
트리의 부분을 떼어내니까요
죽은 말의 원칙을 사용하는 거죠
크리스토퍼, 질문 있나요?
학생: 네, 점진적 심화를 할 때
만약 어떤 노드의 값이
전체 트리에 있는 다른 값들보다-
아주 좋은 의견입니다
크리스토퍼가 한 말은-

Korean: 
조금 중간 단계를 생략해도 된다면-
크리스토퍼가 굉장히 
중요한 의견을 제시했어요
점진적 심화는
항상 답이 있다는 걸 
보장할 뿐만 아니라
실제로 알파-베타와
함께 쓰면 성능을 높여줍니다
왜냐하면 이 중간 노드에서
계산된 값들을 사용해
가장 큰 가지치기가 가능하도록
노드들의 순서를 바꿔주거든요
크리스토퍼, 이걸 말한 게 맞나요?
아니라면 수업 끝나고 얘기해봅시다
모든 게임 프로그램이 그렇습니다
딥 블루는 얼마나 다를까요?
꽤 비슷합니다
딥 블루는 1997년에
일초에 2억 연산이 가능했습니다

English: 
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.

English: 
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--

Korean: 
알파-베타를 사용해서
14, 15, 16단계까지 내려갔죠
따라서, 딥 블루는
미니맥스에 알파-베타와
점진적 심화를 더하고
엄청난 병렬처리를 더하고
오프닝 북을 더하고
경기를 끝내기 위해 
특수 처리를 추가하고

English: 
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?

Korean: 
마지막으로 가장 중요한
불균형 트리 생성을 더한 겁니다
지금까지는 트리가 
항상 특정 단계까지는
일정하다고 가정했습니다
하지만 꼭 그럴만한 이유는 없습니다
트리의 제일 밑 노드의 상황은
특히나 잘 바뀔 수도 있어요
바로 다음 이동에서
상대방의 퀸을 찾을 수도 있어요
이런 상황에서는 적당히
탐색을 덜 하는 것이 좋겠죠
결국 어떤 특정 단계까지
내려가기 위해 노력하는 것보다
보험을 든 값들을
완벽히 신뢰할 수 있는 트리를
만드는 편이 더 좋겠죠
이것이 바로 1997년에 
카스파로브를 이긴 딥 블루에
핵심 추가 사항입니다
자, 이제 돌아와서
딥 블루는 조금 알겠는데
이 모든 게 우리 머릿속
과정을 모델링한 건가요?

Korean: 
인간의 지능을 모델링한 건가요?
아니면 다른 종류의 지능인가요?
답은 이 중간이겠죠?
왜냐하면 우리는 종종
대결하는 상황에 놓이니까요
다른 제조사와 경쟁합니다
내가 어떤 행동을 했을 때
상대방이 어떻게 할지 
몇 단계 나아가 생각해야 합니다
하지만 그렇다고 사람이 체스로
세계 챔피언이 되기 위해 
14단계나 앞서 계산하나요?
일말의 가능성도
없어 보입니다
사람은 다르게 대결합니다
이 정도의 강력한 연산력은 없으니까요
이 정도 연산력이면
불도저가 자갈을 파는 속도와 같죠
복잡도를 
단순 노동으로 대체하는 겁니다
인간 체스마스터가 경기할 때는
머릿속에 있는 체스 지식을 사용해서
게임의 흐름을 읽습니다

English: 
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.

Korean: 
참고로 이걸 실험해서
보여준 유명한 사례가 있어요
체스마스터에게 보드를 보여주고
외우도록 했습니다
규칙에 맞는 한 그들은
아주 잘 외웁니다
만약 말의 배치가 임의적이라면
그들도 잘 못 외웁니다
따라서 그들은 체스에 대한 지식을 종합해
어떤 레페토리를 생성해서
트리의 꼭대기 선수처럼
상황을 바로바로 판단해
경기할 수 있었던 거죠
딥 블루는 분명 지능을 보여줍니다
하지만 우리의 지능은 아니죠
불도저 같은 지능이죠
따라서 이런 류의 지능을
이해하는 것도 중요합니다
우리의 머릿속에 있는 것과는
조금 다를 수 있어요
오늘 수업은 여기까지 하겠습니다
다들 알다시피 수요일은
배움을 자축하는 날입니다

English: 
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.

English: 
And, therefore, I will
see you on Wednesday,
all of you, I imagine.

Korean: 
모두 수요일에 다시 봅시다
여러분 모두 말입니다
