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

[tesuji@xxxxxxxxx]

> 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.
>

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.

> 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.
>
Well, as I said before, you may never get the level of certainty of Chess
programs. The reasons being more or less along the lines as you describe
yourself. However, the tsume-go program we made would solve problems as
shown in the diagram above with a higher accuracy than your average
dan-level amateur. And much faster too. With todays computers I'd estimate
the problem above would be solved in a matter of seconds. So I think it's
not nearly as impossible as you seem to think. And here speed *would*
matter. For a playing program it matters a great deal whether it can
afford such a search once per move or hundreds of times per move.

The main weakness I found in our tsume-go program was that it used the
same algorithms to determine eye-space as in Goliath. These algorithms are
very fast and reasonably accurate, but I found that for tsume-go
'reasonable accuracy' is not really good enough. Now I'm convinced that
with different eye-space algorithms, based on local search, would give
much better accuracy. It would probably make the search slower, but I
think a large part of it would be returned by the fact that you can stop
searching much earlier when your evaluation is more reliable. It would
probably take me a year to implement it though... Maybe I'll have that
kind of time again when I retire :-)

The difficulty, I mentioned in a mail before, of incorporating a
single-minded tsume-go program into a playing program can be demonstrated
by the diagram above. Our program would be significantly faster if you
asked it to kill the stones at B5 and C5 than when you asked it to kill
the stones at C7 and C8. It would be a waste though to have to run the
tsume-go part twice, once for each separate chain. So we'd use a heuristic
to determine the 'strongest' chain and go for that one. However that
potentially has the disadvantage that if it would not be possible to kill
C7 but it would be possible to kill B5, the program would only respond
with a 'not killable' to the question whether the group could be killed as
a whole.

I think this is an essential capability of humans that has yet to be
solved in software. It's when trying to pursue a particular goal, a human
is able to remember details of things happening in relevant parts of the
search-tree that can be used at a later time. Programs generally perform a
search and only return a simple status code about the success or failure
of the search, and nothing about the circumstances of that particular
result and use that knowledge to solve other problems. So basically a
wealth of information that is acquired during the search is simply
discarded as soon as the search finishes.

Possibly this would be a much more interesting thread: anyone any ideas?

A first step could be to annotate the result with information about the
situation in some of the critical end-leaves. So the result could be
something like: "alive with a maximum of n points or losing chain x (in
sente or gote)." This would be extremely useful information to a playing
program and well worth whatever extra resources it would take to gather
such information during the search and pass it up the tree.

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