So last time we were here Artemy
finished up the discussion on
introducing the beginnings of machine
learning and today what we're gonna talk
about over the next couple of lectures
is a case study in machine learning
applied to a specific system so board
games have a very long history and AI
going all the way back to the 1950s and
they were used to kind of drive the
initial developments and artificial
learning and machine intelligence so why
is it why do we care about board games
well on the one hand board games are
this really isolated system where we
know what it means to win we know what
all the moves are and we kind of know
the consequences of the of those actions
unlike in the real world where things
would be really complicated and messy
and people change and times change and
so it's hard to have it a nice
replicable system whereas in a board
game the rules of chess have been the
same for hundreds of years but also
board games have been this measure of
what people think of as intelligent and
whether or not that's true
we can see there are many features of a
board game that were late to the world
world so in particular in this article
but from byte magazine in 1978 we can
see these features that are really
important to playing a game so you need
to plan out a strategy to figure what
moves you're gonna make and how to
execute them you need to plan ahead to
figure out what your goals are both
short term and long term and then you
need to be able to calculate how these
moves are going to play out in order to
execute a good plan so we can see that
while these features might be in their
own specific ways in chess there are
actually the same kinds of things that
we do in real world systems making board
games an ideal place to start trying to
think about how to make machines do
things that seem like they're
intelligent computer scientists have
been building machines to play board
games now for a long time as well so
back in nineteen fifty two of the
Machine oxo Pam managed to play a
perfect game of tic-tac-toe flashing
forward in 1995 the computer Chinook
became the world champion in checkers
now the technically Chinook became the
champion in a way that computers can
which is that humans are mortal and in
fact the best human checkers player
player Marian Tinsley actually passed
away in the middle of their match and
Marian Tinsley was so much better than
every other player
that all of the sudden Chinook became
the world champion but we'll never know
if Chinook was better and then many of
you may have heard in 1997 deep blue
beat garry kasparov - who is the world
chess champion at the time so we see
that 1952 is tic-tac-toe and then 1995
checkers is beaten and then 1997 chess
the computer becomes the world champion
so 1998 how were computers doing it go
well if you see this board here you
might not know how the rules are but the
computer got to play 30 moves at the
beginning of the game and still lost to
a decent human not even the world's best
human so you can see that the way the
computers are the best player ever in
chess but still needed at least 30 30
moves at the beginning of a go game in
order to beat top humans so now let's
take a minute divergent to talk about
the rules of go and we'll talk about how
it works so first let's talk about the
history so go is very popular worldwide
but especially in East Asia and there
are over 30 million players throughout
the world and in fact there are between
four and six tournaments every year that
have a prize winnings of over a quarter
of a million dollars go is between 2,500
and 4,000 years old and in fact some of
the oldest texts that we have about go
is the writings of Confucius so go has a
very long history as well so in
particular it go is a game it's a
two-player game so there's two players
but it's also deterministic which means
there's no randomness so if you play
something like poker you don't know what
card you're gonna draw when you draw
cards whereas in go you play a move and
that's that
and it's also a game of perfect
information which means that both
players know everything that's going on
so you could also imagine say a game
about war where there's a fog of war so
maybe you have pieces but I don't know
where those pieces are and so gantt go
is not that it every everyone knows
everything which makes it a very nice
system for machine learning because we
don't have any hidden information so the
way it works is that I said there are
two players black and white and they
alternate moves the board is 19 points
by 19 points and players alternate
playing on the intersections the next
idea is this idea of capturing
if you have a group of stones that are
connected by points and they get
surrounded entirely by stones of the
opposite color those stones are removed
from the board now black and white play
back and forth taking off stones if
necessary if they get captured and at
the end of the game we finally see who
is surrounded the most territory and so
what we do is we count up the territory
surrounded by both players and then we
count up the number of stones that you
have captured and whoever has the most
points wins so that's not all of the
rules ago but it's almost all the rules
to go and we'll hopefully give you
enough to moving forward to give you
some sense of how the game plays so
going back to computer go as I mentioned
back in 1998 computers are doing really
really poorly and then around 2000 we
finally had one of our first
breakthroughs which was talk later
but in 2004 a computer loss to a
professional with a nine stone handicap
which is still a big handicap but it's
it's much less than 30 stone handicap
and then by 2010 we had decreased
another two stones so a computer beat of
professional with a seven stone handicap
and then another five years on five
years later in 2015 a computer beat a
professional with a five stone handicap
so from 2004 until 2015 so eleven year
span we decreased four-star handicap
couple months later and March of 2016
this program alphago defeated Lisa Dole
who is the one of the top professions at
the time with a zero stone handicap so
it took us 11 years to decrease four
stones and then in like three months it
went from five stones to beating one of
the top professionals and then a couple
of months later the second version of
the program alphago master beat the top
professional coach a three to nothing so
the computer didn't even lose and in qje
was one of the top players at the time
and then recently a couple months ago
alphago zero came out and defeated the
alphago master version eighty nine to
eleven so it took us eleven years to
break four stones but now in the last
year and a half we've managed to like
beat the top players and then beat
programs that have beat the top players
so we've had this amazing level of
progress