I made some artificial tests where I do x inserts, 1 delete, 10 counts and 1 merge. For x=4 inserts, linear arrays are about 4 times faster. For x=8 inserts, linear arrays are about 3 times faster. From your data I calculated an average liberty count of 2.8 (which seems low to me). This means that for the used board sizes, the constant time merge does not pay off vs. the constant time count.
So I can confirm that the linear arrays do seem to be faster, however I haven't tested how they compare to pseudo libs. For heavier playouts, I reckon that true liberties might be a bit faster and more useful. Isaac -------- Original-Nachricht -------- > Datum: Fri, 3 Apr 2009 10:22:37 MDT > Von: w...@swcp.com > An: "computer-go" <computer-go@computer-go.org> > Betreff: Re: [computer-go] Pseudo liberties: Detect 2 unique liberties? > Isaac, > > Most groups have only say 4 to 8 liberties. This is why simple arrays of > liberty locations work so well. The new Intel CPUs have instructions > that can search strings 16 bytes at a time, so it could run even faster. > > Bit vectors also work, but if you want a true liberty count, then you have > to avoid counting (1 or 1) as 2, which is the pseudo liberty problem, and > which takes more code to write and more time to compute. > > When I started, I wanted to find a better implementation than gnugo, and > I was unable to do so. Of course one can refine or simplify the gnugo code > in many different ways, but gnugo has all of the good ideas. > > Michael Wing > > > > PS: Here is the data for how many times the program tried to insert > a stone into a chain that has x liberties or x adjacencies. It was taken > from a run that combined monte carlo simulations and ladder reading > exercises. Note that there are only 2% as many liberties/adjacencies > of size 8 as there are of size 0. Chains with liberties/adjacency lists > of size 16 are so few as to be irrelevant. > > data here. > > > >> On Thu, Apr 2, 2009 at 5:14 AM, <w...@swcp.com> wrote: > >>> Isaac, > >>> > >>> I implemented about 6 way to track liberties, > >>> a couple years ago, and measured the running > >>> performance, and by far the best is also the > >>> simplest: keep an array of liberties for each > >>> chain, and do a simple linear search. > >>> > >>> This may seem slow, but it has a couple real > >>> advantages. First, it works with the cache > >>> to maximize locality. Second it is very simple. > >>> > > > > This *does* seem slow, even when caching the number of liberties. You > > mentioned that you did this a couple years ago, do you think it still > holds > > true? Thank you for the information. > > > >> This is what I do too. I never bothered with bit-arrays but possibly > >> that's simply because I fail to see how you can merge two chains and > >> count liberties in O(1). > > > > Merging would be a simple OR operation. Counting can be done, for > example, > > with some kind of binary search. Counting the bits set has been well > > researched and many different algorithms exist. > > > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ -- Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
