How do these link list of liberties and array of liberties variants work? Are they sorted lists/arrays?
I considered bitmaps but it seemed in many ways a bit wasteful i.e. in most cases for a given group the bitmap probably is extremely sparse. Also if you are trying to identify individual bits I cannot think of any techniques to do this quickly. --- On Sat, 8/15/09, w...@swcp.com <w...@swcp.com> wrote: > From: w...@swcp.com <w...@swcp.com> > Subject: Re: [computer-go] representing liberties > To: "computer-go" <computer-go@computer-go.org> > Date: Saturday, August 15, 2009, 10:54 AM > I tested bit maps in the cgbg > framework, and they perform > slower than other techniques. However, I wrote the code in > C which > does not use the built-in hardware bit tests and sets nor > use SIMD > to merge or clear sets. If you do it in assembler, bitmaps > might work > much better. > > There are various ways that bit test could be combined with > other > techniques such as linked list. However, as far as I know, > these > combinations have not been extensively explored. > > Part of the reason is that the average number of liberties > in a chain > during an insert (when running MC playouts) is only about > 1.3. > > Michael Wing > > > I've seen bit-maps mentioned many times, but is there > any evidence > > it's faster than a 'traditional' implementation? > > > > You can also use board-sized bitmaps. Merging is > a trivial OR > > > operation. > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
