On Tue, Apr 7, 2009 at 07:40, David Fotland <fotl...@smart-games.com> wrote: > 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.
How do you count the number of liberties when you merge two groups? Do you walk over both chains searching for duplicates in their empty neighbourhoods (duplicated liberties)? Lukasz > > David > >> -----Original Message----- >> From: computer-go-boun...@computer-go.org [mailto:computer-go- >> boun...@computer-go.org] On Behalf Of w...@swcp.com >> 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: 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/ >> > >> >> >> >> -- >> >> >> >> _______________________________________________ >> 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/ > _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
