In the cgbg framework, arrays and lists are unsorted. But, there are many reasonable variations.
You will just have to jump in and read some code or write your own to fully understand. I recommend reading the gnugo source, which is pretty darn good. Michael Wing > 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, [email protected] <[email protected]> wrote: > From: [email protected] <[email protected]> > Subject: Re: [computer-go] representing liberties > To: "computer-go" <[email protected]> > 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 > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ > > _______________________________________________ > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ > -- _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
