RE: [computer-go] Re: 9x9 search,tsume-go (was Re: Computer Olympiad photo)

["Anders Kierulf" <anders@xxxxxxxxxxx>]

> A while ago I thought I read somewhere that Thomas Wolf improved
> his program so that it doesn't need an enclosure as rigid as before.
> If it's now incorporated in Kierulf's program it must be, otherwise
> it would be next to useless.

Not so. GoTools is indeed used a lot in SmartGo, but currently always with a
rigid enclosure. During the Olympiad in Graz, it played 33 moves that were
generated by GoTools (25 to kill and 8 to live). For example: Moves 192 and
194 against Aya, move 278 against Indigo, move 183 against Go Intellect, and
moves 278 and 290 against NeuroGo. (The SmartGo games are all available at
http://www.smartgo.com/olympiad2003.sgf; use the free SmartGo:Viewer if your
SGF reader doesn't handle game collections properly.)

In addition to generating these moves, GoTools helps SmartGo evaluate groups
at every node of the global search. SmartGo spends about 20% of the time for
a 19x19 game in GoTools code. (On 9x9, it currently spends over 50% of its
time in GoTools, which is way too much, and is being fixed.)

The basic strategy SmartGo uses to benefit from GoTools is for SmartGo to
always enclose the area in question before passing it to GoTools, as SmartGo
knows a lot more about the stability of surrounding groups than GoTools
does. Of course, a lot can go wrong:
- There are cases where SmartGo doesn't compute the right enclosure.
- There are cases where SmartGo computes an enclosure that's bigger than
necessary, and then GoTools fails to solve the problem in the time
available.
- There are cases where any correct enclosure (one that doesn't change the
result of the life and death problem) would be too big for GoTools to solve
in a reasonable amount of time.
- There are cases where enclosing the area removes crucial interactions with
other areas.

To avoid some of these problems, SmartGo often passes a problem to GoTools
with three different enclosures:
- A minimal enclosure just around the main eye space to see if a group is
clearly alive (very fast).
- A heuristically reasonable enclosure that may miss some threats against
surrounding blocks (but may be fast enough).
- A larger enclosure that includes all the blocks that can be used for
threats (usually too slow, unfortunately).

Each of these may return useful information to SmartGo. In general, having
GoTools available is a great help, but a lot of improvements can be made in
SmartGo's use of GoTools, e.g. calling it only when it's likely to return a
result in the time available, playing out some threats to simplify the
problem before passing it to GoTools, and integrating it further into
SmartGo to be able to use it at a more fine-grained level.

Anders Kierulf
www.smartgo.com


_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://computer-go.org/mailman/listinfo/computer-go