In Many Faces' playouts I don't keep arrays of liberties. I just keep the counts. In the older program I keep linked lists of liberties.
David > -----Original Message----- > From: [email protected] [mailto:computer-go- > [email protected]] On Behalf Of [email protected] > Sent: Monday, April 06, 2009 10:36 AM > To: computer-go > Subject: Re: [computer-go] Pseudo liberties: Detect 2 unique liberties? > > 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/ _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
