[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: computer-go: A problem with understanding lookahead
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