Jason House <[EMAIL PROTECTED]> said: > > On Sat, 2007-11-24 at 08:38 -0700, [EMAIL PROTECTED] wrote: > > To follow up on this thread, I have been playing with > > psuedo liberties a bit, and here is my solution. > > > > * I use 2 vectors of values. The first is used for > > storing the pseudo liberty values. The second lists has > > all 1*, 2*, 3*, and 4* the values, which are sorted. > > Binary search will show whether the value is for > > a single liberty or not. Division is still a pretty > > expensive op. This uses 2 additional memory lookups. > > I assume you mean 2 additional look-ups verses storing just the 1x > values as opposed to other methods.
Yes. I use 2 additional lookups, rather than 2 divides or the bit masking. > > * For liberty values, I use the following equation: > > values[i] = 250000000 + (160000 * (i+1)) + ((i+1) * (i+1)); > > Some bits are constant, some are linear, and some > > are quadratic, which guarantees that the sum of > > up to 4 values will only be in the set if they > > are from the same liberty. I have more confidence > > in an equation than in random numbers. > > Since 160,000 < 2*(19*19)^2, a value well below the various possible > sums of squares, I have to ask what additional work you've done to prove > that the overlap doesn't cause problems? 160,000 is greater than (19 * 19 + 1)^2, so the linear term does not interact with the quadratic term at all. This is not a problem. The unit test code in the previous email tests all possible combinations of up to 4 liberty values, so it has been empirically verified. > If 160,000 was replaced with a number greater than 4*(19*19)^2=521,284, > I'd have no worries. Of course, if you used 521,285, the 250,000,000 > would need to be at least 752,735,541... yielding overflow of 32 bit > values with only 6 liberties. Using larger constants will work just fine, too. The problems with overflow are (in practice) no better or worse than using the smaller constants. In both cases, the program needs to use int64 for the pseudo-liberty value or use an additional pseudo-liberty count. > PS: Did you see the solution by Eric Boesch that used bit masking and no > random numbers? I saw it, but I didn't understand it. However, since it does array references inside a for loop, it probably does at least as many memory accesses as this solution. -- Michael Wing > > * These numbers are small enough that they fit in > > 32 bits. Unfortunately they are so large that > > the sum of say 20 liberties takes more than 32 bits. > > One solution is to use 64 bits for pseudo liberties. > > Another solution is keep a count of PLs, and also > > a 32 bit unsigned PL value, igoring overflow, and > > only check the PL value when the PL count is less > > than 5. _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
