|
Hello all,
It has been a while since I have participated on this list - its been
fun reading
the posts lately though - at least there has been some lively
discussion. ;-)
I suggested this type of multi-level search technique where the global
search
works on higher level "moves" in a post to this list back in May of
1998 soon after learning
about go, studying it and computer-go including all the computer-go
archives at
the time and other research papers. I had started writing a go
program,
but lacked the time and motivation to continue putting any effort into
it. Its hard to believe that was six years ago. Since then, I have
kept up with the discussions on the computer-go list, submitting a few
posts and playing around with a few related algorithms/code from time
to time but not
doing any serious work.
It's also interesting that in that six years, the progress of
computer-go
playing strength and generally accepted/common techniques for
programming go
have made little, if any, significant progress. I hope all of you
working
diligently on your go programs don't take offense to that
characterization, but
that's how it seems to me. That is until recently IMHO.
I think the SlugGo experiment, which uses a parallel multi-level search
technique (correct me if I'm wrong), showing a potential improvement of
5-6
stones over its "root" program and measurable improvement against
another program is significant. I still believe this type of technique
is
most definitely one key to computers playing high-level go. I think
the
same idea can be taken to much further extremes than SlugGo and with
less
complexity and overhead by implementing a search specifically designed
towards
this end. This is not to discount what the SlugGo team has
accomplished. I'm excited to see how their experiment and its results
progress. Keep up the good work!
Also, Frank de Groot's work on his pattern system that harvests
patterns from
game records, despite all the doubts espoused on this list about it,
appears to
me to be very promising - as _one_ component of many in a go program,
just a
Frank has been repeatedly saying over and over. I've posted doubts
about
hand-coded pattern based systems and hand-coded heuristics due to the
fact that
as the number of patterns and heuristics grows, the harder it is to
keep the
system consistent and keep the rule integrity high. Its sounds like
Frank's system could be of great benefit as a move generator base for a
local
and/or global search engine. Also Frank's Moyo Go Studio looks to be
quite impressive from the web site screen shots. If it’s not too
expensive, I'll definitely be buying a copy when it’s ready.
There is little question in my mind that searching is a key to
computer-go just
as it was in chess. It may not be the same kind of search (muti-level
for example), and the
evaluations (including life and death) may not be as easy but I think
it’s the
most promising direction to pursue in combination with pattern based
concepts for move generation and help in evaluation.
Matt
Heikki Levanto wrote:
On Fri, Dec 03, 2004 at 01:17:16PM -0500, Don Dailey wrote:
I thought you did a wonderful job of articulating the problem. This
is the thing that kills a global search and needs to be dealt with
properly to proceed with global searching programs (if that's what we
want to persue.)
I think some work has been done towards solving this, although I don't
have any clear references.
It sounds reasonable to assume that one can do the local searches, and
simplify them into straight sequences, or at least into small trees.
While reading, one should be able to mark possible tenukis (ignoring the
local situation and playing elsewhere).
Now, having a pile of such trees, a higher-level search can try to
decide which local battle to fith at each "move" (which can represent a
longer forced sequence).
If all local moves are graded in terms of their size and urgency
(temperature?), then we should have enough data to make meaningful move
ordering and pruning in the higher-level search.
I don't know if anyone does this sort of multi-level search, and what
practical the practical limitations of such an approach. As with any
search, it needs a decent evaluation function, but that is another
problem...
Regards
Heikki
|