Re: computer-go: minimax and go

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

Hi Dave,

Your reasoning  is basically correct, the   branching factor is indeed
much larger in Go than in Chess.   Not to be  sarcastic, but I have to
ask, "so what?"

To me, this might imply  that it takes a lot  more hardware to play  a
little bit better.   Ok.

The previous poster wrote:

   I need to know (succintly) what are the arguments that a brute-force
   minimax approach to Go won't work assuming increased computer power 
   just like it worked for Chess? 


A brute force program will "work."   Give me infinite computing power,
or enough computing power  to search the  entire game tree and I  will
write a perfect Go program.   Short of that, I can  write a Go program
that plays better with every hardware doubling of power.  It might not
play much better,  it might even  be hard to  measure but it will play
better on the average  with each doubling, until  it reaches the point
where it can search the entire game tree.  

So I have a pathway (in principle) to making a program play perfect GO
with a finite amount of computing power,  or to get abritrarily strong
with an  increasing amount of computing power.   Do you have a pathway
to do the same  without involving any  searching?  I doubt that any of
us do.

Please note that  I   am taking  a  bit of  a philosophical  approach,
believe me I understand the problems, and I realize that we don't know
how  to  construct a  very effective search  ...   yet.  A naive fixed
depth n  ply search  with a simple   static evaluation  is not  what I
suggest.  I'm also not being critical of how Go programs are currently
written,  I think  we are  doing  the best  we  can.  But I just don't
believe that we  will  make much more progress  by  tweaking  our eval
rules, patterns and  openings.  At some point,  we will have  to start
searching more than  just local string battles and  we will have to do
it really intelligently.

The key, is that both evaluation AND search  is much harder in Go than
in Chess.  That only means that whatever we do, it won't be as good or
as easy as in  Chess.  You can't say search  won't work any  more than
you can  say evaluation won't  work just  because it's  so much harder
than Chess and we can't even do it in Chess.


Don


P.S.

  >    Now factor in that chess programs get very good reductions in the
  >    raw numbers because very strong, fast, simple evaluators prune out
  >    most of the really bad nodes without having to evaluate them.

That's  not true.  A true brute  force chess program only prunes based
on alpha/beta    cutoffs.  A Go program written    in this style would
actually prune much more heavily, and it's  doesn't matter how good or
bad the evaluation function is.

Yes,  modern programs  do null    move prunning  and  this does   have
something to do with the strength of the evaluation function and gives
more cutoffs than  alpha/beta.   However, it's not why  Chess programs
are so strong.   If you  throw out  null move prunning  you will still
have a master strength Chess program.  





   X-Sender: ddyer@xxxxxxxxxxxxxxxxx
   X-Mailer: QUALCOMM Windows Eudora Version 5.0
   Date: Wed, 08 Nov 2000 11:49:57 -0800
   From: Dave Dyer <ddyer@xxxxxxxxxxxxxxxxx>
   References: <200011071757.MAA04849@xxxxxxxxxxxxxxxxx>
   Mime-Version: 1.0
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx
   Content-Type: text/plain; charset="us-ascii"
   Content-Length: 783


   The basic arithmetic is this:  

   To do a 10 ply brute force search in Chess might in principle have to examine 
   25^10 ~= 9.5e13 nodes

   To do a 10 ply brute force search in Go might in principle have to examine
   200^10 ~= 1.024e23 nodes

   that's a billion times harder.


   Now factor in that chess programs get very good reductions in the
   raw numbers because very strong, fast, simple evaluators prune out
   most of the really bad nodes without having to evaluate them.

   Now factor in that in go, even very simple, local problems require reading
   15 - 20 ply, and there are usually many such "simple" problems on the
   board at once, so reading the full outcome of a midgame position 
   could easily require 100 ply.

   Now factor in that in go, there are no "strong, simple, fast" evaluators.