Re: computer-go: A problem with understanding lookahead

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

   From: "David Mechner" <mechner@xxxxxxxxxxxxxxxxx>

> I don't think the intuition you're appealing to in your "thought experiment"
> really proves much.

But it's not supposed to be a proof.  


> There's a lot hidden in the phrase "reasonable" evaluation function. In
> chess, counting material seemed reasonable, but it was far from clear that
> this could ever lead to the sophisticated positional judgement that strong
> players all believed was absolutely necessary for high level play.

You obviously are not familiar  with the computer chess world, because
"counting  material" is a  horrible evaluation  function and  does not
lead to "sophisticated positional judgement" in modern programs.  When
chess  programs   are  explained  to  laymen,   the  explanation  gets
simplified  tremendously for  clarity.  But  there are  no  good chess
programs that do not have  a tremendous amount of knoweldge built into
them.  Fritz is often quoted as  an example of a "stupid fast program"
but even  this program  has more knowledge  than anyone on  this group
probably  would believe,  since the  common belief  is that  all chess
programs do is search fast and add up material.  You could write chess
programs  for  years  and never  be  able  to  compete with  the  best
programs, but you could easily write one that searches just as fast.

Now back  to what  a "reasonable" evaluation  function is.   Really, I
don't care what the evaluation  function is, the intuition I wanted to
get across  is that no matter what  your notions of good  and bad are,
you will have an advantage in  terms of "getting your way" if you know
you'll be happy or sad n moves later.

Naturally,  if you have  stupidity or  misconceptions built  into your
evaluation, the search will work hard to achieve these silly goals.

I want to clear up another thing  before we go on.  Nobody can do more
than 2 ply searches with Go and still have a really good evaluation as
far as  I know.  I  never said, nor  am I saying  now this is  what we
"should" be doing.  OK?   Stop feeling threatened by this.  

Having said that, let me answer your objections and let's pretend that
we could  do a deep  search and try  to understand what  would happen.
That's really the issue of  contention, not whether we SHOULD be doing
this or something else.


> Now take go. Let's consider a reasonable (but naive) evaluation function:
> count territory, assuming everything on the board is alive. It's not a
> perverse evaluation function; on the contrary if you could search all the
> way to the leaves, it's actually "correct."  But it's far from clear that,
> say, a depth 6 full-width search using this evaluation function will yield
> even a 20 kyu program, or that searching to depth 7 (or 8 or 9) will be
> significantly better than searching 6. 

Consider   a   human  beginner.    He   probably   has  very   serious
misconceptions about  what is  good and bad  in a position.   He might
have a completely  lost game for many moves  before even realizing it.
Using my thought experiment,  the beginner, even with this "superhuman
insight" I talked about would still  be in the dark.  But this doesn't
mean much  at all, it just  means he is so  stupid it takes  him a lot
more  moves to realize  he is  lost.  I  aruge that  he is  STILL much
better off  with the insight than  without it.  How  does your example
refute this?  It doesn't.

Search  is not an  effective substitute  for evaluation  either.  Your
example  of a very  simple evaluation  function is  just that,  a very
simple  and bad  evaluation.   

There  is another  very interesting  characteristic of  searches.  The
program with the better evaluation function seems to benefit more from
an extra  level of searching!  I  did a bunch of  experiments to prove
this and  so did others  using chess as  the domain.  No one  has ever
proven it doesn't work in other games, it's only been asserted.

So in  your example of  missing knowledge in  a Go program,  you might
play a stupid  move and the effects of it might  go unnoticed for many
moves, therefore it might take an incredibly deep search to recognnize
that it  leads to a  bad position.  But  just a little  knowledge, not
neccessarily specific to the  actual mistake, might allow it recognize
something bad in the position much sooner.

I'll give a simple chess illustration  of this since I know chess much
better than Go.

In chess, you can have a  backward or weak pawn.  If it's weak enough,
it will probably be lost, and  a deep enough search will discover this
and defend, but  it would take a lot more moves  than any modern chess
program can possibly see.  (That probably  comes as a shock to most of
you who seem  to think chess program search  deeply, they don't.)  But
when you have a backward pawn, you  are forced to defend it or it gets
captured right away.  But when you  are forced to defend it, you can't
do other nifty  stuff that your evaluation likes to  do.  Of course if
all you  did was "count material" you  might not care for  a very long
time,  but usually  being forced  to defend  is a  nuisance  that your
evaluation function  notices WELL BEFORE  the pawn ever  becomes lost,
even if your program has no idea that it's weak.



> How deep do you have to go before the
> program can appreciate the value of a crosscut that doesn't lead to an
> immediate capture? How deep do you have to search before it sees the value
> of strengthening a weak group that's got lots of liberties but no eyes?

What difference does  it make how deep?  It would take  a lot of moves
to see this.  You seem to want to believe that a search is supposed to
REPLACE good knowledge, maybe  that's what's wrong here.  My assertion
is that  it cannot hurt to  know a few  moves in advance (of  when you
normally would)  that something is wrong with  your position.  Indeed,
this would be a benefit.  And the sooner you know about it (the deeper
you search)  the more likely you  might be able to  do something about
it.  If your example is suppose to refute this, I don't see how.

So even if you could do deep searching in Go,  your program will still
be tied to the quality of its evaluation function.   I really wish
people would stop separating the two, as if it's one or the other.


> The fact that /we/ would like to be able to do full lookahead with /our/
> evaluation functions doesn't mean that any player with a "reasonable"
> evaluation function will benefit from limited search, even in games we think
> of as having "well behaved" game trees.

We would like to  be able to do a full lookehead  in Go, but it's just
not feasible due to the huge branching factor in Go.  BUT if we could,
I believe it  would be more effective in Go than  in most other games.
In chess, the position can violently  change from move to move and who
is winning can  change repeatedly based on who  made the last mistake.
This is a serious problem in  computer chess.  It's far more stable in
Go.




Don