Re: computer-go: Applying Moore's Law to Computer Go

[Sam Sloan <sloan@xxxxxxxxxxxxx>]

> I disagree.
> 
> It was predictable that the strength of chess playing programs would
> increase as the speed of computers increased because by the mid-1980s we
> had solved the basic problems of how to write a good chess playing program.
> I competed in the World Computer Chess Championship in Cologne, Germany in
> 1986 and the programs we had then work the same as now. The programs now
> are faster, more efficient and contain fewer bugs but they are basically
> the same as in 1986. The main reason they are stronger now is the CPUs run
> faster.

Yes, I agree.   As far as go  is concerned, it's my understanding that
the very  best programs do  not scale  AT  ALL to faster hardware  but
would simply play  the same way no matter   how fast the hardware  is.
Doesn't one of  the  top programs  usually play a   move within a  few
seconds?  I'm sorry I can't remember the reference, but I remember one
program author complaining that his go program played weaker if it did
too  much searching.   I consider  that a bug   of sorts, but it  does
demonstrate that computer  go isn't where chess  is, even factoring in
the extra complexity.

My  prediction is that, like chess,  a few well known solid techniques
will become widely accepted and used  after a shaking out period, some
of the "bad ideas" and highly speculative  experiments will get culled
out and there will  be a sudden jump  in the strength of  go programs.
But the  jump won't put  them anywhere near  the strength of  any good
chess program.  After this, progress will be slow  and incremental.  I
do believe that once it is done right, there should, like chess, be an
improvement that is closely tied to the power of the hardware.  I also
believe that  the  correct way to  think about   go  programming is to
search for some algorithm that improves with computational power.  The
extra "computation" may not necessarily  be applied to the search  but
might be applied  in other ways  we haven't thought about.  Finally  I
don't think we'll get the same jump in strength  we get with chess for
each  doubling of computer resources.  Remember,  if your "go" program
doesn't scale to better hardware, I can write one guranteed to beat it
given enough computing power by simply doing a brute  force search.  I
would argue that  this "algorithm"  at  least scales well, although  I
concede it may not play good go for a very long time!

Has anyone ever considered doing a brute force  search combined with a
very powerful evaluation component?  In chess, the  early days saw the
first   really sucessful programs    did very shallow   but full width
searches.   Everybody  then  said it  wouldn't work,   but  it did.  I
remember being  very surpised that  a 2 or  3  ply search played quite
reasonable chess.  These early  programs  didn't play great, but  they
played much better  than anyone expected and a  lot of people wasted a
lot of time  with selective searching.  I  would argue that if someone
wrote an evaluator capable of playing a reasonable move, then adding a
ply of look   ahead would improve  the program  significantly.  People
ignore this possibility because they feel overwhelmed by the fact that
even the simplest go sequences need many moves to develop.  But we are
babies and  must start  with baby steps.   The short  term goal  is to
write a   go program today  that  beats the go programs  of yesterday.
That's  how we did it in  chess.  Probably we could  do 2 or 3 plys of
lookahead  and  we  could   combine    this with extensions     and  a
sophisticated quies search, just like in chess.

Since todays go   programs are  based very  heavily   on evaluation, I
simply  suggest  a framework where this   heavy evaluation is combined
with something like a brute  force search, or one  that does a "bounds
based"  kind of  selectivity like modern   chess programs do.  I don't
think you  have to change anything else,  you keep  trying to get more
sophisticated  in the evaluator and for  many years  I suspect most of
the improvements will come from the  evaluation, but I'll bet it would
scale to better hardware.

Finally, I'll say  that by analogy, if there  is  something that works
much better  in go, the basic idea  could probably  be used to improve
chess programs.    We could dump  the  searching  and  do it all  with
evaluation.  This  is the way  a lot of  people thought computer chess
should be approached many years ago.   

- Don Dailey <drd@xxxxxxxxxxxxxxxxx>