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

[William Harold Newman <william.newman@xxxxxxxxxxx>]

On Fri, Dec 05, 2003 at 09:04:12PM -0800, David Fotland wrote:
> 
> >
> >
> >
> >(I'm aware that people -- including, I think, David Fotland on this
> >list -- have reported higher than 80% success at choosing the right
> >move in such problems. But what I mean by "solve" is to arrive at a
> >100% certain answer, so that the program either returns "this *is* the
> >move" or "I'm not absolutely sure, I need to think more". That is,
> >"solve" as pros solve such problems, or as computers solve the
> >corresponding chess problems.)
> >
> 
> Go Tools by Thomas Wolf can solve 100% of those problems very 
> quickly.  It's designed as
> a go problem solver, but it took many, many years to write.

I've never experimented with GoTools, but I read a paper by Wolf some
time ago and was left with the impression that GoTools is limited to
problems enclosed by iron walls (and that it does very well indeed on
those, much better than I can). Two examples of the kinds of problems
I remember are shown in the "Overall Strength" section of
  <http://www.qmw.ac.uk/~ugah006/gotools/>.
The example in the upper right corner of the same page shows that
GoTools can also understand walls with possible cutting points, so it's
less finicky than I realized. But can it also handle incompletely
enclosed problems like #192, #194, or #199 in GGPFB4? The web page
says "The main current limitation is that the program can solve only
fully enclosed positions," so I doubt it.
  
#192 fits reasonably easily on a 9x9 board as
    A B C D E F G H J
  9 . . . . . . . . . 9
  8 . . O . . . . . . 8
  7 . . O # . # . . . 7
  6 . . . # . . . . . 6
  5 . O O # . . . . . 5
  4 . # # . . . . . . 4
  3 . . . . . . . . . 3
  2 . . # . . . . . . 2
  1 . . . . . . . . . 1
    A B C D E F G H J
although the presence of the lower wall probably makes it less likely
that a program will get confused by long weird escaping sequences
around B2.

As far as I know, going from excellence in iron-enclosed problems to
competence in effectively-enclosed problems like #192 is an unsolved
problem with no obvious answer, because GoTools or similar approaches
have a lot of trouble with variations threatening to escape.
(sequences like white E8, black D8, white D9; then if black blocks
around F8, white D4 "threatening" confusing things like a placement at
B3, or pushing through at E7 and cutting at F6; or if black plays
something other than a block around F8, white jumps out to G8 or G9 or
H9 or something) Even when such threats fail, as long as they fail
without losing sente and without doing much to use up the life and
death aji left in the enclosed space, they make it hard to get to an
evaluable endpoint in a reasonable search depth.

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
"about as much chance as a one-armed blind man in a dark room trying
to shove a pound of melted butter into a wild cat's left ear with 
a red-hot needle" -- Ukridge (P.G. Wodehouse)
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://computer-go.org/mailman/listinfo/computer-go