Thanks. What about linked lists? They seem to be both compact and fast to merge and detect duplicates. Why have you abandoned them?
Lukasz On Tue, Apr 7, 2009 at 17:42, David Fotland <fotl...@smart-games.com> wrote: > 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/ > _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
