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

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

At 12:11 PM 11/18/99 +0900, Sam Sloan wrote:
>
>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.

This is not true.  The top programs use all of their time.

>Doesn't one of  the  top programs  usually play a   move within a  few
>seconds?  

This was true of Handtalk many years ago, but no longer.  Handtalk was
developed on a very slow original IBM PC, so it ran extremly fast in
early tournaments on much faster hardware.

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.

I think this was me.  More search exposes evaluation bugs.  Go evaluation
functions are orders of magnitude more complex and slower than chess
evaluation functions, since there is no major, simple factor like
chess material balance.

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

I think this has already happened.

>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!

No chance while we are both alive, since computers fast enough to brute 
force go will not exist for centuries, if ever.

>
>Has anyone ever considered doing a brute force search combined with a
>very powerful evaluation component?  

Of course.  It has been tried.  One of those early experiments.  But an
accurate evaluation is too slow for more than a one or two ply search.

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

Not at all.  A ply of lookahead can't see the simplest tactics that a
beginer can see, like an atari on the second line.  The capture is
4 ply deep.  A capture with atari on the third line is seen by someone
only slightly better, and is over 10 ply deep.  Searches must be local 
deep, not full width brute force.

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

A good goal, but you can't do it with brute force.

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

The heavy evaluation, to be accurate, has to do lot of local search for
string tactics, connections, etc.  So you are lucky to get 10 evaluations
per second.

-David Fotland