The solution that John Tromp found, for 9x9 is this: Keep an extended pseudo-liberty count that looks like this: lower 8 bits: Standard pseudo-liberty count next 12 bits: Encoding of x-coordinate information next 12 bits: Encoding of y-coordinate information
For each block of 12 bits we need to find 9 numbers with all the desired properties of being able to tell whether an arbitrary sum of up to four of them (possibly repeated) comes from adding up the same number up to 4 times. For this, we use the following numbers in base 5: 00011 00101 00110 01001 01010 01100 10001 10010 10100 11000 (one extra ;) ) Since 5^5 < 2^12, 12 bits is enough to store any sum. Now if the sum looks something like 03030, you know that it's from adding 01010 three times. A 4096-entry lookup table is used to decode the two 12-bit blocks separately. Now it's easy to combine the results to know where the last liberty of the chain is. For 19x19 you need to use 6-digit numbers in base 5 and use numbers with exactly three ones (there are 20 of them). Unfortunately, you need 12 bits for the traditional pseudo-liberty count and 14 for each block, so you are out of the 32-bit realm. A quick computation shows that you can get to sizes of over 200x200 and stay within 64 bits. Álvaro. _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
