Isaac, My numbers were extracted from the insert() function, so my numbers don't say how long the average search. would be. When you place a stone on the board, you immediately add up to 4 adjacent liberties, one at a time. Never-the-less, it does say something.
I have intended to measure the distributions of all set operations in the board funcions, but I have not finished them. Space is also very significant when choosing a representation. Another issue is whether the board can undo or rewind to saved positions. The arrays that store liberties take 19*19*256 shorts or 184832 bytes. (A chain can only have about 2/3 of the locations on the board as liberties, if you follow the usual rules.) This overwhelms all other data in the board. Michael Wing > 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: [email protected] > > An: "computer-go" <[email protected]> > > 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, <[email protected]> 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 > > [email protected] > > 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 > [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/
