[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: computer-go: A problem with understanding lookahead


I don't think your evaluation function needs to be totally out of whack. For
example, Many Faces tries to recognize shapes that are worth two eyes when
they are large, to avoid reading every life and death problem down to two
one-point eyes. This early evaluation has some bugs, since it is complex. When
doing life and death reading, if I read wider and deeper, and it more likely to
run into one of the rare positions that is misevaluated, and make a bad move.

A specific case might be that a friendly group is unsettled and needs to be defended.
The no-reading evaluation says that the group is unsettled, but to check this I have
it do some reading. If it runs into an evaluation bug and finds that it can make a living
shape after the opponent attacks it, it will play somewhere else, and the group will die.

In this case, the evaluation function for life and death is certainly not "Totally out
of whack". It just has a bug that might show up in one position out of 100,000.

-David

At 06:08 PM 1/17/2001 -0500, you wrote:

Yes, if your evaluation is totally out of whack I agree with you. The
power of the search is that it helps you reach your goals, even if
your goals are stupid and out of line. You might regret reaching your
goals, but you get better at it with increasing search depth.

So I think the thought experiment is valid. If your evaluation is
this far out of whack, then your program really just doesn't have a
clue about what is good and what isn't and thus a 1 ply search does
the least damage. In fact, maybe you should just change the sign of
the evaluation!

Don


From: "Mark Boon" <tesuji@xxxxxxxxxxxxxxxxx>

Well, your thought experiment is a good one in case of a reliable evaluation
but it's not necessarily applicable in the case of an unreliable evaluation.
Most search strategies rely on alfa-beta cut-off or something similar to cut
down the tree-size which means you need to use evaluations to determine what
to cut-off. If the evaluation is unreliable, the actual tree becomes just as
unreliable. I think David has written several times here that he experienced
that there's a point where more reading made it less reliable because you
give it more opportunity to construct a false search-tree.

This is not the case in Chess because it's so much easier to make a reliable
evaluation function.

Did anyone do any research on this? I mean, trying to quantify theoretically
how much the evaluation has to be wrong to get a less reliable tree at a
given depth. It might possibly be that it's only the case for really very
unreliable functions, which will of course be the case for Go. That would be
very useful information.

Mark

From: Don Dailey <drd@xxxxxxxxxxxxxxxxx>
To: <computer-go@xxxxxxxxxxxxxxxxx>
Sent: Wednesday, January 17, 2001 3:16 AM
Subject: Re: computer-go: A problem with understanding lookahead


>
> Lookahead is a simple concept but very few people seem to have a
> significant grasp of what it is all about.
>
> In a nutshell, if I have a clearly defined goal and a function that
> recognizes it, then in a 2 player perfect information game like Go,
> Chess, Checkers, tic-tac-toe etc, you can try all possibilities and
> discover that you can either achieve your goal or not. There are no
> exceptions, this always works, as long as the goal can be measured
> with 100% certainty.
>
> But with imperfect evaluation functions, things are different.
> Whether you search deep or shallow, your end-node evaluation is just
> as imperfect. So why does passing it down the tree makes it any
> better? Or does it?
>
> The answer is that there is some magic in the fact that a score
> actually survived the journey to the root node! This single score had
> to compete with a vicious adversary (during the min-max process) who
> has the opposite goal. In a nutshell, it boils down to this: It's
> better to be happy 20 moves from now, that it is to be happy right
> now! That's the key to mini-max and why it works. It works with
> humans too, consider:
>
> Let's do a strange thought experiment. Suppose, as a Go player, you
> had the ability to know exactly how you would feel 20 moves later
> about any move you make. Let's say I like a certain move, but a voice
> in my head magically tells me that 20 moves later I will not like my
> position. Let's say this ability is integrated in a nicely recursive
> fashion into your brain, so that I know that the move I'm currently
> thinking of playing is the culprit, not one I might play later (which
> is exactly what a search does.) Would this ability make you a better
> player? In my opinion it would make a very good player practically
> unbeatable, and a weak player much better.
>
> The "magic" seems to be that if you can survive many moves and you
> still like your position (which a search with an evaluation function
> proves because it "knows" it will like it's position n moves later),
> then it's probably a pretty good move.
>
> People used to wonder, in Chess, why just doing a single extra ply of
> searching was so powerful, despite the fact that it SEEMED like we
> needed a whole lot more just to get a little improvement. But this is
> why. The "obvious" conclusions were completely wrong. Even very weak
> players often realize after seeing the opponents reply that they
> "screwed up." I do this in Go myself. If 1 ply error free searches
> were built into the human brain, every chess player would improve a
> class.
>
> I think it's true of Go too. However we have to assume a "reasonable"
> evaluation function and FULL WIDTH search for these things to be true.
> Unfortunately, anything more than a 1 or 2 ply FULL WIDTH search seems
> to be unreasonably difficult in GO, if you also require a reasonably
> good evaluation function!
>
>
> Don
>
>
>
>
> X-Sender: gl7@xxxxxxxxxxxxxxxxx
> X-Mailer: QUALCOMM Windows Eudora Version 5.0.2
> Date: Tue, 16 Jan 2001 21:03:22 +0100
> From: "GL7: David Elsdon" <gl7@xxxxxxxxxxxxxxxxx>
> References: <20010108235912Z4277-62332+78@xxxxxxxxxxxxxxxxx>
> Mime-Version: 1.0
> Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
> Precedence: bulk
> Reply-To: computer-go@xxxxxxxxxxxxxxxxx
> Content-Type: text/plain; charset="us-ascii"; format=flowed
> Content-Length: 780
>
> Hello all,
>
> I have a serious problem with lookahead. I don't understand why it
works.
> Why should the backed up values of a, say, 7 ply full width alpha-beta
> minimax search be any better than the values my evaluation function
gives
> me by simply evaluating the positions at ply 1. I can understand that
if
> the end of the game is in sight then lookahead is useful. I can
> understand that if I use a quiesence measure or some such and only
> evaluate positions when I know that my evaluation function will work
best
> then lookahead is useful. But if neither of these is the case then does
> lookahead help. Is there some way in which the backing up of values and
> minimaxing somehow reduces the error in the evaluations.
>
> I really am seriously stuck with this one.
>
> Cheers
>
> David
>
>
>
David Fotland