[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
computer-go: Go Devil
In my personal opinion, the estimate that the best humans are about 1
or 2 stones from perfect Go play is way off the mark.
I don't know that much about Go and I freely admit it but by analogy
with Chess, which I do know pretty well, I would like to make a case
that humans are quite far away from perfect Go play. This is all
based on the assumption that Go is more complex for humans to master
than Chess. I don't know for sure that this is true, but I strongly
suspect it is.
So the rest of my discussion will be an excercise in convincing you
that humans are not nearly as close to perfect play as we might think
in the game of Chess and you can extrapolate to Go if you wish.
Unfortunately, I have no proof of any of the assertions I'll be
making, but here goes anyway ...
In Chess we have a very mathematically logical rating system, that
makes it quite easy to compare two players. You can easily calculate
for instance, based on the ratings of two individuals, what the likely
results of a series of games will be.
Therefore, in principle, all we have to do is compare Kasparov's
rating to Gods rating to get our answer. Unfortunately, we do not
know what Gods rating is! But maybe we can at least set some kind of
crude lower bound on it?
One thing we do have a pretty good feel for, at least in computer
chess, is that computers seem to improve almost linearly with depth of
search. In fact, there is a rule of thumb that states about 180 ELO
rating points per ply of search (more or less.) A few years ago, when
this was demonstrated, it was believed that this linear improvement
wouldn't hold with a little more speed. I watched the depth of search
go up year after year without this happening, and yet many people
always felt we were right at that point where further speedups
wouldn't help. After all, computer were starting to get nearly as
good as humans!
Although there is now some evidence that the flat line of linear
improvment is starting to curve somewhat, it's not that pronounced
even yet. Of course there are many theories and opinions that these
studies might be flawed or that there is too much intransitivy between
computer and human games and so on, but even if you make very liberal
allowances for these, it's difficult to conclude that a program like
Deep Blue is very close to playing like God.
How deep does a computer have to go to play like God? Personally, I
don't think you have to search the entire game tree to get pretty
close. We now have endgame databases that take really simple subsets
of the game of Chess and solves them, effectively giving us the
equivalent of 50, 100, 200 or more ply searches in these specialized
situations. These databases play absolutely perfect chess in the
domain for which they were built.
So if you had a computer capable of searching about 100 ply (let's
make up numbers!) in fairly simple endgames, you would have something
reasonably close to perfect play. But since the middlegame and
opening still have to happen first, even this program will still see
many positions that it can't solve. However, I believe that with a
good sound evaluation function you might find that a 100 ply search
would come pretty close to playing God-like chess! This is just a
wild guess. I think the 'curve' is already very flat in this area
however, and probably a 50 ply full width search will do nearly as
well.
Over the years I have heard so much (well meaning) nonsense that I am
very skeptical of judgments like this. I remember the bet that
computers would easily beat the best humans in 10 years. The bet was
made and lost, and then made and lost for the next 10 years. Humans
are notoriously bad about judging their relative position in the order
of things and if I were a betting person, I would bet my whole life
savings that an omniscient player (especially Go Devil) could give up
MANY stones to the best living player.
Don