Yes, I walk both chains looking for duplicates. This is quite fast if done efficiently, since group merging is rare enough. I found keeping the liberty arrays to be slower since they are big, so there is more copy overhead in the UCT tree, and they are not cache friendly.
David > -----Original Message----- > From: computer-go-boun...@computer-go.org [mailto:computer-go- > boun...@computer-go.org] On Behalf Of Lukasz Lew > Sent: Tuesday, April 07, 2009 2:32 AM > To: computer-go > Subject: Re: [computer-go] Pseudo liberties: Detect 2 unique liberties? > > 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/ _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
