[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: [computer-go] Learning : was Chess programs versus go programs
I think that going to 4 liberties instead of 3 doesn't cost much, since it
is easy to prove that most 4 liberty groups must get 5 liberties soon. I'll
try the experiment though, and see what the speed/strength tradeoff is for
defining escape as 4 liberties instead of 5.
You make a very good point about wasted search. I started with tactics and
added life and death later, so perhaps some of my tactical search is now
redundant.
David
> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx] On Behalf Of Mark Boon
> Sent: Saturday, December 11, 2004 3:03 AM
> To: computer-go
> Subject: RE: [computer-go] Learning : was Chess programs
> versus go programs
>
>
> > -----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/
>
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/