Re: computer-go: minimax and go

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

   From: Christian Nentwich <c.nentwich@xxxxxxxxxxxxxxxxx>

   > The  universe is far too small,  light is too slow  to ever search the
   > entire game  tree within  a few   billion years.   But my  argument is
   > theoretical.  The practical goal is not even to play  good Go, it's to
   > play "better" Go than we did yesterday with a computer.

   Your argument up to here has been the following, as far as I can tell:

     1) Given infinite resources you could search the whole game tree
     2) Searching the whole game tree yields a perfect program

   and then

     3) There are no infinite resources
     4) The distance to searching the full game tree is proportional
	to the program's playing strength

It's  useful to  use the  terminolgy  "in theory"  which usually means
something can be imagined to work correctly, even if todays technology
has no chance.  So I  can state, "Searching  the entire game tree will
yield perfect play!"  That is not to say we can do it now or ever.

So points 1 and 2 were to illustrate a point.

   Is it worth pointing out that 4) is complete speculation ? There is
   plenty of evidence of experimental Go programs getting weaker with
   increased search depth, because their evaluation functions break under
   the amount of trade-off to be done.

It's very difficult for me to believe that  if I can ALMOST search the
entire game tree, but not quite, then I should be playing about as bad
as  possible (since I'm doing  such a deep search  and the deeper I go
the worse I  play) until I actually   search the entire game  tree and
play perfectly.  If you graphed this it would form a big check mark.

Point 4 is not    speculation.  In theoretically constructed    search
tree's this can happens,  if your evaluation function bears absolutely
no relationship to end  node scores or  there is no clustering of good
and  bad positions.  But in  Go,  if I  have  an excellent position, I
probably will  still  have an  excellent position  on  the  next  move
assuming  I play a minimally  competent move (and  in most case even a
totally random move or even the worst possible move!)

The evidence you cite  is no kind of proof,  even by a very long shot.
It happens for several  reasons, all of  them having to do with design
bugs.   For instance:

A selective search could be  incredibly tricky and  could lead to this
behavior.   Also, a   search   can magnify   the  errors  of incorrect
evaluation.  The anectodal evidence doesn't convince me that it's just
plain wrong to think ahead, it just tells me something  is wrong.  You
said it right when you said "their  evaluation functions break."  They
are good for what they  do, but they are broken  with respect to being
properly constructed for global search.

   Of course it is easy to argue that programs should be developed so that
   their strength increases as the search depth increases, but that is
   equivalent to arguing that "people should try to write better programs".

Hey, I'm definitely   not being  critical  of Go   programs, they  are
wonderful  engineering feats in my  opinion.  I'm saying that programs
should  be developed that increase   in  strength with hardware,   not
neccesarily  "search depth."  Search depth  is the intuitively obvious
path but maybe  there are more paths available.   If you can construct
an evaluation or set  of move selection  rules that takes advantage of
increasing  power then there is  nothing wrong with   that either.  My
guess is that we will want a lot of both.

I  "know" that depth will do  it, but only  very  slowly and maybe too
slow for our tastes.  But no one has suggested another way that scales
infinitely.  (actually, perhaps pattern datbases scale infinitely with
table space but you still have the exponential space explosion just to
gain minor  improvements  and  the  problem of  how  to populate these
databases.)

I think we are scaling, over time, by program re-writes.  If I started
distributing computers that were 1  trillion times faster than what we
have right  now to all the Go  programmers, they would start rewriting
their programs tomorrow, and they would have some degree of succees in
writing much stronger programs.

Don