[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: computer-go: A problem with understanding lookahead
> Chess has a useful exact metric -- forced win! -- which is useful in a
> significant fraction of the game space.
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. Mabye 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 desgin 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.
It's my understanding that the program Handtalk used to be constructed
pretty much like this, and did pretty well. You guys can correct me
if I am wrong, but I read that it did everthing by static evaluation.
I don't know of any chess program that could do a 1 ply search (even
with a capture search) and be considered even nearly as good as
Handtalk was (which still wasn't very good.) The term "advanced
beginner" would describe an opponent far superior to the 1 ply chess
program.
Almost all of the strength of Chess programs has to do with how a
search modifies, enhances and even supplements whatever knoweldge is
in a chess program. You can't separate terms "forced wins", from the
search.
You do bring up an interesting point, endgame databases. They are
like perfect little evaluation functions. And they do make chess
programs stronger, but still, we are not talking about something very
significant. Like all evaluation, they become more useful with deeper
searches. If I am very generous, they may add 50 ELO points to a
chess program that is already 2500 in strength. In a significant
fraction of games they have no effect on the outcome. Don't forget
that endgame databases are just a table of positions that were
pre-searched (there is that nasty word again, SEARCH.)
Counting material. That's the number one thing people think is such a
good metric. Well, it IS easy to compute. I sometimes compare it to
territory in Go, but it's not the same thing at all. In Go, territory
is the only thing that matters in the end. It's very hard to compute
accurately, but at least we have ways to get estimates that are
sometimes correct or at least close. In Chess, the only thing that
matters is who checkmates his opponent. So why do we count material
instead? Which measurement is most compatible with the goal you are
trying to achieve?
Don
From: William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
On Tue, Jan 23, 2001 at 08:13:33PM -0500, Don Dailey wrote:
>
> X-Sender: ddyer@xxxxxxxxxxxxxxxxx
> X-Mailer: QUALCOMM Windows Eudora Version 5.0.2
> Date: Tue, 23 Jan 2001 16:02:46 -0800
> From: Dave Dyer <ddyer@xxxxxxxxxxxxxxxxx>
> References: <20010123160847.E8740@xxxxxxxxxxxxxxxxx>
> <I1JHLB.A.i_E.Qegb6@xxxxxxxxxxxxxxxxx>
> Mime-Version: 1.0
> Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
> Precedence: bulk
> Reply-To: computer-go@xxxxxxxxxxxxxxxxx
> Content-Type: text/plain; charset="us-ascii"
> Content-Length: 756
>
> At 02:59 PM 1/23/01, Heikki Levanto wrote:
> >Dave Dyer <ddyer@xxxxxxxxxxxxxxxxx> wrote:
> >> In go, there are no such metrics.
> >
> >Ok, idle speculation: What sort of metrics could be useful in go? Never
> >mindthe branching facor, just speculate on what we could possibly use for
> >determining if we like one position better than another?
>
> My point is precisely that there are no known metrics which are
> both useful and computable, and not even a theoretical
> framework exists that could lead to such metrics.
>
> Go has metrics "thickness" "influence" "alive" "dead" "heavy"
> "overconcentrated" etc, but they are all essentially uncomputable.
> Conversely, lots of computable things have been tried as proxies
> for the real metrics, and none has been shown to be much use.
>
>
> All of the metrics in chess are proxies for the real things too. In
> chess, the goal is to checkmate the king, being up in material is
> roughly corelated with the ability to do this. How much material you
> have is computable but doesn't have to do with being in checkmate.
> Being computable doesn't mean much, 4+4 is computable but probably
> won't help my chess program.
>
> I'm telling you, we have the same exact problems in Go and in chess,
> the issue is just clouded by the fact that chess programs search so
> deeply that people think intelligent evaluation is going on.
>
> Don
Chess has a useful exact metric -- forced win! -- which is useful in a
significant fraction of the game space.
It's relatively straightforward to write a computer program which
reads out forcing sequences close to checkmate (at least all sequences
of checks, plus perhaps some search extension bonus for other kinds of
moves, e.g. moves which clobber king safety). It's also
straightforward to put together a database of won endgames. And you
can afford to do an N-ply search on top of that evaluation, for N=8 or
more. Just on that alone, you'll ambush amateur players from time to
time. Simply avoiding game states which aren't lost immediately by
these analyses is a nontrivial challenge for the club players I've
watched and played. Computers do it easily.
In Chess, once you're out of your opening book, you have a significant
chance of finding a forced win in, say, 8-12 plies of full-width
search. In Go at the same point in the game, even if you searched
80-120 plies, you'd have zero chance of finding a forced win, unless
you can make a huge breakthrough in position evaluation. So "searching
so deeply that people think intelligent evaluation is going on" ends
up means something hugely different in Chess than in Go.
Even if a Chess program is relatively clueless about where to go
within the safe subspace of the full game space, perhaps because of
the enormous difficulty of writing a useful approximate evaluation
function for Chess, the program still gains a lot from the way that
this relatively safe subspace (no provable win in N moves) is a twisty
maze through the full space, and it's a continuous challenge to stay
inside it. (It's a challenge for me at N=8 or so, and a challenge for
Kasparov at N=14 or so:-). Chess programs are sufficiently good at
dealing with this challenge that their advantage here helps them win a
fair number of games, both directly, and also indirectly by
constraining their opponents to avoid sharp situations where this
advantage would be telling. Go programs have no such advantage.
It's also interesting that writing a program to solve most Chess
problems I've seen (mate in N, or small endgame problems) is pretty
straightforward, while writing a program to solve Go problems
(tsume-go) seems to be quite a bit trickier. I'm not sure where that
fits into this, though.
--
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
software consultant
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C B9 25 FB EE E0 C3 E5 7C