RE: [computer-go] Designing faster, better influence functions

["Mark Boon" <tesuji@xxxxxxxxx>]

There are some things for which you can do incremental book-keeping, and
some for which you can't. When two chains merge, you'll have to do something
of O(n). You can try to keep n to a minimum by trying to process only the
smallest part of the merge, but in principle this is unavoidable.

So far I never did incremental book-keeping when it came down to
liberty-lists. If I had to start again I would probably experiment with it,
as I think some performance gain can be had there. But it doesn't eliminate
the need for my getNlib example altogether, as I also use it to figure out
how many liberties a move *would* make *if* it got played etc. When I was
referring to 20-30%, it wasn't for a playing program of course, but the
life-and-death program, which relies much more on tactics.

For global groups the situation is worse. They merge and get split much more
than chains, and involve bigger areas. So I still see good use for a fast
flood-fill operation. And by that I don't mean some special
assembler-routine (sorry Frank, I can't understand your code) but rather
some 2D-graphics library call that can be processed by the hardware on a
graphics card, if available.

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of Peter Drake
> Sent: Tuesday, November 02, 2004 15:42
> To: computer-go
> Subject: Re: [computer-go] Designing faster, better influence functions
>
>
> This is something that has always confused me:  I can see how to
> incrementally update the liberty count of a block if it is simply
> expanded by one stone, but what if two blocks are merged or (in an
> undo) split?  Blocks of vacant points can be split by a move or merged
> by an undo.
>
> Similarly, it is difficult for a block to keep track of neighboring
> blocks if they are splitting and merging all over the place.  Do people
> have a way of doing this, or do you just recompute this information
> from scratch after each move?
>
> Peter Drake
> Assistant Professor of Computer Science
> Lewis & Clark College
> http://www.lclark.edu/~drake/
>
>
> On Monday, November 1, 2004, at 07:29  PM, David Fotland wrote:
>
> > Many Faces also keeps incremental lists of liberties and liberty
> > counts,
> > block sizes, etc.
> > It's very fast.
> >
> > David
> >
> >> -----Original Message-----
> >> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> >> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx] On Behalf Of Evan Daniel
> >> Sent: Monday, November 01, 2004 5:33 PM
> >> To: computer-go
> >> Subject: Re: [computer-go] Designing faster, better influence
> >> functions
> >>
> >>
> >> On Tue, 2 Nov 2004 02:14:52 +0100, Mark Boon <tesuji@xxxxxxxxxxxxxxxxx> wrote:
> >>> I don't think I would want to get into using CPU-specific
> >>> instructions. But I must say I've sometimes thought about
> >> what could
> >>> be useful to have in terms of Go-specific hardware. In
> >> Tsume-Goliath I
> >>> think I found that the single most expensive function was
> >> getNlib(),
> >>> which would retrieve the number of liberties of a chain at
> >> a certain
> >>> coordinate and put the coordinates of those liberties in a little
> >>> list, with a maximum of 'n' liberties. A very simple and basic
> >>> function, used in a lot of different places. The total time
> >> spent in
> >>> this one function was something like 20 or 30%.
> >>
> >> Have you looked at how GNU Go deals with the problem?  The
> >> GNU Go board code keeps incremental updates of things like
> >> liberty counts, liberty locations, etc.  I don't really
> >> remember how fast it is, but I don't think it spends that
> >> much of the runtime on it.
> >>
> >> Evan Daniel
> >> _______________________________________________
> >> 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/
> >
>
> _______________________________________________
> 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/