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. > * 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? 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. PS: Did you see the solution by Eric Boesch that used bit masking and no random numbers? > * 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. > > -- Michael Wing _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
