Re: computer-go: A problem with understanding lookahead

["David Mechner" <mechner@xxxxxxxxxxx>]

Don,

> I am trying to make the case that both Chess and Go evaluation is hard
> and about  the same order of difficulty.   In other words, there is NO
> searching allowed.  I   am asking  the  question, which   plays better
> relative to its domain, a 1 ply chess search (without a capture search
> remember) or  a 1  ply Go program  (without  any local stone battles.)
> The term "forced  win" has no place  in the discussion, unless you can
> figure  out  how  to find   one without  searching.   Maybe you   mean
> "checkmate    positions?"  If so,  they   amount to an incredibly tiny
> fraction of all the chess positions encountered in a tree search.
>
> In both cases, for true 1 ply searches only, the programmer would have
> to  do his best to design  an evaluation that  tries to resolve either
> capture sequences without doing a search, or dead groups without doing
> a search of any kind.  In both cases, this works poorly and is usually
> wrong.

You're making a false comparison: current state of the art go and chess
evaluation functions have been developed with opposite sets of goals and
constraints. Chess evaluation functions have to be fast because they are
used in search, and are effective even though they are crude by human
standards because they are coupled with deep search. Research into
expensive, sophisticated positional evaluation functions in chess was
abandoned when it became clear that deep search with a cruder evaluation
function was a much surer path. In contrast, Go evaluation functions don't
have to be fast because they are not used in search. And they are as
sophisticated as they can possibly be made, because they are /intended/ to
be used in 1-ply search.

In that light, your observation that chess and go evaluation functions are
comparably crude takes on a new significance, quite opposite to the point
you intended.


Anyway, the more I think about it, the sillier this whole argument is. I
don't think anyone denies that if you could search sufficiently deeply, even
a naive evaluation function would work in go. And there is no disagreement
that such search is practically impossible because of the size of the tree
that would have to be searched. Our complaints about life and death really
boil down (in search terms) to saying you'd have to read much, much deeper
in go than you do in chess to get a similar level of play. But since
searching even the same depth is impossible, this seems sort of a silly
objection. We're saying, you don't just need to be able to do 250^D, where
depth D search gives master level play in chess, you have to do 250^(D*k)
where k accounts for the relative difficulty of evaluation in go. Your
intuition says k is close to 1. Mine says it's probably more like 5 or 10. I
can argue more to try to convince you that my k is right, if you'd like, but
I'm not sure there's much point.

-David