On Tue, Nov 13, 2007 at 04:11:24PM -0500, Imran Hendley wrote:
> I definitely understand the idea now, and it looks very good. However
> this implementation could break:
>
> Say we have pseudoliberties at intersections: 99,100,101. We sum those
> up to get 300, divide by the number of pseudoliberties - 3, get back
> 100, check to see if 100 is a liberty, and since it is we conclude
> that we have one liberty at intersection 100 that we counted three
> times, and hence our string is in atari.
So we cant use numbers 1..81
Let elaborate a little more on this. We want one number for each cells :
nums = {n1, n2, n3, ..., n81}
And we want the following properties :
for any a, b in nums :
(a + b) / 2 is in nums --> a == b
for any a, b, c in nums :
(a + b + c) / 3 is in nums --> a == b == c
for any a, b, c, d in nums :
(a + b + c + d) / 4 is in nums --> a == b == c == d
If we have this we are sure to don't have problems like you pointed.
Using brute force search, I've produced the following sequence of
numbers :
[17, 18, 21, 30, 49, 86, 134, 274, 590, 1061, 1348, 2301, 3005, 4805,
7609, 11157, 17802, 19393, 29046, 31538, 41442, 49154, 74823, 97358,
134625, 148826, 217801, 234930, 294657, 402550, 452686, 610274,
726514, 885190, 1040877, 1070361, 1337862, 1611001, 1829345, 1962193,
2308061, 3007701, 3133837, 4007989, 4727218, 4883797, 5546029, 7454733,
8548661, 9547305, 11552366, 13177582, 13697142, 14689461, 15538838,
15733662, 21054617, 22691377, 24433197, 27274934, 31994414, 35217106,
37507258, 41114134, 45045090, 47089386, 57357330, 62400606, 68297193,
75036946, 83039110, 96477718, 110160994, 119390498, 122575210,
148912497, 156351446, 168096257, 176942297, 194310098, 211199842]
This sequence is not the best you can found, but it was quick to
generate...
But now we have another problem... We have the sum of the number of the
pseudo libertyes of a chain, and we can compute (sum / nb_plibs) but
next we have to check if the resulting number is in the list.
In some cases the number (sum / nb_plibs) will not be an integer so it
is trivialy not in nums, but for all the other cases this will require
log(81) operation using a binnary search.
Actually, when I need to check for atari on a group with 2,3,4 pseudo
liberties, I search a liberty of this group and check how mch plibs it
add to this group. I don't known if this will improve the speed but it
add a lot of complexity and atari-checking doesn't represent so much of
the calculations done by my engine to be valuable.
And the second problems is that this solution doesn't scale well. On
19x19 you need 361 numbers in your list, so even if you find a list like
this, I doubt that you can sum up the value of all the pseudo liberties
of a big group without overflowing an unsigned and you have to switch
to bigger int like int 64.
So I think John was suggesting something different in his first mail,
but I still search what it can be...
Does anyone have an idea ?
Tom
PS: I'm very sorry for my poor english
--
Thomas Lavergne "Le vrai rêveur est celui qui rêve
de l'impossible." (Elsa Triolet)
[EMAIL PROTECTED] http://reveurs.org
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
