RE: [computer-go] Learning : was Chess programs versus go programs

["Mark Boon" <tesuji@xxxxxxxxx>]

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of David Fotland
> Sent: Saturday, December 11, 2004 2:36
> To: 'computer-go'
> Subject: RE: [computer-go] Learning : was Chess programs versus go
> programs

> I do use alpha-beta+evaluation.  The issue isn't a/b, but the
> high amount of
> pruning required by the slow evaluation function.  The real
> debate should be
> whether one can make a good enough evaluation function without using local
> tactical search inside the evaluation.  That's what makes evaluation so
> slow.  I believe local search is required since if tactical stability of
> stones is not established, there is no way to estimate territory.

I also found using a lot of tactical search slows down the evaluation too
much. Reading ladders (or 2-liberty problems) is fast, I get that almost for
free. But anything beyond that needs serious pruning and then it still slows
down evaluation a lot. Moreover, when you do pruning you lose the certainty
that the outcome is correct.

So I more and more moved away from using tactical search inside the
evaluation function to determine if I can capture stones. If you think about
it, it's not strictly necessary. During evaluation of groups you find some
without eyes. If they don't have weak neighbours then they're going to be
evaluated dead. Any reading you did on such a dead group are wasted cycles.
If they do have weak neighbours, then things can get really complicated. In
some of those cases, tactical search is the fastest way to find out which of
the weak groups is going to win the fight, so you can selectively use it
there. And possibly extend the search-depth, as you really want to get those
right.

Then there's the case of course where a chain can be captured tactically,
but otherwise it evaluates to completely alive. It's actually rare to happen
for a 3-liberty problem to appear in a case that is otherwise evaluated as
alive. Still, it will probably happen a few times per game. Since you can't
afford to miss those, you still need to look for them. But you can do it
after everything else. You'll find that that is much faster, as usually the
tactical searches that take long are the ones that have weak neighbours, or
that are loose inside territory.

I've never gone beyond 3 liberties. I got to 6-dan by counting 1-2-3-many. A
4-liberty tactical capture of something that would otherwise evaluate to
alive is really, really rare. Does anyone have counter-examples?

At the moment I'm doing part-time remote work. So I have had plenty of time
to do some more work on the Go library. I'm enjoying it imensely. Although I
never smoked, I imagine it's similar to a former chain-smoker lighting his
first cigarette after years of abstinence :)

I've always felt that tactical searches or L&D search should use
automatically learned patterns, not so much for pruning as for move
ordering. My library is to the point now where it has tactics and a
pattern-matcher and last night I was actually contemplating the possibility
to automatically generate patterns after each tactical search and then use
those patterns for subsequent reading. The more I think about it, the more
it seems like a good idea. My estimate is that using the pattern-matcher
during tactical search is going to make it search at half the speed (in
nodes/sec.), maybe even worse. But I think it's easily going to make up for
those in nodes saved by better move-ordering or recognising a situation as a
capture outright, without reading (tricky, I know).

To get there, I'll need to automatically generate patterns. This could be
done after the game, but then I don't get to benefit from it during a game.
When I generate patterns during the game, there are going to be a few speed
bottlenecks:
- I'll need to keep a move-tree of the search. This means some slow-down of
the search, but hopefully isn't going to be too bad.
- Then I need to generate the pattern(s) from the resulting search-tree.
This is easily going to be more expensive than the actual search.
- Then it needs to incorporate those patterns in the decision-graph to
enable speedy lookup. That might take some time too.

These costs mean it will only be worth it if after some time it starts to
find patterns in other places than the situations where they originated. And
those patterns will have to be better than a few hand-coded ones. I'll have
to think of some good test-cases. One can easily be fooled into wrong
conclusions by messing up the test-cases. One step beyond that will be to
see if some patterns start to look similar and see if more generic patterns
can be deduced from them. Not easy, but that's when this thing would start
to be really powerful.

Anyway, it would be an interesting little project to sink my teeth in.



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