[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: [computer-go] Designing faster, better influence functions
Merging blocks is easy. Just merge the two liberty lists. I keep the old
lists
from before the merge, so it is easy to take back the move and split as
well.
I keep liberty lists sorted, so the merge operation is linear in the number
of liberties,
and it is easy to find duplicate liberties and update the liberty counts.
They aren't merging all over the place, only local to the last move.
Splitting only
happens when a move it taken back, so just restore the old values. No need
to recalculate.
David
> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx] On Behalf Of Peter Drake
> Sent: Tuesday, November 02, 2004 12:42 PM
> 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/