Re: computer-go: FPGA

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

   From: Mike Gherrity <gherrity@xxxxxxxxxxxxxxxxx>
   Date: Wed, 30 Aug 2000 15:56:10 -0700 (PDT)
   CC: Mike Gherrity <gherrity@xxxxxxxxxxxxxxxxx>
   X-Mailer: ELM [version 2.4ME+ PL68 (25)]
   MIME-Version: 1.0
   Content-Transfer-Encoding: 7bit
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx
   Content-Type: text/plain; charset=US-ASCII
   Content-Length: 731

   Hi Don,

   > Dave, I  am interested in why a  computer would get consistantly worse
   > results   with more computing  power  and   why  you believe it's  not
   > possible to fix.

   Dana Nau at U. Maryland showed there were games with this property.  The
   deeper you search, the worse you play.  He called such games "pathological."

   It was also shown that scheduling can have such un-intuitive behavior.  Adding
   another cpu can actually increase the time it takes to finish a job.

   Although history has shown that more computing power improves play in many
   parlor games, including checkers and chess, it is not clear when this
   assumption may fail.  Perhaps Go has many pathological positions.  Has MFG
   encountered such positions?


	   mike


Yes, I am  familiar with the  pathological searches and have  heard of
this results.  My understanding was  that theoretical trees have  this
property, where you assign completely random  scores to end nodes in a
made up  graph of constant width.  I   don't remember what theoretical
evaluation function was used to compute scores at intermediate nodes.

I   don't  think this   result applies   in   practice  to  chess, go,
tic-tac-toe or any  typical 2 player game we  are used to playing.  Do
you remember  what   the  assumption was  concerning   the  evaluation
function used in these theoretical games?  I seem to remember that the
evaluation attempted to be corelated to a win probability based on the
number  of children that were game  theorectic wins, or something like
this but I don't remember the details.


I did  write a go program that  improves (based on self-play at least)
significantly   with  depth.  It's  not  a   good basis  for  a strong
tournament program, but it did seem to indicate that  it's not hard to
write  a program that has the  properties  that its strength is highly
corelated to depth of search.

Here is how the program worked:

I did  a board influence type of  analysis at the root  node to get an
initial  move  ordering only  but the  rest of  the  search was simply
iterative deepening  full width search.   The evaluation  function was
stone count only.  I used many tricks (mostly  based on liberty counts
of strings) to prune the tree, but always in a way that guaranteed the
same results  as  a  full  width search,  so  I   don't consider  this
selective in any way.

I played thousands of games on all different sizes  of boards.  On the
small boards I could  really search deeply.  I  never failed to get  a
significantly greater  win percentage  by  doing 1  extra search  ply.
This is exactly the same results you would get in chess.

I believed I succeeded in writing a scalable go  program and it wasn't
difficult to do.  However   I don't pretend that  this  was a GOOD  go
program or that  it  would even  be good  on  a computer running  100X
faster.  I don't  think it's the right way  to design a go program but
all  I wanted to learn is  if it was  possible to  write a scalable go
program and I am strongly inclined to believe that it is.

Also, I cannot  prove that the  program would play  better at depths I
was unable  to reach due  to time  considerations, but it  seemed very
likely that it would keep improving until it looked deep enough to see
the end  of  all game   variations.   Of course  this  would take  the
lifetime of many universes to properly test!  However it's easy to see
that given  enough  time, it  would in principle   play perfect go and
would be  infallible.  It doesn't  seem likely  to me  that there is a
level somewhere between this and what I tested where it would suddenly
play worse for a while.

So to me, the only question is can I write a practical program that is
competive  with modern   programs  and yet  also  has  this very  nice
scalable property?


Don