Re: computer-go: A problem with understanding lookahead

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

>  Forget the combinatorics.

Why?  The premise of this whole discussion is how  a deep searching Go
program would behave, not  IF we  can do one.

Your explanation  of the difficulties of   Go evaluation was excellent
and easy to understand and I agree with this part completely.

However, you are also completely unaware about how  difficult it is to
do  Chess evaluation.  Chess  evaluators are horribly incompetent, and
suffer from the  same problems  that Go  programs do.  King  safety is
notoriously  difficult, you can be  a  queen up and  have  a dead lost
position.   Trapped pieces are  just like  your  dead stones, they are
dead and  can't be evaluated with  any kind of accuracy.  Passed pawns
can't  be correctly evaluated unless  the search actually resolves the
situation.

The fact that modern  Chess programs  have  managed to  play extremely
well has come   as  a HUGE surprise  to   most of  the  computer chess
community precisely  because we all recognized  with  the same clarity
that you  do in Go, the  horrible inadequacy of  evaluation functions.

Every  time I hear   someone  enumerate why   Go  is hard, I  get this
overwhelming sense that I'm hearing the  same old broken record I have
been  hearing for decades about Chess.   For some reason a minority of
Go programmers (I think you are one of them) seem to  think it's a new
problem unique to their domain.  When I started  writing my Go program
I already knew  to expect these  problems, I  can't understand  why Go
programmers  think chess is  somehow immune  to the same difficulties.

Your last paragraph tries  to tie lack of deep  searches in Go to  the
difficulty  of  evaluating Go positions,  and   I hardly see  how this
follows, it  doesn't take great genius  to realize  it's the branching
factor  that  makes deep searches a   fantasy in Go.    

Even though  Go  evaluators are  truly difficult  (I won't deny this),
they are reasonable  in the Chess sense  of what  reasonable is, which
means they often  have a rough  idea of who has  the advantage  if the
advantage is large enough.

By the way, it's not completely clear that it is important as we might
think that  an  evaluator estimates all    positions accurately.  This
sounds like  a  strange  statement, but what   a tree  search does  is
COMPARE positions, and  most  positions it compares are  very similar.
It's easier to   compare similar positions  and tell  which is better.
It's also  a  hard problem, but  it's  much easier than  comparing two
completely different  (but equal) positions   and determining which is
better.  So a program can drift into a position  it thinks is bad, but
still be playing  excellent moves because  it compares better  than it
actually evaluates. 


Don




   From: "David Mechner" <mechner@xxxxxxxxxxxxxxxxx>
   Content-Length: 1117

   Forget the combinatorics.

   The critical difference between go and chess, as far as evaluation goes, is
   that in go dead pieces can stay on the board, even until the end of the
   game.

   Go is a game of territory. To evaluate, you have to be able to count
   territory. Dead stones are enemy territory. To be able to count territory,
   you have to know which stones are dead. Therefore to able to evaluate a
   position, you have to know which stones are dead.

   But knowing which stones are dead is HARD. Not only can't our programs
   figure it out quickly enough for practical use in a static evaluation
   function, they can't figure it out AT ALL.

   There are simple cases where a group is obviously alive or obviously dead,
   where fast heuristics might give reasonably accurate answers. But in the
   majority of (important) cases, there is no working model of how to go about
   solving the problem.

   Until serious advances are made in the state of the art of life and death
   analysis, talk of a reasonable evaluation function is fantasy, and talk
   about using big search in go is a fantasy.

   -David Mechner
   http://cns.nyu.edu/~mechner/