On Nov 24, 2007 10:38 AM, <[EMAIL PROTECTED]> wrote:
> * 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.
It's embarrassing how long it took me to notice that you were
exploiting the theorem that if you have n terms that sum to m, then
the sum of the squares of the terms will exceed (m**2)/n unless each
term equals exactly m/n. (This is essentially the same statistics
theorem that says that the expected value of the square equals the
square of the expected value plus the variance.)
Instead of smushing the three parts of your triple together, why not
keep them separate? So when you add a 1-dimensional coordinate, you do
{
libs++;
sum += coordinate;
sumSquares += coordinate * coordinate;
}
which is admittedly a little more complicated than a table lookup, but
then the atari test becomes
(sum * sum == sumSquares * libs)
Computing the triple-sum and testing for atari are just a couple adds
and multiplies. The process involves no initialization, lookup tables,
64-bit numbers, loops, branching, divisions, or remainders, and (even
though this doesn't matter for normal go, it's still nice) there's
almost no limit to how many duplicates of the same value you can
detect. I like it.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
